Identification and comparison of protein-protein interactions that occur in populations

• US 6,083,693 A
• Filed: 06/14/1996
• Issued: 07/04/2000
• Est. Priority Date: 06/14/1996
• Status: Expired due to Fees

• Current Assignee: CuraGen Corporation (Celldex Therapeutics Incorporated)
• Original Assignee: CuraGen Corporation (Celldex Therapeutics Incorporated)
• Inventors: Nandabalan, Krishnan, Rothberg, Jonathan Marc
• Primary Examiner(s): Zitomer, Stephanie W.
• Application Number:
  US08/663,824
• Time in Patent Office: 1,481 Days
• Field of Search: 435/6, 435/69.1, 435/69.7, 435/70.1, 435/71.1, 435/254.11, 435/172.3, 436/501, 935/77, 935/78
• US Class Current: 435/6.13
• CPC Class Codes: B01J 2219/00605 the compounds being directly bound or immobilised to solid supports
• CPC Class Codes: B01J 2219/0061 The surface being organic
• CPC Class Codes: B01J 2219/00659 Two-dimensional arrays
• CPC Class Codes: B01J 2219/00677 Ex-situ synthesis followed by deposition on the substrate
• CPC Class Codes: B01J 2219/00689 using computers
• CPC Class Codes: B01J 2219/00695 Synthesis control routines, e.g. using computer programs
• CPC Class Codes: B82Y 30/00 Nanotechnology for materials or surface science, e.g. nanocomposites
• CPC Class Codes: C12N 15/1055 Protein x Protein interaction, e.g. two hybrid selection
• CPC Class Codes: C12N 15/81 for yeasts
• CPC Class Codes: C40B 30/04 by measuring the ability to specifically bind a target molecule, e.g. antibody-antigen binding, receptor-ligand binding
• CPC Class Codes: G01N 33/6845 Methods of identifying protein-protein interactions in protein mixtures
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/10 Sequence alignment; Homology search

Abstract

Methods are described for detecting protein--protein interactions, among two populations of proteins, each having a complexity of at least 1,000. For example, proteins are fused either to the DNA-binding domain of a transcriptional activator or to the activation domain of a transcriptional activator. Two yeast strains, of the opposite mating type and carrying one type each of the fusion proteins are mated together. Productive interactions between the two halves due to proten--protein interactions lead to the reconstitution of the transcriptional activator, which in turn leads to the activation of a reporter gene containing a binding site for the DNA-binding domain. This analysis can be carried out for two or more populations of proteins. The differences in the genes encoding the proteins involved in the protein--protein interactions are characterized, thus leading to the identification of specific protein--protein interactions, and the genes encoding the interacting proteins, relevant to a particular tissue, stage or disease. Furthermore, inhibitors that interfere with these protein--protein interactions are identified by their ability to inactivate a reporter gene. The screening for such inhibitors can be in a multiplexed format where a set of inhibitors will be screened against a library of interactors.

Claims

1. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein--protein interactions, said method comprising:

(a) recombinantly expressing within a population of host cells a first population of first fusion proteins, each said first fusion protein comprising a first protein sequence and a DNA binding domain in which the DNA binding domain is the same in each said first fusion protein, in which said host cells comprise at least one polynucleotide operably linked to a promoter driven by one or more DNA binding sites recognized by said DNA binding domain of said first fusion protein such that an interaction of a first fusion protein with a second fusion protein, said second fusion protein comprising a transcriptional regulatory domain, results in regulation of transcription of said at least one polynucleotide by said transcriptional regulatory domain, and in which said first population of first fusion proteins has a complexity of at least 10;

(b) negatively selecting to eliminate those host cells expressing said first population of first fusion proteins in which said regulation of transcription of said at least one polynucleotide occurs in the absence of a second fusion protein, said negatively selecting being performed by a method comprising incubating said host cells expressing said first population of first fusion proteins in an environment in which substantial death of said host cells occurs if said regulation of transcription occurs;

(c) after step (b), recombinantly co-expressing within said population of host cells a second population of second fusion proteins, each said second fusion protein comprising a second protein sequence and a transcriptional regulatory domain of a transcriptional regulator, in which the transcriptional regulatory domain is the same in each said second fusion protein, and in which said second population of second fusion proteins has a complexity of at least 10;

(d) detecting said regulation of transcription of said at least one polynucleotide, thereby detecting cells in which an interaction between a first protein and a second protein has occurred;

(e) amplifying DNA fragments encoding said first fusion protein or encoding a portion thereof comprising said first protein sequence from a plurality of host cells in which said regulation of transcription has been detected;

(f) probing a sample comprising said amplified DNA fragments with one or more recognition means, each recognition means causing recognition of a target nucleotide subsequence or a set of target nucleotide subsequences;

(g) generating one or more output signals from said sample probed by said recognition means, each output signal being produced from a nucleic acid in said sample by recognition of one or more target nucleotide subsequences in said nucleic acid by said recognition means and comprising a representation of (i) the identities of effective subsequences, each said effective subsequence being a nucleotide subsequence comprising a target nucleotide subsequence, or the identities of sets of effective subsequences, each said set having member effective subsequences each of which comprises a different target nucleotide subsequence from one of said sets of target nucleotide sequences, and (ii) the length between occurrences of effective subsequences in said nucleic acid; and

(h) searching a nucleotide sequence database to determine sequences that are predicted to produce or the absence of any sequences that are predicted to produce said one or more signals produced by said nucleic acid, said database comprising a plurality of known nucleotide sequences of nucleic acids that may be present in the sample, a sequence from said database being predicted to produce said one or more output signals when the sequence from said database has both (i) the same length between occurrences of effective subsequences as is represented by said one or more output signals, and (ii) the same effective subsequences as are represented by said one or more output signals, or effective subsequences that are members of the same sets of effective subsequences as are represented by said one or more output signals, whereby said one or more nucleic acids in said sample are identified or classified.

2. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein--protein interactions, said method comprising:

(a) recombinantly expressing in a first population of yeast cells of a first mating type, a first population of first fusion proteins, each first fusion protein comprising a first protein sequence and a DNA binding domain, in which the DNA binding domain is the same in each said first fusion protein;

wherein said first population of yeast cells contains a first polynucleotide operably linked to a promoter driven by one or more DNA binding sites recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein, said second fusion protein comprising a transcriptional activation domain, results in increased transcription of said first polynucleotide, and in which said first population of first fusion proteins has a complexity of at least 100;

(b) negatively selecting to eliminate those yeast cells expressing said first population of first fusion proteins in which said increased transcription of said first polynucleotidc occurs in the absence of said second fusion protein, said negatively selecting being carried out by a method comprising incubating said first population of yeast cells expressing said first population of first fulsion proteins in an environment in which substantial death of said first population of yeast cells occurs if said increased transcription occurs;

(c) recombinantly expressing in a second population of yeast cells of a second mating type different from said first mating type, a second population of said second fusion proteins, each second fusion protein comprising a second protein sequence and an activation domain of a transcriptional activator, in which the activation domain is the same in each said second fusion protein, and in which said second population of second fusion proteins has a complexity of at least 100;

(d) mating said first population of yeast cells that has been nevatively selected with said second population of yeast cells to fon-n a population of diploid yeast cells, wherein said population of diploid yeast cells contains a second polynucleotide operably linked to a promoter driven by a DNA binding site recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein results in increased transcription of said second polynucleotide, in which the first and second polynucleotide can be the same or different;

(e) detecting said increased transcription of said first and/or second polynucleotide, thereby detecting colonies in which an interaction between a first protein and a second protein has occurred;

(f) amplifying DNA fragments encoding said first fusion protein or encoding a portion thereof comprising said first protein sequence from a plurality of yeast cells in which said increased transcription has been detected;

(g) probing a sample comprising said amplified DNA fragments with one or more recognition means, each recognition means causing recognition of a target nucleotide subsequence or a set of target nucleotide subsequences;

(h) generating one or more output signals from said sample probed by said recognition means, each output signal being produced from a nucleic acid in said sample by recognition of one or more target nucleotide subsequences in said nucleic acid by said recognition means and comprising a representation of (i) the identities of effective subsequences, each said effective subsequence being a nucleotide subsequence comprising a target nucleotide subsequence, or the identities of sets of effective subsequences, each said set having member effective subsequences each of which comprises a different target nucleotide subsequence from one of said sets of target nucleotide sequences, and (ii) the length between occurrences of effective subsequences in said nucleic acid; and

(i) searching a nucleotide sequence database to determine sequences that are predicted to produce or the absence of any sequences that are predicted to produce said one or more signals produced by said nucleic acid, said database comprising a plurality of known nucleotide sequences of nucleic acids that may be present in the sample, a sequence from said database being predicted to produce said one or more output signals when the sequence from said database has both (i) the same length between occurrences of effective subsequences as is represented by said one or more output signals, and (ii) the same effective subsequences as are represented by said one or more output signals, or effective subsequences that are members of the same sets of effective subsequences as are represented by said one or more output signals,

whereby said one or more nucleic acids in said sample are identified or classified.

3. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein--protein interactions, said method comprising:

(a) introducing into a first population of cells of Saccharomyces cerevisiae a first population of first plasmids, each said first plasmid encoding and capable of expressing in the first population of cells (i) TRP1, and (ii) a first population of first fusion proteins, each said first fusion protein comprising a GAL4 DNA binding domain and a first protein sequence, in which said first population of first fusion proteins has a complexity of at least 100, and in which said first population of cells (i) is of a first mating type selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional URA3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences under the control of a promoter containing GAL4 binding sites;

(b) introducing into a second population of cells of Saccharomyces cerevisiae a second population of second plasmids, each said second plasmid encoding and capable of expressing in the second population of cells (i) LEU2, and (ii) a second population of second fusion proteins, each said second fusion protein comprising a GAL4 transcriptional activation domain and a second protein sequence, in which said second population of second fusion proteins has a complexity of at least 100, and in which said second population of cells (i) is of a second mating type different from said first mating type and selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional HIS3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences under the control of a promoter containing GAL4 binding sites;

(c) after step (a), incubating said first population of cells in an environment lacking tryptophan and containing 5-fluoroorotic acid;

(d) pooling surviving cells from said first population after step (c);

(e) after step (b), incubating said second population of cells in an environment lacking leucine;

(f) pooling surviving cells from said second population after step (e);

(g) mating the pooled cells from said first population and the pooled cells from said second population by mixing the cells together, applying the cells to a solid medium and incubating the cells, to form diploid cells;

(h) incubating the diploid cells in an environment lacking uracil, histidine, tryptophan and leucine, to select diploid cells containing a said first plasmid and a said second plasmid and in which transcription of the URA3 and HIS3 coding sequences has been activated, thereby indicating that a first protein has interacted with a second protein within the diploid cell, thereby detecting cells in which one or more protein--protein interactions have occurred;

(i) amplifying DNA fragments encoding said first fusion protein or encoding a portion thereof comprising said first protein sequence from a plurality of cells which survive said incubating in step (h);

(j) probing a sample comprising said amplified DNA fragments with one or more recognition means, each recognition means causing recognition of a target nucleotide subsequence or a set of target nucleotide subsequences;

(k) generating one or more output signals from said sample probed by said recognition means, each output signal being produced from a nucleic acid in said sample by recognition of one or more target nucleotide subsequences in said nucleic acid by said recognition means and comprising a representation of (i) the identities of effective subsequences, each said effective subsequence being a nucleotide subsequence comprising a target nucleotide subsequence, or the identities of sets of effective subsequences, each said set having member effective subsequences each of which comprises a different target nucleotide subsequence from one of said sets of target nucleotide sequences, and (ii) the length between occurrences of effective subsequences in said nucleic acid; and

(l) searching a nucleotide sequence database to determine sequences that are predicted to produce or the absence of any sequences that are predicted to produce said one or more signals produced by said nucleic acid, said database comprising a plurality of known nucleotide sequences of nucleic acids that may be present in the sample, a sequence from said database being predicted to produce said one or more output signals when the sequence from said database has both (i) the same length between occurrences of effective subsequences as is represented by said one or more output signals, and (ii) the same effective subsequences as are represented by said one or more output signals, or effective subsequences that are members of the same sets of effective subsequences as are represented by said one or more output signals,

whereby said one or more nucleic acids in said sample are identified or classified.

4. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein--protein interactions, said method comprising:

(a) recombinantly expressing within a population of host cells a first population of first fusion proteins, each said first fusion protein comprising a first protein sequence and a DNA binding domain in which the DNA binding domain is the same in each said first fusion protein, in which said host cells comprise at least one polynucleotide operably linked to a promoter driven by one or more DNA binding sites recognized by said DNA binding domain of said first fusion protein such that an interaction of a first fusion protein with a second fusion protein, said second fusion protein comprising a transcriptional regulatory domain, results in regulation of transcription of said at least one polynucleotide by said transcriptional regulatory domain, and in which said first population of first fusion proteins has a complexity of at least 10;

(b) negatively selecting to eliminate those host cells expressing said first population of first fusion proteins in which said regulation of transcription of said at least one polynucleotide occurs in the absence of a second fusion protein, said negatively selecting being performed by a method comprising incubating said host cells expressing said first population of first fusion proteins in an environment in which substantial death of said host cells occurs if said regulation of transcription occurs;

(c) after step (b), recombinantly co-expressing within said population of host cells a second population of second fusion proteins, each said second fusion protein comprising a second protein sequence and a transcriptional regulatory domain of a transcriptional regulator, in which the transcriptional regulatory domain is the same in each said second fusion protein, and in which said second population of second fusion proteins has a complexity of at least 10;

(d) detecting said regulation of transcription of said at least one polynucleotide, thereby detecting cells in which an interaction between a first protein and a second protein has occurred;

(e) amplifying DNA fragments encoding said second fusion protein or encoding a portion thereof comprising said second protein sequence from a plurality of host cells in which said regulation of transcription has been detected;

(f) probing a sample comprising said amplified DNA fragments with one or more recognition means, each recognition means causing recognition of a target nucleotide subsequence or a set of target nucleotide subsequences;

(g) generating one or more output signals from said sample probed by said recognition means, each output signal being produced from a nucleic acid in said sample by recognition of one or more target nucleotide subsequences in said nucleic acid by said recognition means and comprising a representation of (i) the identities of effective subsequences, each said effective subsequence being a nucleotide subsequence comprising a target nucleotide subsequence, or the identities of sets of effective subsequences, each said set having member effective subsequences each of which comprises a different target nucleotide subsequence from one of said sets of target nucleotide sequences, and (ii) the length between occurrences of effective subsequences in said nucleic acid; and

(h) searching a nucleotide sequence database to determine sequences that are predicted to produce or the absence of any sequences that are predicted to produce said one or more signals produced by said nucleic acid, said database comprising a plurality of known nucleotide sequences of nucleic acids that may be present in the sample, a sequence from said database being predicted to produce said one or more output signals when the sequence from said database has both (i) the same length between occurrences of effective subsequences as is represented by said one or more output signals, and (ii) the same effective subsequences as are represented by said one or more output signals, or effective subsequences that are members of the same sets of effective subsequences as are represented by said one or more output signals,

whereby said one or more nucleic acids in said sample are identified or classified.

5. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein--protein interactions, said method comprising:

(a) recombinantly expressing in a first population of yeast cells of a first mating type, a first population of first fusion proteins, each first fusion protein comprising a first protein sequence and a DNA binding domain, in which the DNA binding domain is the same in each said first fusion protein;

wherein said first population of yeast cells contains a first polynucleotide operably linked to a promoter driven by one or more DNA binding sites recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein, said second fusion protein comprising a transcriptional activation domain, results in increased transcription of said first polynucleotide, and in which said first population of first fusion proteins has a complexity of at least 100;

(b) negatively selecting to eliminate those yeast cells expressing said first population of first fusion proteins in which said increased transcription of said first polynucleotide occurs in the absence of said second fusion protein, said negatively selecting being carried out by a method comprising incubating said first population of yeast cells expressing said first population of first fusion proteins in an environment in which substantial death of said first population of yeast cells occurs if said increased transcription occurs;

(c) recombinantly expressing in a second population of yeast cells of a second mating type different from said first mating type, a second population of said second fusion proteins, each second fusion protein comprising a second protein sequence and an activation domain of a transcriptional activator, in which the activation domain is the same in each said second fusion protein, and in which said second population of second fusion proteins has a complexity of at least 100;

(d) mating said first population of yeast cells that has been negatively selected with said second population of yeast cells to form a population of diploid yeast cells, wherein said population of diploid yeast cells contains a second polynucleotide operably linked to a promoter driven by a DNA binding site recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein results in increased transcription of said second polynucleotide, in which the first and second polynucleotide can be the same or different;

(e) detecting said increased transcription of said first and/or second polynucleotide, thereby detecting colonies in which an interaction between a first protein and a second protein has occurred;

(f) amplifying DNA fragments encoding said second fusion protein or encoding a portion thereof comprising said second protein sequence from a plurality of yeast cells in which said increased transcription has been detected;

(g) probing a sample comprising said amplified DNA fragments with one or more recognition means, each recognition means causing recognition of a target nucleotide subsequence or a set of target nucleotide subsequences;

(h) generating one or more output signals from said sample probed by said recognition means, each output signal being produced from a nucleic acid in said sample by recognition of one or more target nucleotide subsequences in said nucleic acid by said recognition means and comprising a representation of (i) the identities of effective subsequences, each said effective subsequence being a nucleotide subsequence comprising a target nucleotide subsequence, or the identities of sets of effective subsequences, each said set having member effective subsequences each of which comprises a different target nucleotide subsequence from one of said sets of target nucleotide sequences, and (ii) the length between occurrences of effective subsequences in said nucleic acid; and

(i) searching a nucleotide sequence database to determine sequences that are predicted to produce or the absence of any sequences that are predicted to produce said one or more signals produced by said nucleic acid, said database comprising a plurality of known nucleotide sequences of nucleic acids that may be present in the sample, a sequence from said database being predicted to produce said one or more output signals when the sequence from said database has both (i) the same length between occurrences of effective subsequences as is represented by said one or more output signals, and (ii) the same effective subsequences as are represented by said one or more output signals, or effective subsequences that are members of the same sets of effective subsequences as are represented by said one or more output signals,

whereby said one or more nucleic acids in said sample are identified or classified.

6. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein--protein interactions, said method comprising:

(a) introducing into a first population of cells of Saccharomyces cerevisiae a first population of first plasmids, each said first plasmid encoding and capable of expressing in the first population of cells (i) TRP1, and (ii) a first population of first fusion proteins, each said first fusion protein comprising a GAL4 DNA binding domain and a first protein sequence, in which said first population of first fusion proteins has a complexity of at least 100, and in which said first population of cells (i) is of a first mating type selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional URA3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences under the control of a promoter containing GAL4 binding sites;

(b) introducing into a second population of cells of Saccharomyces cerevisiae a second population of second plasmids, each said second plasmid encoding and capable of expressing in the second population of cells (i) LEU2, and (ii) a second population of second fusion proteins, each said second fusion protein comprising a GAL4 transcriptional activation domain and a second protein sequence, in which said second population of second fusion proteins has a complexity of at least 100, and in which said second population of cells (i) is of a second matins type different from said first mating type and selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional HIS3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences under the control of a promoter containing GAL4 binding slites;

(c) after step (a), incubating said first population of cells in an environment lacking tryptophan and containing 5-fluoroorotic acid;

(d) pooling surviving cells from said first population after step (c);

(e) after step (b), incubating said second population of cells in an environment lacking leucine;

(f) pooling surviving cells from said second population after step (e);

(g) mating the pooled cells from said first population and the pooled cells from said second population by mixing the cells together, applying the cells to a solid medium and incubating the cells, to form diploid cells;

(h) incubating the diploid cells in an environment lacking uracil, histidine, tryptophan and leucine, to select diploid cells containing a said first plasmid and a said second plasmid and in which transcription of the URA3 and HIS3 coding sequences has been activated, thereby indicating that a first protein has interacted with a second protein within the diploid cell, thereby detecting cells in which one or more protein--protein interactions have occurred,

(i) amplifying DNA fragments encoding said second fusion protein or encoding a portion thereof comprising said second protein sequence from a plurality of cells which survive said incubating of step (h);

(j) probing a sample comprising said amplified DNA fragments with one or more recognition means, each recognition means causing recognition of a target nucleotide subsequence or a set of target nucleotide subsequences;

(k) generating one or more output signals from said sample probed by said recognition means, each output signal being produced from a nucleic acid in said sample by recognition of one or more target nucleotide subsequences in said nucleic acid by said recognition means and comprising a representation of (i) the identities of effective subsequences, each said effective subsequence being a nucleotide subsequence comprising a target nucleotide subsequence, or the identities of sets of effective subsequences, each said set having member effective subsequences each of which comprises a different target nucleotide subsequence from one of said sets of target nucleotide sequences, and (ii) the length between occurrences of effective subsequences in said nucleic acid; and

(l) searching a nucleotide sequence database to determine sequences that are predicted to produce or the absence of any sequences that are predicted to produce said one or more signals produced by said nucleic acid, said database comprising a plurality of known nucleotide sequences of nucleic acids that may be present in the sample, a sequence from said database being predicted to produce said one or more output signals when the sequence from said database has both (i) the same length between occurrences of effective subsequences as is represented by said one or more output signals, and (ii) the same effective subsequences as are represented by said one or more output signals, or effective subsequences that are members of the same sets of effective subsequences as are represented by said one or more output signals,

whereby said one or more nucleic acids in said sample are identified or classified.

7. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein--protein interactions, said method comprising:

(a) recombinantly expressing within a population of host cells a first population of first fusion proteins, each said first fusion protein comprising a first protein sequence and a DNA binding domain in which the DNA binding domain is the same in each said first fusion protein, in which said host cells comprise at least one polynucleotide operably linked to a promoter driven by one or more DNA binding sites recognized by said DNA binding domain of said first fusion protein such that an interaction of a first fusion protein with a second fusion protein, said second fusion protein comprising a transcriptional regulatory domain, results in regulation of transcription of said at least one polynucleotide by said transcriptional regulatory domain, and in which said first population of first fusion proteins has a complexity of at least 10;

(b) negatively selecting to eliminate those host cells expressing said first population of first fusion proteins in which said regulation of transcription of said at least one polynucleotide occurs in the absence of a second fusion protein, said negatively selecting being performed by a method comprising incubating said host cells expressing said first population of first fusion proteins in an environment in which substantial death of said host cells occurs if said regulation of transcription occurs;

(c) after step (b), recombinantly co-expressing within said population of host cells a second population of second fusion proteins, each said second fusion protein comprising a second protein sequence and a transcriptional regulatory domain of a transcriptional regulator, in which the transcriptional regulatory domain is the same in each said second fusion protein, and in which said second population of second fusion proteins has a complexity of at least 10;

(d) detecting said regulation of transcription of said at least one polynucleotide, thereby detecting cells in which an interaction between a first protein and a second protein has occurred;

(e) amplifying DNA fragments encoding said first fusion protein or encoding a portion thereof comprising said first protein sequence from a plurality of host cells in which said regulation of transcription has been detected;

(f) digesting a sample comprising said amplified DNA fragments with one or more restriction endonucleases, each said restriction endonuclease recognizing a subsequence recognition site and digesting DNA at said recognition site to produce fragments with 5'"'"' overhangs;

(g) contacting said fragments with shorter and longer oligodeoxynucleotides, in which each said shorter oligodeoxynucleotide comprises a first subsequence 5'"'"' to a second subsequence, said first subsequence being hybridizable to a 5'"'"' overhang and said second subsequence being hybridizable to a 3'"'"' terminal subsequence of a longer oligodeoxynucleotide;

(h) ligating said longer oligodeoxynucleotides to said 5'"'"' overhangs on said fragments to produce ligated DNA fragments;

(i) extending said ligated DNA fragments by synthesis with a DNA polymerase to produce blunt-ended double stranded DNA fragments;

(j) amplifying said blunt-ended double stranded DNA fragments by a method comprising contacting said blunt-ended double stranded DNA fragments with a DNA polymerase and primer oligodeoxynucleotides, each said primer oligodeoxynucleotide having a sequence comprising that of one of the longer oligodcoxynucleotides;

(f) determining the length of the amplified DNA fragments produced in step (e); and

(l) searching a DNA sequence database, said database comprising a plurality of known DNA sequences that may be present in the sample, for sequences predicted to produce one or more of said fragments of determined length, a sequence from said database being predicted to produce a fragment of determined length when the sequence from said database comprises recognition sites of said one or more restriction endonucleases spaced apart by the determined length,

whereby DNA molecules in said sample are identified, classified, or quantified.

8. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein--protein interactions, said method comprising:

(a) recombinantly expressing in a first population of yeast cells of a first mating type, a first population of first fusion proteins, each first fusion protein comprising a first protein sequence and a DNA binding domain, in which the DNA binding domain is the same in each said first fusion protein;

wherein said first population of yeast cells contains a first polynucleotide operably linked to a promoter driven by one or more DNA binding sites recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein, said second fusion protein comprising a transcriptional activation domain, results in increased transcription of said first polynucleotide, and in which said first population of first fusion proteins has a complexity of at least 100;

(b) negatively selecting to eliminate those yeast cells expressing said first population of first fusion proteins in which said increased transcription of said first polynucleotide occurs in the absence of said second fusion protein, said negatively selecting being carried out by a method comprising incubating said first population of yeast cells expressing said first population of first fusion proteins in an environment in which substantial death of said first population of yeast cells occurs if said increased transcription occurs;

(c) recombinantly expressing in a second population of yeast cells of a second mating type different from said first mating type, a second population of said second fusion proteins, each second fusion protein comprising a second protein sequence and an activation domain of a transcriptional activator, in which the activation domain is the same in each said second fusion protein, and in which said second population of second fusion proteins has a complexity of at least 100;

(d) mating said first population of yeast cells that has been negatively selected with said second population of yeast cells to form a population of diploid yeast cells, wherein said population of diploid yeast cells contains a second polynucleotide operably linked to a promoter driven by a DNA binding site recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein results in increased transcription of said second polynucleotide, in which the first and second polynucleotide can be the same or different;

(e) detecting said increased transcription of said first and/or second polynucleotide, thereby detecting colonies in which an interaction between a first protein and a second protein has occurred;

(f) amplifying DNA fragments encoding said first fusion protein or encoding a portion thereof comprising said first protein sequence from a plurality of yeast cells in which said increased transcription has been detected;

(g) digesting a sample comprising said amplified DNA fragments with one or more restriction endonucleases, each said restriction endonuclease recognizing a subsequence recognition site and digesting DNA at said recognition site to produce fragments with 5'"'"' overhangs;

(h) contacting said fragments with shorter and longer oligodeoxynucleotides, in which each said shorter oligodeoxynucleotide comprises a first subsequence 5'"'"' to a second subsequence, said first subsequence being hybridizable to a 5'"'"' overhang and said second subsequence being hybridizable to a 3'"'"' terminal subsequence of a longer oligodeoxynucleotide;

(i) ligating said longer oligodeoxynucleotides to said 5'"'"' overhangs on said fragments to produce ligated DNA fragments;

(j) extending said ligated DNA fragments by synthesis with a DNA polymerase to produce blunt-ended double stranded DNA fragments;

(k) amplifying said blunt-ended double stranded DNA fragments by a method comprising contacting said blunt-ended double stranded DNA fragments with a DNA polymerase and primer oligodeoxynucleotides, each said primer oligodeoxynucleotide having a sequence comprising that of one of the longer oligodeoxynucleotides;

(l) determining the length of the amplified DNA fragments produced in step (f); and

(m) searching a DNA sequence database, said database comprising a plurality of known DNA sequences that may be present in the sample, for sequences predicted to produce one or more of said fragments of determined length, a sequence from said database being predicted to produce a fragment of determined length when the sequence from said database comprises recognition sites of said one or more restriction endonucleases spaced apart by the determined length,

whereby DNA molecules in said sample are identified, classified, or quantified.

9. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein--protein interactions, said method comprising:

(a) introducing into a first population of cells of Saccharomyces cerevisiae a first population of first plasmids, each said first plasmid encoding and capable of expressing in the first population of cells (i) TRP1, and (ii) a first population of first fusion proteins, each said first fusion protein comprising a GAL4 DNA binding domain and a first protein sequence, in which said first population of first fusion proteins has a complexity of at least 100, and in which said first population of cells (i) is of a first mating type selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional URA3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences under the control of a promoter containing GAL4 binding sites;

(b) introducing into a second population of cells of Saccharomyces cerevisiae a second population of second plasmids, each said second plasmid encoding and capable of expressing in the second population of cells (i) LEU2, and (ii) a second population of second fusion proteins, each said second fusion protein comprising a GAL4 transcriptional activation domain and a second protein sequence, in which said second population of second fusion proteins has a complexity of at least 100, and in which said second population of cells (i) is of a second mating type different from said first mating type and selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional HIS3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences under the control of a promoter containing GAL4 binding sites;

(c) after step (a), incubating said first population of cells in an environment lacking tryptophan and containing 5-fluoroorotic acid;

(d) pooling surviving cells from said first population after step (c);

(e) after step (b), incubating said second population of cells in an environment lacking leucine;

(f) pooling surviving cells from said second population after step (e);

(g) mating the pooled cells from said first population and the pooled cells from said second population by mixing the cells together, applying the cells to a solid medium and incubating the cells, to form diploid cells;

(h) incubating the diploid cells in an environment lacking uracil, histidine, tryptophan and leucine, to select diploid cells containing a said first plasmid and a said second plasmid and in which transcription of the URA3 and HIS3 coding sequences has been activated, thereby indicating that a first protein has interacted with a second protein within the diploid cell, thereby detecting cells in which one or more protein--protein interactions have occurred;

(i) amplifying DNA fragments encoding said first fusion protein or encoding a portion thereof comprising said first protein sequence from a plurality of cells which survive said incubating of step (h);

(j) digesting a sample comprising said amplified DNA fragments with one or more restriction endonucleases, each said restriction endonuclease recognizing a subsequence recognition site and digesting DNA at said recognition site to produce fragments with 5'"'"' overhangs;

(k) contacting said fragments with shorter and longer oligodeoxynucleotides, in which each said shorter oligodeoxynucleotide comprises a first subsequence 5'"'"' to a second subsequence, said first subsequence being hybridizable to a 5'"'"' overhang and said second subsequence being hybridizable to a 3'"'"' terminal subsequence of a longer oligodeoxynucleotide;

(l) ligating said longer oligodeoxynucleotides to said 5'"'"' overhangs on said fragments to produce ligated DNA fragments;

(m) extending said ligated DNA fragments by synthesis with a DNA polymerase to produce blunt-ended double stranded DNA fragments;

(n) amplifying said blunt-ended double stranded DNA fragments by a method comprising contacting said blunt-ended double stranded DNA fragments with a DNA polymerase and primer oligodeoxynucleotides, each said primer oligodeoxynucleotide having a sequence comprising that of one of the longer oligodeoxynucleotides;

(o) determining the length of the amplified DNA fragments produced in step (i); and

(p) searching a DNA sequence database, said database comprising a plurality of known DNA sequences that may be present in the sample, for sequences predicted to produce one or more of said fragments of determined length, a sequence from said database being predicted to produce a fragment of determined length when the sequence from said database comprises recognition sites of said one or more restriction endonucleases spaced apart by the determined length,

whereby DNA molecules in said sample are identified, classified, or quantified.

10. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein--protein interactions, said method comprising:

(a) recombinantly expressing within a population of host cells a first population of first fusion proteins, each said first fusion protein comprising a first protein sequence and a DNA binding domain in which the DNA binding domain is the same in each said first fusion protein, in which said host cells comprise at least one polynucleotide operably linked to a promoter driven by one or more DNA binding sites recognized by said DNA binding domain of said first fusion protein such that an interaction of a first fusion protein with a second fusion protein, said second fusion protein comprising a transcriptional regulatory domain, results in regulation of transcription of said at least one polynucleotide by said transcriptional regulatory domain, and in which said first population of first fusion proteins has a complexity of at least 10;

(b) negatively selecting to eliminate those host cells expressing said first population of first fusion proteins in which said regulation of transcription of said at least one polynucleotide occurs in the absence of a second fusion protein, said negatively selecting being performed by a method comprising incubating said host cells expressing said first population of first fusion proteins in an environment in which substantial death of said host cells occurs if said regulation of transcription occurs;

(c) after step (b), recombinantly co-expressing within said population of host cells a second population of second fusion proteins, each said second fusion protein comprising a second protein sequence and a transcriptional regulatory domain of a transcriptional regulator, in which the transcriptional regulatory domain is the same in each said second fusion protein, and in which said second population of second fusion proteins has a complexity of at least 10;

(d) detecting said regulation of transcription of said at least one polynucleotide, thereby detecting cells in which an interaction between a first protein and a second protein has occurred;

(e) amplifying DNA fragments encoding said second fusion protein or encoding a portion thereof comprising said second protein sequence from a plurality of host cells in which said regulation of transcription has been detected;

(f) digesting a sample comprising said amplified DNA fragments with one or more restriction endonucleases, each said restriction endonuclease recognizing a subsequence recognition site and digesting DNA at said recognition site to produce fragments with 5'"'"' overhangs;

(g) contacting said fragments with shorter and longer oligodeoxynucleotides, in which each said shorter oligodeoxynucleotide comprises a first subsequence 5'"'"' to a second subsequence, said first subsequence being hybridizable to a 5'"'"' overhang and said second subsequence being hybridizable to a 3'"'"' terminal subsequence of a longer oligodeoxynucleotide;

(h) ligating said longer oligodeoxynucleotides to said 5'"'"' overhangs on said fragments to produce ligated DNA fragments;

(i) extending said ligated DNA fragments by synthesis with a DNA polymerase to produce blunt-ended double stranded DNA fragments;

(j) amplifying said blunt-ended double stranded DNA fragments by a method comprising contacting said blunt-ended double stranded DNA fragments with a DNA polymerase and primer oligodeoxynucleotides, each said primer oligodeoxynucleotide having a sequence comprising that of one of the longer oligodeoxynucleotides;

(k) determining the length of the amplified DNA fragments produced in step (e); and

(l) searching a DNA sequence database, said database comprising a plurality of known DNA sequences that may be present in the sample, for sequences predicted to produce one or more of said fragments of determined length, a sequence from said database being predicted to produce a fragment of determined length when the sequence from said database comprises recognition sites of said one or more restriction endonucleases spaced apart by the determined length,

whereby DNA molecules in said sample are identified, classified, or quantified.

11. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein--protein interactions, said method comprising:

(a) recombinantly expressing in a first population of yeast cells of a first mating type, a first population of first fusion proteins, each first fusion protein comprising a first protein sequence and a DNA binding domain, in which the DNA binding domain is the same in each said first fusion protein;

wherein said first population of yeast cells contains a first polynucleotide operably linked to a promoter driven by one or more DNA binding sites recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein, said second fusion protein comprising a transcriptional activation domain, results in increased transcription of said first polynucleotide, and in which said first population of first fusion proteins has a complexity of at least 100;

(b) negatively selecting to eliminate those yeast cells expressing said first population of first fusion proteins in which said increased transcription of said first polynucleotide occurs in the absence of said second fusion protein, said negatively selecting being carried out by a method comprising incubating said first population of yeast cells expressing said first population of first fusion proteins in an environment in which substantial death of said first population of yeast cells occurs if said increased transcription occurs;

(c) recombinantly expressing in a second population of yeast cells of a second mating type different from said first mating type, a second population of said second fusion proteins, each second fusion protein comprising a second protein sequence and an activation domain of a transcriptional activator, in which the activation domain is the same in each said second fusion protein, and in which said second population of second fusion proteins has a complexity of at least 100;

(d) mating said first population of yeast cells that has been negatively selected with said second population of yeast cells to form a population of diploid yeast cells, wherein said population of diploid yeast cells contains a second polynucleotide operably linked to a promoter driven by a DNA binding site recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein results in increased transcription of said second polynucleotide, in which the first and second polynucleotide can be the same or different;

(e) detecting said increased transcription of said first and/or second polynucleotide, thereby detecting colonies in which an interaction between a first protein and a second protein has occurred;

(f) amplifying DNA fragments encoding said second fusion protein or encoding a portion thereof comprising said second protein sequence from a plurality of yeast cells in which said increased transcription has been detected;

(g) digesting a sample comprising said amplified DNA fragments with one or more restriction endonucleases, each said restriction endonuclease recognizing a subsequence recognition site and digesting DNA at said recognition site to produce fragments with 5'"'"' overhangs;

(h) contacting said fragments with shorter and longer oligodeoxynucleotides, in which each said shorter oligodeoxynucleotide comprises a first subsequence 5'"'"' to a second subsequence, said first subsequence being hybridizable to a 5'"'"' overhang and said second subsequence being hybridizable to a 3'"'"' terminal subsequence of a longer oligodeoxynucleotide;

(i) ligating said longer oligodeoxynucleotides to said 5'"'"' overhangs on said fragments to produce ligated DNA fragments;

(j) extending said ligated DNA fragments by synthesis with a DNA polymerase to produce blunt-ended double stranded DNA fragments;

(k) amplifying said blunt-ended double stranded DNA fragments by a method comprising contacting said blunt-ended double stranded DNA fragments with a DNA polymerase and primer oligodeoxynucleotides, each said primer oligodeoxynucleotide having a sequence comprising that of one of the longer oligodeoxynucleotides;

(l) determining the length of the amplified DNA fragments produced in step (f); and

(m) searching a DNA sequence database, said database comprising a plurality of known DNA sequences that may be present in the sample, for sequences predicted to produce one or more of said fragments of determined length, a sequence from said database being predicted to produce a fragment of determined length when the sequence from said database comprises recognition sites of said one or more restriction endonucleases spaced apart by the determined length,

whereby DNA molecules in said sample are identified, classified, or quantified.

12. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein-protein interactions, said method comprising:

(a) introducing into a first population of cells of Saccharomyces cerevisiae a first population of first plasmids, each said first plasmid encoding and capable of expressing in the first population of cells (i) TRP1, and (ii) a first population of first fusion proteins, each said first fusion protein comprising a GAL4 DNA binding domain and a first protein sequence, in which said first population of first fusion proteins has a complexity of at least 100, and in which said first population of cells (i) is of a first matin2 type selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional URA3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences under the control of a promoter containing GAL4 binding sites;

(b) introducing into a second population of cells of Saccharomyces cerevisiae a second population of second plasmids, each said second plasmid encoding and capable of expressing in the second population of cells (i) LEU2, and (ii) a second population of second fusion proteins, each said second fusion protein comprising a GAL4 transcriptional activation domain and a second protein sequence, in which said second population of second fusion proteins has a complexity of at least 100, and in which said second population of cells (i) is of a second matins type different from said first mating type and selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional HIS3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences tinder the control of a promoter containing GAL4 binding sites;

(c) after step (a), incubating said first population of cells in an environment lacking tryptophan and containing 5-fluoroorotic acid;

(d) pooling surviving cells from said first population after step (c);

(e) after step (b), incubating said second population of cells in an environment lacking leucine;

(f) pooling surviving cells from said second population after step (e);

(g) mating the pooled cells from said first population and the pooled cells from said second population by mixing the cells together, applying the cells to a solid medium and incubating the cells, to form diploid cells;

(h) incubating the diploid cells in an environment lacking uracil, histidine, tryptophan and leucine, to select diploid cells containing a said first plasmid and a said second plasmid and in which transcription of the URA3 and HIS3 coding sequences has been activated, thereby indicating that a first protein has interacted with a second protein within the diploid cell, thereby detecting cells in which one or more protein--protein interactions have occurred;

(i) amplifying DNA fragments encoding said second fusion protein or encoding a portion thereof comprising said second protein sequence from a plurality of cells which survive said incubating of step (h);

(j) digesting a sample comprising said amplified DNA fragments with one or more restriction endonucleases, each said restriction endonuclease recognizing a subsequence recognition site and digesting DNA at said recognition site to produce fragments with 5'"'"' overhangs;

(k) contacting said fragments with shorter and longer oligodeoxynucleotides, in which each said shorter oligodeoxynucleotide comprises a first subsequence 5'"'"' to a second subsequence, said first subsequence being hybridizable to a 5'"'"' overhang and said second subsequence being hybridizable to a 3'"'"' terminal subsequence of a longer oligodeoxynucleotide;

(l) ligating said longer oligodeoxynucleotides to said 5'"'"' overhangs on said fragments to produce ligated DNA fragments;

(m) extending said ligated DNA fragments by synthesis with a DNA polymerase to produce blunt-ended double stranded DNA fragments;

(n) amplifying said blunt-ended double stranded DNA fragments by a method comprising contacting said blunt-ended double stranded DNA fragments with a DNA polymerase and primer oligodeoxynucleotides, each said primer oligodeoxynucleotide having a sequence comprising that of one of the longer oligodeoxynucleotides;

(o) determining the length of the amplified DNA fragments produced in step (i); and

(p) searching a DNA sequence database, said database comprising a plurality of known DNA sequences that may be present in the sample, for sequences predicted to produce one or more of said fragments of determined length, a sequence from said database being predicted to produce a fragment of determined length when the sequence from said database comprises recognition sites of said one or more restriction endonucleases spaced apart by the determined length,

whereby DNA molecules in said sample arc identified, classified, or quantified.

13. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein--protein interactions, said method comprising:

(a) recombinantly expressing in a first population of yeast cells of a first mating type, a first population of first fusion proteins, each first fusion protein comprising a first protein sequence and a DNA binding domain, in which the DNA binding domain is the same in each said first fusion protein;

wherein said first population of yeast cells contains a first polynucleotide operably linked to a promoter driven by one or more DNA binding sites recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein, said second fusion protein comprising a transcriptional activation domain, results in increased transcription of said first polynucleotide, and in which said first population of first fusion proteins has a complexity of at least 100;

(b) negatively selecting to eliminate those yeast cells expressing said first population of first fusion proteins in which said increased transcription of said first polynucleotide occurs in the absence of said second fusion protein, said negatively selecting being carried out by a method comprising incubating said first population of yeast cells expressing said first population of first fusion proteins in an environment in which substantial death of said first population of yeast cells occurs if said increased transcription occurs;

(c) recombinantly expressing in a second population of yeast cells of a second mating type different from said first mating type, a second population of said second fusion proteins, each second fusion protein comprising a second protein sequence and an activation domain of a transcriptional activator, in which the activation domain is the same in each said second fusion protein, and in which said second population of second fusion proteins has a complexity of at least 100;

(d) mating said first population of yeast cells that has been negatively selected with said second population of yeast cells to form a population of diploid yeast cells, wherein said population of diploid yeast cells contains a second polynucleotide operably linked to a promoter driven by a DNA binding site recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein results in increased transcription of said second polynucleotide, in which the first and second polynucleotide can be the same or different;

(e) detecting said increased transcription of said first and/or second polynucleotide, thereby detecting colonies in which an interaction between a first protein and a second protein has occurred;

(f) amplifying a DNA fragment encoding said first fusion protein or encoding a portion thereof comprising said first protein sequence, from a plurality of yeast cells in which said increased transcription is detected in step (e);

(g) amplifying a DNA fragment encoding said second fusion protein or encoding a portion thereof comprising said second protein sequence, from a plurality of yeast cells in which said increased transcription is detected in step (e);

(h) pooling the amplified DNA fragments resulting from steps (f) and (g);

(i) probing a sample comprising said pooled amplified DNA fragments with one or more recognition means, each recognition means causing recognition of a target nucleotide subsequence or a set of target nucleotide subsequences;

(j) generating one or more output signals from said sample probed by said recognition means, each output signal being produced from a nucleic acid in said sample by recognition of one or more target nucleotide subsequences in said nucleic acid by said recognition means and comprising a representation of (i) the identities of effective subsequences, each said effective subsequence being a nucleotide subsequence comprising a target nucleotide subsequence, or the identities of sets of effective subsequences, each said set having member effective subsequences each of which comprises a different target nucleotide subsequence from one of said sets of target nucleotide sequences, and (ii) the length between occurrences of effective subsequences in said nucleic acid; and

(k) searching a nucleotide sequence database to determine sequences that are predicted to produce or the absence of any sequences that are predicted to produce said one or more signals produced by said nucleic acid, said database comprising a plurality of known nucleotide sequences of nucleic acids that may be present in the sample, a sequence from said database being predicted to produce said one or more output signals when the sequence from said database has both (i) the same length between occurrences of effective subsequences as is represented by said one or more output signals, and (ii) the same effective subsequences as are represented by said one or more output signals, or effective subsequences that are members of the same sets of effective subsequences as are represented by said one or more output signals.

14. A method for identifying, classifying, or quantifying one or more nucleic acids encoding one or more proteins of one or more protein--protein interactions, said method comprising:

(a) introducing into a first population of cells of Saccharomyces cerevisiae a first population of first plasmids, each said first plasmid encoding and capable of expressing in the first population of cells (i) TRP1, and (ii) a first population of first fusion proteins, each said first fusion protein comprising a GAL4 DNA binding domain and a first protein sequence, in which said first population of first fusion proteins has a complexity of at least 100, and in which said first population of cells (i) is of a first mating type selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional URA3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences under the control of a promoter containing GAL4 binding sites;

(b) introducing into a second population of cells of Saccharomyces cerevisiae a second population of second plasmids, each said second plasmid encoding and capable of expressing in the second population of cells (i) LEU2, and (ii) a second population of second fusion proteins, each said second fusion protein comprising a GAL4 transcriptional activation domain and a second protein sequence, in which said second population of second fusion proteins has a complexity of at least 100, and in which said second population of cells (i) is of a second mating type different from said first mating type and selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional HIS3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences under the control of a promoter containing GAL4 binding sites;

(c) after step (a), incubating said first population of cells in an environment lacking tryptophan and containing 5-fluoroorotic acid;

(d) pooling surviving cells from said first population after step (c);

(e) after step (b), incubating said second population of cells in an environment lacking leucine;

(f) pooling surviving cells from said second population after step (e);

(g) mating the pooled cells from said first population and the pooled cells from said second population by mixing the cells together, applying the cells to a solid medium and incubating the cells, to form diploid cells;

(h) incubating the diploid cells in an environment lacking uracil histidine, tryptophan and leucine, to select diploid cells containing a said first plasmid and a said second plasmid and in which transcription of the URA3 and HIS3 coding sequences has been activated, thereby indicating that a first protein has interacted with a second protein within the diploid cell, thereby detecting cells in which one or more protein--protein interactions have occurred;

(i) amplifying a DNA fragment encoding said first fusion protein or encoding a portion thereof comprising said first protein sequence, from a cell which survives said incubating step (h) and is thereby selected;

(j) amplifying a DNA fragment encoding said second fusion protein or encoding a portion thereof comprising said second protein sequence, from a cell which survives said incubating step (h) and is thereby selected;

(k) pooling the amplified DNA fragments resulting from steps (i) and (j);

(l) probing a sample comprising said pooled amplified DNA fragments with one or more recognition means, each recognition means causing recognition of a target nucleotide subsequence or a set of target nucleotide subsequences;

(m) generating one or more output signals from said sample probed by said recognition means, each output signal being produced from a nucleic acid in said sample by recognition of one or more target nucleotide subsequences in said nucleic acid by said recognition means and comprising a representation of (i) the identities of effective subsequences, each said effective subsequence being a nucleotide subsequence comprising a target nucleotide subsequence, or the identities of sets of effective subsequences, each said set having member effective subsequences each of which comprises a different target nucleotide subsequence from one of said sets of target nucleotide sequences, and (ii) the length between occurrences of effective subsequences in said nucleic acid; and

(n) searching a nucleotide sequence database to determine sequences that are predicted to produce or the absence of any sequences that are predicted to produce said one or more signals produced by said nucleic acid, said database comprising a plurality of known nucleotide sequences of nucleic acids that may be present in the sample, a sequence from said database being predicted to produce said one or more output signals when the sequence from said database has both (i) the same length between occurrences of effective subsequences as is represented by said one or more output signals, and (ii) the same effective subsequences as are represented by said one or more output signals, or effective subsequences that are members of the same sets of effective subsequences as are represented by said one or more output signals.

15. A method of determining the sizes of nucleic acids encoding an interacting pair of proteins from among a plurality of yeast cell colonies, said method comprising:

(a) recombinantly expressing in a first population of yeast cells of a first mating type, a first population of first fusion proteins, each first fusion protein comprising a first protein sequence and a DNA binding domain, in which the DNA binding domain is the same in each said first fusion protein;

wherein said first population of yeast cells contains a first polynucleotide operably linked to a promoter driven by one or more DNA binding sites recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein, said second fusion protein comprising a transcriptional activation domain, results in increased transcription of said first polynucleotide, and in which said first population of first fusion proteins has a complexity of at least 100;

(b) negatively selecting to eliminate those yeast cells expressing said first population of first fusion proteins in which said increased transcription of said first polynucleotide occurs in the absence of said second fusion protein, said negatively selecting being carried out by a method comprising incubating said first population of yeast cells expressing said first population of first fusion proteins in an environment in which substantial death of said first population of yeast cells occurs if said increased transcription occurs;

(c) recombinantly expressing in a second population of yeast cells of a second mating type different from said first mating type, a second population of said second fusion proteins, each second fusion protein comprising a second protein sequence and an activation domain of a transcriptional activator, in which the activation domain is the same in each said second fusion protein, and in which said second population of second fusion proteins has a complexity of at least 100;

(d) mating said first population of yeast cells that has been negatively selected with said second population of yeast cells to form a population of diploid yeast cells, wherein said population of diploid yeast cells contains a second polynucleotide operably linked to a promoter driven by a DNA binding site recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein results in increased transcription of said second polynucleotide, in which the first and second polynucleotide can be the same or different;

(e) detecting said increased transcription of said first and/or second polynucleotide, thereby detecting interactant colonies in which an interaction between a first protein and a second protein has occurred;

(f) coding each interactant colony as one point of a multidimensional array, in which said array has one axis for each dimension of the array, and in which each said interactant colony is identified by a particular position along each of said axes;

(g) forming a plurality of pools by pooling aliquots of said coded interactant colonies, in which each of said pools corresponds to a particular position along a particular axis and comprises aliquots from all coded interactant colonies having said same particular position along said same axis, and in which said plurality of pools comprises pools from each fixed position along each axis;

(h) amplifying from a first aliquot of each pool a plurality of first nucleic acids, said first nucleic acids comprising a sequence encoding said first fusion protein or a portion thereof comprising said first protein sequence;

(i) amplifying from a second aliquot of each pool a plurality of second nucleic acids, said second nucleic acids comprising a sequence encoding said second fusion protein or a portion thereof comprising said second protein sequence;

(j) subjecting said first nucleic acids from each pool to size separation, thereby determining the sizes of said first nucleic acids in each pool;

(k) subjecting said second nucleic acids from each pool to size separation, thereby determining the sizes of said second nucleic acids in each pool;

(l) determining which sizes of said nucleic acids encoding said first proteins are present in an interactant colony coded by particular positions along each of said axes, in which sizes of said nucleic acids present in said interactant colony are determined to be those sizes that are determined in step (j) to be present in all of said pools corresponding to each of said particular positions of said interactant colony along each of said axes; and

(m) determining which sizes of said nucleic acids encoding said second proteins are present in an interactant colony coded by particular positions along each of said axes, in which sizes of said nucleic acids present in said interactant colony are determined to be those sizes that are determined in step (k) to be present in all of said pools corresponding to each of said particular positions of said interactant colony along each of said axes,

whereby the sizes of nucleic acids encoding an interacting pair of proteins in each interactant colony are determined as said sizes of nucleic acids encoding said first and said second proteins which are determined to be present in said interactant colony.

17. The method according to claim 15 or 16 in which said amplifying is by use of polymerase chain reaction.

18. The method according to claim 15 which further comprises determining the nucleotide sequence of at least one first nucleic acid or second nucleic acid.

16. A method of determining the sizes of DNA molecules encoding an interacting pair of proteins from among a plurality of yeast cell colonies, said method comprising:

(a) introducing into a first population of cells of Saccharomyces cerevisiae a first population of first plasmids, each said first plasmid encoding and capable of expressing in the first population of cells (i) TRP1, and (ii) a first population of first fusion proteins, each said first fusion protein comprising a GAL4 DNA binding domain and a first protein sequence, in which said first population of first fusion proteins has a complexity of at least 100, and in which said first population of cells (i) is of a first mating type selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional URA3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences under the control of a promoter containing GAL4 binding sites;

(b) introducing into a second population of cells of Saccharomyces cerevisiae a second population of second plasmids, each said second plasmid encoding and capable of expressing in the second population of cells (i) LEU2, and (ii) a second population of second fusion proteins, each said second fusion protein comprising a GAL4 transcriptional activation domain and a second protein sequence, in which said second population of second fusion proteins has a complexity of at least 100, and in which said second population of cells (i) is of a second mating type different from said first mating type and selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional HIS3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences under the control of a promoter containing GAL4 binding sites;

(c) after step (a), incubating said first population of cells in an environment lacking tryptophan and containing 5-fluoroorotic acid;

(d) pooling surviving cells from said first population after step (c);

(e) after step (b), incubating said second population of cells in an environment lacking leucine;

(f) pooling surviving cells from said second population after step (e);

(g) mating the pooled cells from said first population and the pooled cells from said second population by mixing the cells together, applying the cells to a solid medium and incubating the cells, to form diploid cells;

(h) incubating the diploid cells in an environment lacking uracil, histidine, tryptophan and leucine, to select diploid cells containing a said first plasmid and a said second plasmid and in which transcription of the URA3 and HIS3 coding sequences has been activated, thereby indicating that a first protein has interacted with a second protein within the diploid cell, thereby detecting interactant colonies in which one or more protein--protein interactions have occurred;

(i) coding each interactant colony as one point of a multidimensional array, in which said array has one axis for each dimension of the array, and in which each said interactant colony is identified by a particular position along each of said axes;

(j) forming a plurality of pools by pooling aliquots of said coded interactant colonies, in which each of said pools corresponds to a particular position along a particular axis and comprises aliquots from all coded interactant colonies having said same particular position along said same axis, and in which said plurality of pools comprises pools from each fixed position along each axis;

(k) amplifying from a first aliquot of each pool a plurality of first DNA molecules, said first DNA molecules comprising a sequence encoding said first fusion protein or a portion thereof comprising said first protein sequence;

(l) amplifying from a second aliquot of each pool a plurality of second DNA molecules, said second DNA molecules comprising a sequence encoding said second fusion protein or a portion thereof comprising said second protein sequence;

(m) subjecting said first DNA molecules from each pool to size separation, thereby determining the sizes of said first DNA molecules from each pool;

(n) subjecting said second DNA molecules from each pool to size separation, thereby determining the sizes of said second DNA molecules from each pool;

(o) determining which sizes of said DNA molecules encoding said first proteins are present in an interactant colony coded by particular positions along each of said axes, in which sizes of said DNA molecules present in said interactant colony are determined to be those sizes that are determined in step (m) to be present in all of said pools corresponding to each of said particular positions of said interactant colony along each of said axes; and

(p) determining which sizes of said DNA molecules encoding said second proteins are present in an interactant colony coded by particular positions along each of said axes, in which sizes of said DNA molecules present in said interactant colony are determined to be those sizes determined in step (n) to be present in all of said pools corresponding to each of said particular positions of said interactant colony along each of said axes,

whereby the sizes of DNA molecules encoding an interacting pair of proteins in each interactant colony are determined as said sizes of DNA molecules encoding said first and said second proteins which are determined to be present in said interactant colony.

19. The method according to claim 16 which further comprises determining the nucleotide sequence of at least one first DNA molecule or second DNA molecule.

20. A method for determining the identities of nucleic acids encoding an interacting pair of proteins in each colony of a plurality of yeast cell colonies, said method comprising:

(a) recombinantly expressing in a first population of yeast cells of a first mating type, a first population of first fusion proteins, each first fusion protein comprising a first protein sequence and a DNA binding domain, in which the DNA binding domain is the same in each said first fusion protein;

wherein said first population of yeast cells contains a first polynucleotide operably linked to a promoter driven by one or more DNA binding sites recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein, said second fusion protein comprising a transcriptional activation domain, results in increased transcription of said first polynucleotide, and in which said first population of first fusion proteins has a complexity of at least 100;

(b) negatively selecting to eliminate those yeast cells expressing said first population of first fusion proteins in which said increased transcription of said first polynucleotide occurs in the absence of said second fusion protein, said negatively selecting being carried out by a method comprising incubating said first population of yeast cells expressing said first population of first fusion proteins in an environment in which substantial death of said first population of yeast cells occurs if said increased transcription occurs;

(c) recombinantly expressing in a second population of yeast cells of a second mating type different from said first mating type, a second population of said second fusion proteins, each second fusion protein comprising a second protein sequence and an activation domain of a transcriptional activator, in which the activation domain is the same in each said second fusion protein, and in which said second population of second fusion proteins has a complexity of at least 100;

(d) mating said first population of yeast cells that has been negatively selected with said second population of yeast cells to form a population of diploid yeast cells, wherein said population of diploid yeast cells contains a second polynucleotide operably linked to a promoter driven by a DNA binding site recognized by said DNA binding domain such that an interaction of a first fusion protein with a second fusion protein results in increased transcription of said second polynucleotide, in which the first and second polynucleotide can be the same or different;

(e) detecting said increased transcription of said first and/or second polynucleotide, thereby detecting interactant colonies in which an interaction between a first protein and a second protein has occurred;

(f) coding each interactant colony as one point in a multidimensional array, in which said array has one axis for each dimension of the array, and in which each said interactant colony is identified by a particular position along each of said axes;

(g) forming a plurality of pools by pooling aliquots of said coded interactant colonies, in which each of said pools corresponds to a particular position along a particular axis and comprises aliquots from all coded interactant colonies having said same particular position along said same axis, and in which said plurality of pools comprises pools from each fixed position along each axis;

(h) identifying in each of said pools a separate plurality of first nucleic acids, by amplifying from an aliquot of each of said pools a plurality of first nucleic acids, said first nucleic acids comprising sequences encoding said first proteins, and by subjecting a sample of said first nucleic acids to a method for identifying or classifying nucleic acids in a sample of nucleic acids;

(i) identifying in each of said pools a separate plurality of second nucleic acids, by amplifying from an aliquot of each of said pools a plurality of second nucleic acids, said second nucleic acids comprising sequences encoding said second proteins, and by subjecting a sample of said second nucleic acids to a method for identifying or classifying nucleic acids in a sample of nucleic acids;

(j) determining which of said first nucleic acids are present in each interactant colony, in which a first nucleic acid is determined to be present in an interactant colony coded by particular positions along each of said axes if that first nucleic acid is identified in all of said pools corresponding to each of said particular positions along each of said axes; and

(k) determining which of said second nucleic acids are present in each interactant colony, in which a second nucleic acid is determined to be present in an interactant colony coded by particular positions along each of said axes if that second nucleic acid is identified in all of said pools corresponding to each of said particular positions along each of said axes;

whereby the identities of nucleic acids encoding an interacting pair of proteins in each interactant colony are determined as said first and said second nucleic acids which are determined to be present in said interactant colony.

22. The method according to claim 20 or 21 wherein said method for identifying or classifying nucleic acids in said sample of nucleic acids comprises the steps of:

(a) probing said sample with one or more recognition means, each recognition means causing recognition of a target nucleotide subsequence or a set of target nucleotide subsequences;

(b) generating one or more output signals from said sample probed by said recognition means, each output signal being produced from a nucleic acid in said sample by recognition of one or more target nucleotide subsequences in said nucleic acid by said recognition means and comprising a representation of (i) the identities of effective subsequences, each said effective subsequence being a nucleotide subsequence comprising at least one target subsequence, or the identities of sets of effective subsequences, each said set of effective subsequences having member effective subsequences each of which comprises at least one different target subsequence from one of said sets of target sequences, and (ii) the length between occurrences of effective subsequences in said nucleic acid; and

(c) searching a nucleotide sequence database to determine sequences that are predicted to produce or the absence of any sequences that are predicted to produce said one or more output signals produced by said nucleic acids, said database comprising a plurality of known nucleotide sequences of nucleic acids that may be present in the sample, a sequence from said database being predicted to produce said one or more output signals when the sequence from said database has both (i) the same length between occurrences of effective subsequences as is represented by said one or more output signals, and (ii) the same effective subsequences as are represented by said one or more output signals, or effective subsequences that are members of the same sets of effective subsequences as are represented by said one or more output signals,

whereby said one or more nucleic acids in said sample are identified in said nucleotide database or classified by said signals.

23. The method according to claim 20 or 21 wherein said method for identifying or classifying nucleic acids in said sample of nucleic acids comprises the steps of:

(a) digesting said sample with one or more restriction endonucleases, each said restriction endonuclease recognizing a subsequence recognition site and digesting nucleic acids at said recognition site to produce fragments with 5'"'"' overhangs;

(b) contacting said fragments with shorter and longer oligodeoxynucleotides, wherein each said shorter oligodeoxynucleotide comprises a first subsequence 5'"'"' to a second subsequence, said first subsequence being hybridizable to a 5'"'"' overhang and said second subsequence being hybridizable to a 3'"'"' terminal subsequence of a longer oligodeoxynucleotide;

(c) ligating said longer oligodeoxynucleotides to said 5'"'"' overhangs on said fragments to produce ligated nucleic acid fragments;

(d) extending said ligated nucleic acid fragments by synthesis with a DNA polymerase to produce blunt-ended double stranded DNA fragments;

(e) amplifying said blunt-ended double stranded nucleic acid fragments by a method comprising contacting said blunt-ended double stranded nucleic acid fragments with a DNA polymerase and primer oligodeoxynucleotides, each said primer oligodeoxynucleotide having a sequence comprising that of one of the longer oligodeoxynucleotides;

(f) determining the length of the amplified nucleic acid fragments produced in step (e); and

(g) searching a nucleotide sequence database, said database comprising a plurality of known nucleic acid sequences that may be present in the sample, for sequences predicted to produce one or more of said fragments of determined length, a sequence from said database being predicted to produce a fragment of determined length when the sequence from said database comprises recognition sites of said one or more restriction endonucleases spaced apart by the determined length,

whereby nucleic acids in said sample are in said nucleotide database or classified by said signals.

21. A method for determining the identities of DNA molecules encoding an interacting pair of proteins in each colony of a plurality of yeast cell colonies, said method comprising:

(a) introducing into a first population of cells of Saccharomyces cerevisiae a first population of first plasmids, each said first plasmid encoding and capable of expressing in the first population of cells (i) TRP1, and (ii) a first population of first fusion proteins, each said first fusion protein comprising a GAL4 DNA binding domain and a first protein sequence, in which said first population of first fusion proteins has a complexity of at least 100, and in which said first population of cells (i) is of a first mating type selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional URA3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences under the control of a promoter containing GAL4 binding sites;

(b) introducing into a second population of cells of Saccharomyces cerevisiae a second population of second plasmids, each said second plasmid encoding and capable of expressing in the second population of cells (i) LEU2, and (ii) a second population of second fusion proteins, each said second fusion protein comprising a GAL4 transcriptional activation domain and a second protein sequence, in which said second population of second fusion proteins has a complexity of at least 100, and in which said second population of cells (i) is of a second mating type different from said first mating type and selected from the group consisting of a and α

, (ii) is mutant in endogenous URA3 and HIS3, (iii) contains functional HIS3 coding sequences under the control of a promoter containing GAL4 binding sites, and (iv) contains functional lacZ coding sequences under the control of a promoter containing GAL4 binding sites;

(c) after step (a), incubating said first population of cells in an environment lacking tryptophan and containing 5-fluoroorotic acid;

(d) pooling surviving cells from said first population after step (c);

(e) after step (b), incubating said second population of cells in an environment lacking leucine;

(f) pooling surviving cells from said second population after step (e);

(g) mating the pooled cells from said first population and the pooled cells from said second population by mixing the cells together, applying the cells to a solid medium and incubating the cells, to form diploid cells;

(h) incubating the diploid cells in an environment lacking uracil, histidine, tryptophan and leucine, to select diploid cells containing a said first plasmid and a said second plasmid and in which transcription of the URA3 and HIS3 coding sequences has been activated, thereby indicating that a first protein has interacted with a second protein within the diploid cell, thereby detecting interactant colonies in which one or more protein--protein interactions have occurred;

(i) coding each interactant colony as one point in a multidimensional array, in which said array has one axis for each dimension of the array, and in which each said interactant colony is identified by a particular position along each of said axes;

(j) forming a plurality of pools by pooling aliquots of said coded interactant colonies, in which each of said pools corresponds to a particular position along a particular axis and comprises aliquots from all coded interactant colonies having said same particular position along said same axis, and in which said plurality of pools comprises pools from each fixed position along each axis;

(k) identifying in each of said pools a separate plurality of first DNA molecules, by amplifying from an aliquot of each of said pools a plurality of first DNA molecules, said first DNA molecules comprising sequences encoding said first proteins, and by subjecting a sample of said first DNA molecules to a method for identifying or classifying nucleic acids in a sample of nucleic acids;

(l) identifying in each of said pools a separate plurality of second DNA molecules, by amplifying from an aliquot of each of said pools a plurality of second DNA molecules, said second DNA molecules comprising sequences encoding said second protein, and by subjecting a sample of said second DNA molecules to a method for identifying or classifying nucleic acids in a sample of nucleic acids;

(m) determining which of said first DNA molecules are present in each interactant colony, in which a first DNA molecule is determined to be present in an interactant colony coded by particular positions along each of said axes if that first DNA molecule is identified in all of said pools corresponding to each of said particular positions along each of said axes; and

(n) determining which of said second DNA molecules are present in each interactant colony, in which a second DNA molecule is determined to be present in an interactant colony coded by particular positions along each of the axes if that second DNA molecule is identified in all of said pools corresponding to each of said particular positions along each of said axes;

whereby the identities of DNA molecules encoding an interacting pair of proteins in each interactant colony are determined as said first and said second DNA molecules which are determined to be present in said interactant colony.