Method and apparatus for identifying, classifying, or quantifying DNA sequences in a sample without sequencing

• US 5,871,697 A
• Filed: 10/24/1995
• Issued: 02/16/1999
• Est. Priority Date: 10/24/1995
• Status: Expired due to Fees

• Current Assignee: CuraGen Corporation (Celldex Therapeutics Incorporated)
• Original Assignee: CuraGen Corporation (Celldex Therapeutics Incorporated)
• Inventors: Simpson, John W., Deem, Michael W., Rothberg, Jonathan Marc
• Primary Examiner(s): JONES, WILLIAM G
• Assistant Examiner(s): Rees, Dianne
• Application Number:
  US08/547,214
• Time in Patent Office: 1,211 Days
• Field of Search: 435/6, 435/5, 435/91.2, 536/23.1, 536/24.3, 536/24.33, 364/497, 364/499, 422/68.1
• US Class Current: 422/68.1
• CPC Class Codes: C12N 15/10 Processes for the isolation, preparation or purification of DNA or RNA chemical preparation of DNA or RNA C07H21/00; preparation of non-structural polynucleotides from microorganisms or with enzymes C12P19/34
• CPC Class Codes: C12Q 1/68 involving nucleic acids
• CPC Class Codes: C12Q 1/6809 Methods for determination or identification of nucleic acids involving differential detection
• CPC Class Codes: C12Q 1/6855 Ligating adaptors
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

This invention provides methods by which biologically derived DNA sequences in a mixed sample or in an arrayed single sequence clone can be determined and classified without sequencing. The methods make use of information on the presence of carefully chosen target subsequences, typically of length from 4 to 8 base pairs, and preferably the length between target subsequences in a sample DNA sequence together with DNA sequence databases containing lists of sequences likely to be present in the sample to determine a sample sequence. The preferred method uses restriction endonucleases to recognize target subsequences and cut the sample sequence. Then carefully chosen recognition moieties are ligated to the cut fragments, the fragments amplified, and the experimental observation made. Polymerase chain reaction (PCR) is the preferred method of amplification. Another embodiment of the invention uses information on the presence or absence of carefully chosen target subsequences in a single sequence clone together with DNA sequence databases to determine the clone sequence. Computer implemented methods are provided to analyze the experimental results and to determine the sample sequences in question and to carefully choose target subsequences in order that experiments yield a maximum amount of information.

Claims

1. A method for identifying, classifying, or quantifying one or more nucleic acids in a sample comprising a plurality of nucleic acids having different nucleotide sequences, said method comprising:

(a) probing said sample with one or more recognition means, each recognition means recognizing a different target nucleotide subsequence or a different 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 length between occurrences of target nucleotide subsequences in said nucleic acid, and (ii) the identities of said target nucleotide subsequences in said nucleic acid or the identities of said sets of target nucleotide subsequences among which are included the target nucleotide 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 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 target nucleotide subsequences as is represented by said one or more output signals, and (ii) the same target nucleotide subsequences as are represented by said one or more output signals, or target nucleotide subsequences that are members of the same sets of target nucleotide subsequences represented by said one or more output signals, whereby said one or more nucleic acids in said sample are identified, classified, or quantified.

2. The method of claim 1 wherein each recognition means recognizes one target nucleotide subsequence, and wherein a sequence from said database is predicted to produce a particular output signal when the sequence from said database has both the same length between occurrences of target nucleotide subsequences as is represented by the output signal and the same target nucleotide subsequences as represented by the particular output signal.

3. The method of claim 1 wherein each recognition means recognizes a set of target nucleotide subsequences, and wherein a sequence from said database is predicted to produce a particular output signal when the sequence from said database has both the same length between occurrences of target nucleotide subsequences as is represented by the particular output signal, and the target nucleotide subsequences are members of the sets of target nucleotide subsequences represented by the particular output signal.

4. The method of claim 1 further comprising dividing said sample of nucleic acids into a plurality of portions and performing the steps of claim 1 individually on a plurality of said portions, wherein a different one or more recognition means are used with each portion.

5. The method of claim 1 wherein the quantitative abundances of nucleic acids in said sample are determined from the quantitative levels of the output signals produced by said nucleic acids.

6. The method of claim 1 wherein said plurality of nucleic acids are DNA.

7. The method of claim 6 wherein the DNA is cDNA.

8. The method of claim 7 wherein the cDNA is prepared from a plant, a single celled animal, a multicellular animal, a bacterium, a virus, a fungus, or a yeast.

9. The method of claim 8 wherein said database comprises substantially all the known expressed sequences of said plant, single celled animal, multicellular animal, bacterium, virus, fungus, or yeast.

10. The method of claim 7 wherein the cDNA is of total cellular RNA or total cellular poly(A) RNA.

11. The method of claim 6 wherein the recognition means are one or more restriction endonucleases whose recognition sites are said target nucleotide subsequences, and wherein

the step of probing comprises digesting said sample with said one or more restriction endonucleases into fragments and ligating double stranded adapter DNA molecules to said fragments to produce ligated fragments, each said adapter DNA molecule comprising (i) a shorter stand having no 5'"'"' terminal phosphates and consisting of a first and second portion, said first portion at the 5'"'"' end of the shorter strand and being complementary to the overhang produced by one of said restriction endonucleases, and (ii) a longer strand having a 3'"'"' end subsequence complementary to said second portion of the shorter strand;

and wherein

the step of generating further comprises melting the shorter strand from the ligated fragments, contacting the ligated fragments with a DNA polymerase, extending the ligated fragments by synthesis with the DNA polymerase to produce blunt-ended double stranded DNA fragments, and amplifying the blunt-ended fragments by a method comprising contacting the blunt-ended fragments with the DNA polymerase and primer oligodeoxynucleotides, said primer oligodeoxynucleotides comprising a hybridizable portion of the sequence of the longer strand of the adapter nucleic acid molecule, and said contacting being at a temperature not greater than the melting temperature of the primer oligodeoxynucleotide from a strand of the blunt-ended fragments complementary to the primer oligodeoxynucleotide and not less than the melting temperature of the shorter strand of the adapter nucleic acid molecule from the blunt-ended fragments.

12. The method of claim 6 wherein the recognition means are one or more restriction endonucleases whose recognition sites are said target nucleotide subsequences, and wherein the step of probing further comprises digesting the sample into fragments with said one or more restriction endonucleases.

13. The method of claim 12 further comprising:

(a) identifying a fragment of a nucleic acid in the sample which generates said one or more output signals; and

(b) recovering said fragment.

14. The method of claim 13 wherein the output signals generated by said recovered fragment are not predicted to be Produced by a sequence in said nucleotide sequence database.

15. The method of claim 13 which further comprises using at least a hybridizable portion of said recovered fragment as a hybridization probe to bind to a nucleic acid.

16. The method of claim 12 wherein the step of generating further comprises after said digesting:

removing from the sample both nucleic acids which have not been digested and nucleic acid fragments resulting from digestion at only a single terminus of the fragments.

17. The method of claim 16 wherein prior to digesting, the nucleic acids in the sample are each bound at one terminus to a biotin molecule, and said removing is carried out by a method which comprises contacting the nucleic acids in the sample with streptavidin or avidin affixed to a solid support.

18. The method of claim 16 wherein prior to digesting, the nucleic acids in the sample are each bound at one terminus to a hapten molecule, and said removing is carried out by a method which comprises contacting the nucleic acids in the sample with an anti-hapten antibody affixed to a solid support.

19. The method of claim 12 wherein said digesting with said one or more restriction endonucleases leaves single-stranded nucleotide overhangs on the digested ends.

20. The method of claim 19 wherein the step of probing further comprises hybridizing double-stranded adapter nucleic acids with the digested sample fragments, each said double-stranded adapter nucleic acid having an end complementary to said overhang generated by a particular one of the one or more restriction endonucleases, and ligating with a ligase a strand of said double-stranded adapter nucleic acids to the 5'"'"' end of a strand of the digested sample fragments to form ligated nucleic acid fragments.

21. The method of claim 20 wherein said digesting with said one or more restriction endonucleases and said ligating are carried out in the same reaction medium.

22. The method of claim 21 wherein said digesting and said ligating comprises incubating said reaction medium at a first temperature and then at a second temperature, wherein said one or more restriction endonucleases are more active at the first temperature than the second temperature and said ligase is more active at the second temperature than the first temperature.

23. The method of claim 22 wherein said incubating at said first temperature and said incubating at said second temperature are performed repetitively.

24. The method of claim 20 wherein the step of probing further comprises prior to said digesting:

removing terminal phosphates from DNA in said sample by incubation with an alkaline phosphatase.

25. The method of claim 24 wherein said alkaline phosphatase is heat labile and is heat inactivated prior to said digesting.

26. The method of claim 20 wherein said generating step comprises amplifying the ligated nucleic acid fragments.

27. The method of claim 26 wherein said amplifying is carried out by use of a nucleic acid polymerase and primer nucleic acid strands, said primer nucleic acid strands comprising a hybridizable portion of the sequence of said strands ligated to said sample fragments.

28. The method of claim 27 wherein the primer nucleic acid strands have a G+C content of between 40% and 60%.

29. The method of claim 27 wherein each said double-stranded adapter nucleic acid comprises a shorter strand hybridized to a longer strand, wherein the longer strand is said strand of said double-stranded adapter nucleic acid that becomes ligated to the digested sample fragments, wherein each said shorter strand is complementary both to one of said single-stranded nucleotide overhangs and to one of said longer strands, and said generating step comprises prior to said amplifying step the melting of the shorter strand from the ligated fragments, contacting the ligated fragments with a DNA polymerase, extending the ligated fragments by synthesis with the DNA polymerase to produce blunt-ended double stranded DNA fragments, and wherein the primer nucleic acid strands comprise a hybridizable portion of the sequence of said longer strands.

30. The method of claim 27 wherein each said double-stranded adapter nucleic acid comprises a shorter strand hybridized to a longer strand, wherein the longer strand is said strand of said double-stranded adapter nucleic acid that becomes ligated to the digested sample fragments, wherein each said shorter strand is complementary both to one of said single-stranded nucleotide overhangs and to one of said longer strands, and said generating step comprises prior to said amplifying step the melting of the shorter strand from the ligated fragments, contacting the ligated fragments with a DNA polymerase, extending the ligated fragments by synthesis with the DNA polymerase to produce blunt-ended double stranded DNA fragments, and wherein the primer nucleic acid strands comprise the sequence of said longer strands.

31. The method of claim 30 wherein during said amplifying step the primer nucleic acid strands are annealed to the ligated nucleic acid fragments at a temperature that is less than the melting temperature of the primer nucleic acid strands from strands complementary to the primer nucleic acid strands but greater than the melting temperature of the shorter adapter strands from said blunt-ended fragments.

32. The method of claim 30 wherein the primer nucleic acid strands further comprise at the 3'"'"' end of and contiguous with the longer strand sequence, the sequence of the portion of the restriction endonuclease recognition site remaining on a nucleic acid fragment terminus after digestion by the restriction endonuclease.

33. The method of claim 32 wherein each said primer nucleic acid strand further comprises at its 3'"'"' end one or more additional nucleotides 3'"'"' to and contiguous with said sequence of the portion of the restriction endonuclease recognition site remaining on a nucleic acid fragment after digestion by said restriction endonuclease, whereby the ligated nucleic acid fragment amplified is that comprising said remaining portion of said restriction endonuclease recognition site contiguous to said one or more additional nucleotides.

34. The method of claim 33 wherein said primer nucleic acid strands are detectably labeled, such that said primer nucleic acid strands comprising a particular said one or more additional nucleotides can be detected and distinguished from said primer nucleic acid strands comprising a different said one or more additional nucleotides.

35. The method of claim 6 wherein the recognition means comprise oligomers of nucleotides, universal nucleotides, nucleotide-mimics, or a combination of nucleotides, universal nucleotides, and nucleotide-mimics, said oligomers being hybridizable with the target nucleotide subsequences.

36. The method of claim 35 wherein the step of generating comprises amplifying with a nucleic acid polymerase and with primers, the sequence of said primers comprising (i) the sequence of said oligomers, and (ii) an additional subsequence 5'"'"' to said sequence of said oligomers.

37. The method of claim 36 further comprising:

(a) identifying a fragment of a nucleic acid in the sample which generates said one or more output signals; and

(b) recovering said fragment.

38. The method of claim 37 wherein said one or more output signals generated by said recovered fragment are not predicted to be produced by any sequence in said nucleotide database.

39. The method of claim 37 which further comprises using at least a hybridizable portion of said recovered fragment as a hybridization probe to bind to a nucleic acid.

40. The method of claim 1 wherein said one or more output signals further comprise a representation of whether an additional target nucleotide subsequence is present in said nucleic acid in the sample between said occurrences of target nucleotide subsequences.

41. The method of claim 40 wherein said additional target nucleotide subsequence is recognized by a method comprising contacting nucleic acids in the sample with oligomers of nucleotides, nucleotide-mimics, or mixed nucleotides and nucleotide-mimics, which are hybridizable with said additional target nucleotide subsequence.

42. The method of claim 1 wherein the step of generating comprises generating said one or more output signals only when an additional target nucleotide subsequence is not present in said nucleic acid in the sample between said occurrences of target nucleotide subsequences, and wherein a sequence from said sequence database is predicted to produce said one or more output signals when the sequence from said database (i) has the same length between occurrences of target nucleotide subsequences as is represented by said one ore more output signals, (ii) has the same target nucleotide subsequences as are represented by said one or more output signals, or target nucleotide subsequences that are members of the same sets of target nucleotide subsequences as are represented by said one or more output signals and (iii) does not contain said additional target nucleotide subsequence between occurrences of said target nucleotide subsequences.

43. The method of claim 42 wherein the step of generating comprises amplifying nucleic acids in the sample, and wherein said additional target nucleotide subsequence is recognized by a method comprising contacting nucleic acids in the sample with (a) oligomers of nucleotides, nucleotide-mimics, or mixed nucleotides and nucleotide-mimics, which hybridize with said additional target nucleotide subsequence and disrupt the amplifying step;

or (b) restriction endonucleases which have said additional target nucleotide subsequence as a recognition site and digest the nucleic acids in the sample at the recognition site.

44. The method of claim 12 or 36 wherein the step of generating further comprises separating nucleic acid fragments by length.

45. The method of claim 44 wherein the step of generating further comprises detecting said separated nucleic acid fragments.

46. The method of claim 45 wherein the abundance of a nucleic acid comprising a particular nucleotide sequence in the sample is determined from the level of the one or more output signals produced by said nucleic acid that are predicted to be produced by said particular nucleotide sequence.

47. The method of claim 45 wherein said detecting is carried out by a method comprising staining said fragments with silver, labeling said fragments with a DNA intercalating dye, or detecting light emission from a fluorochrome label on said fragments.

48. The method of claim 45 wherein said representation of the length between occurrences of target nucleotide subsequences is the length of fragments determined by said separating and detecting steps.

49. The method of claim 45 wherein said separating is carried out by use of liquid chromatography or mass spectrometry.

50. The method of claim 45 wherein said separating is carried out by use of electrophoresis.

51. The method of claim 50 wherein said electrophoresis is carried out in a gel arranged in a slab or arranged in a capillary using a denaturing or non-denaturing medium.

52. The method of claim 1 wherein a predetermined one or more nucleotide sequences in said database are of interest, and wherein the target nucleotide subsequences are such that said sequences of interest are predicted to produce at least one output signal that is not predicted to be produced by other nucleotide sequences in said database.

53. The method of claim 52 wherein the nucleotide sequences of interest are a majority of the sequences in said database.

54. The method of claim 1 wherein the target nucleotide subsequences have a probability of occurrence in the nucleotide sequences in said database of from approximately 0.01 to approximately 0.30.

55. The method of claim 1 wherein the target nucleotide subsequences are such that nucleotide sequences in said database comprise on average a sufficient number of occurrences of target nucleotide subsequences in order to on average be predicted to produce an output signal that is not predicted to be produced by any other nucleotide sequence in said database.

56. The method of claim 55 wherein the number of pairs of target nucleotide subsequences present on average in a nucleotide sequence in said database is no less than 3, and wherein the average number of output signals predicted to be produced from nucleotide sequences in said database is such that the average difference between lengths represented by the output signals predicted to be produced is greater than or equal to 1 nucleotide.

57. The method of claim 55 wherein the target nucleotide subsequences have a probability of occurrence, p, approximately given by the solution of ##EQU4## wherein N=the number of different nucleotide sequences in said database;

L=the average length of said different nucleotide sequences in said database;

M=the number of pairs of recognition means;

A=the number of pairs of target nucleotide subsequences present on average in said different nucleotide sequences in said database; and

B=the average difference between lengths represented by the signals predicted to be produced from the sequences in said database.

58. The method of claim 57 wherein A is greater than or equal to 3.

59. The method of claim 57 wherein B is greater than or equal to 1.

60. The method of claim 1 wherein the target nucleotide subsequences are selected according to the further steps comprising;

(a) predicting a pattern of signals that can be produced and the sequences predicted to produce each such signal by simulating the steps of probing and generating using sequences in said database of nucleotide sequences;

(b) computing an information measure, having a numerical value depending on input comprising the sequences predicted to generate one or more of the signals in said pattern of signals; and

(c) choosing the target nucleotide subsequences in order to predict a new pattern that maximizes said numerical value of the information measure.

61. The method of claim 60 wherein said choosing step selects target nucleotide subsequences which comprise the recognition sites of the one or more restriction endonucleases.

62. The method of claim 60 wherein said choosing step selects target nucleotide subsequences which comprise the recognition sites of one or more restriction endonucleases and one or more additional nucleotides, said additional nucleotides contiguous with said recognition sites.

63. The method of claim 60 wherein a predetermined one or more of the nucleotide sequences present in said database of nucleotide sequences are of interest, and said numerical value of said information measure equals the number of said sequences of interest which are predicted to produce at least one output signal that is not predicted to be produced by any other nucleotide sequence present in said database.

64. The method of claim 63 wherein said nucleotide sequences of interest are a majority of the nucleotide sequences present in said database.

65. The method of claim 60 wherein said choosing step is by a method comprising searching all combinations of target nucleotide subsequences of length less than approximately 10.

66. The method of claim 60 wherein said step of choosing target nucleotide subsequences is by a method comprising simulated annealing.

67. The method of claim 1 wherein the step of searching comprises:

(a) predicting a pattern of signals that can be produced and the sequences predicted to produce each such signal by simulating the steps of probing and generating using sequences in said database of nucleotide sequences; and

(b) determining the one or more nucleotide sequences in said database that are predicted to produce said one or more output signals by finding in said pattern those signals that comprise a representation of (i) the same lengths between occurrences of target nucleotide subsequences as is represented by the output signals, and (ii) the same target nucleotide subsequences as are represented by the output signals, or target nucleotide subsequences that are members of the same sets of target nucleotide subsequences represented by the output signals.

68. The method of claim 60 or 67 wherein the step of predicting comprises:

(a) searching for occurrences of said target nucleotide subsequences or sets of target nucleotide subsequences in nucleotide sequences in said database of nucleotide sequences;

(b) determining the lengths between occurrences of said target nucleotide subsequences or sets of target nucleotide subsequences in the nucleotide sequences of said database; and

(c) storing in said pattern of signals predicted to be produced from the sequences of said database information representing that said nucleotide sequences can produce output signals comprising a representation of the identities of said target nucleotide subsequences and of said lengths between occurrences of said target nucleotide subsequences.

69. The method of claim 20 wherein said restriction endonucleases generate 5'"'"' overhangs at the terminus of digested fragments and wherein each double stranded adapter nucleic acid comprises:

(a) a shorter nucleic acid strand consisting of a first and second contiguous portion, said first portion being a 5'"'"' end subsequence complementary to the overhang produced by one of said restriction endonucleases; and

(b) a longer nucleic acid strand having a 3'"'"' end subsequence complementary to said second portion of the shorter strand.

70. The method of claim 69 wherein said shorter strand has a melting temperature from a complementary strand of less than approximately 68°

C., and has no terminal phosphate.

71. The method of claim 70 wherein said shorter strand is approximately 12 nucleotides long.

72. The method of claim 69 wherein said longer strand has a melting temperature from a complementary strand of greater than approximately 68°

C., is not complementary to any nucleotide sequence in said database, and has no terminal phosphate.

73. The method of claim 72 wherein said ligated nucleic acid fragments do not contain a recognition site for any of said restriction endonucleases.

74. The method of claim 72 wherein said one or more restriction endonucleases are heat inactivated before said ligating.

75. The method of claim 72 wherein said longer strand is approximately 24 nucleotides long and has a G+C content between 40% and 60%.

76. The method of claim 20 wherein said restriction endonucleases generate 3'"'"' overhangs at the terminus of the digested fragments, and wherein each double stranded adapter nucleic acid comprises:

(a) a longer nucleic acid strand consisting of a first and second contiguous portion, said first portion being a 3'"'"' end subsequence complementary to the overhang produced by one of said restriction endonucleases; and

(b) a shorter nucleic acid strand complementary to the 3'"'"' end of said second portion of the longer nucleic acid stand.

77. The method of claim 76 wherein said shorter strand has a melting temperature from said longer strand of less than approximately 68°

C., and has no terminal phosphates.

78. The method of claim 77 wherein said shorter strand is 12 base pairs long.

79. The method of claim 76 wherein said longer strand has a melting temperature from a complementary strand of greater than approximately 68°

C., is not complementary to any nucleotide sequence in said database, has no terminal phosphate, and wherein said ligated nucleic acid fragments do not contain a recognition site for any of said restriction endonucleases.

80. The method of claim 79 wherein said longer strand is 24 base pairs long and has a G+C content between 40% and 60%.

122. A method of detecting one or more differentially expressed genes in an in vitro cell exposed to an exogenous factor relative to an in vitro cell not exposed to said exogenous factor comprising:

(a) performing the method of claim 1 wherein said plurality of nucleic acids comprises cDNA of RNA of said in vitro cell exposed to said exogenous factor;

(b) performing the method of claim 1 wherein said plurality of nucleic acids comprises cDNA of RNA of said in vitro cell not exposed to said exogenous factor; and

(c) comparing the identified, classified, or quantified cDNA of said in vitro cell exposed to said exogenous factor with the identified, classified, or quantified cDNA of said in vitro cell not exposed to said exogenous factor,

whereby differentially expressed genes are identified, classified, or quantified.

123. A method of detecting one or more differentially expressed genes in a diseased tissue relative to a tissue not having said disease comprising:

(a) performing the method of claim 1 wherein said plurality of nucleic acids comprises cDNA of RNA of said diseased tissue, such that one or more cDNA molecules are identified, classified, and/or quantified;

(b) performing the method of claim 1 wherein said plurality of nucleic acids comprises cDNA of RNA of said tissue not having said disease, such that one or more cDNA molecules are identified, classified, and/or quantified; and

(c) comparing said identified, classified, and/or quantified cDNA molecules of said diseased tissue with said identified, classified, and/or quantified cDNA molecules of said tissue not having the disease,

whereby differentially expressed cDNA molecules are detected.

124. The method of claim 123 wherein the step of comparing further comprises determining cDNA molecules which are reproducibly expressed in said diseased tissue or in said tissue not having the disease and further determining which of said reproducibly expressed cDNA molecules have significant differences in expression between the tissue having said disease and the tissue not having said disease.

125. The method of claim 124 wherein said determining cDNA molecules which are reproducibly expressed and said significant differences in expression of said cDNA molecules in said diseased tissue and in said tissue not having the disease are determined by a method comprising applying statistical measures.

126. The method of claim 125 wherein said statistical measures comprise determining reproducible expression if the standard deviation of the level of quantified expression of a cDNA molecule in said diseased tissue or said tissue not having the disease is less than the average level of quantified expression of said cDNA molecule in said diseased tissue or said tissue not having the disease, respectively, and wherein a cDNA molecule has significant differences in expression if the sum of the standard deviation of the level of quantified expression of said cDNA molecule in said diseased tissue plus the standard deviation of the level of quantified expression of said cDNA molecule in said tissue not having the disease is less than the absolute value of the difference of the level of quantified expression of said cDNA molecule in said diseased tissue minus the level of quantified expression of said cDNA molecule in said tissue not having the disease.

127. The method of claim 123 wherein the diseased tissue and the tissue not having the disease are from one or more mammals.

128. The method of claim 123 wherein the disease is a malignancy.

129. The method of claim 123 wherein the disease is a malignancy selected from the group consisting of prostrate cancer, breast cancer, colon cancer, lung cancer, skin cancer, lymphoma, and leukemia.

130. The method of claim 123 wherein the disease is a malignancy and the tissue not having the disease has a premalignant character.

131. A method of staging or grading a disease in a human individual comprising:

(a) performing the method of claim 1 in which said plurality of nucleic acids comprises cDNA of RNA prepared from a tissue from said human individual, said tissue having or suspected of having said disease, whereby one or more said cDNA molecules are identified, classified, and/or quantified; and

(b) comparing said one or more identified, classified, and/or quantified cDNA molecules in said tissue to the one or more identified, classified, and/or quantified cDNA molecules expected at a particular stage or grade of said disease.

132. A method for predicting a human patient'"'"'s response to therapy for a disease, comprising:

(a) performing the method of claim 1 in which said plurality of nucleic acids comprises cDNA of RNA prepared from a tissue from said human patient, said tissue having or suspected of having said disease, whereby one or more cDNA molecules in said sample are identified, classified, and/or quantified; and

(b) ascertaining if the one or more cDNA molecules thereby identified, classified, and/or quantified correlates with a poor or a favorable response to one or more therapies.

133. The method of claim 132 which further comprises selecting one or more therapies for said patient for which said identified, classified, and/or quantified cDNA molecules correlates with a favorable response.

134. A method for evaluating the efficacy of a therapy in a mammal having a disease, the method comprising:

(a) performing the method of claim 1 wherein said plurality of nucleic acids comprises cDNA of RNA of said mammal prior to a therapy;

(b) performing the method of claim 1 wherein said plurality of nucleic acids comprises cDNA of RNA of said mammal subsequent to said therapy;

(c) comparing one or more identified, classified, and/or quantified cDNA molecules of said mammal prior to said therapy with one or more identified, classified, and/or quantified cDNA molecules of said mammal subsequent to therapy; and

(d) determining whether the response to therapy is favorable or unfavorable according to whether any differences in the one or more identified, classified, and/or quantified cDNA molecules after therapy are correlated with regression or progression, respectively, of the disease.

136. The method of claim 57 wherein the values of A, B, L, and N are provided and the values of M and p are determined by jointly solving said equations.

137. The method of claim 1 wherein said step of searching is performed by a method comprising searching sequences in said nucleotide sequence database sequence by sequence.

140. The method of claim 19 wherein the step of probing further comprises contacting said fragments in said digested sample with shorter and longer nucleic acid strands, wherein each said shorter strand comprises a first subsequence 5'"'"' to a second subsequence, said first subsequence being hybridizable to an overhang, and said second subsequence being hybridizable to a longer strand, and ligating with a ligase said longer strand to the 5'"'"' end of a strand of said fragments to form ligated nucleic acid fragments.

81. A method for identifying or classifying a nucleic acid in a sample comprising a plurality of nucleic acids having different nucleotide sequences, said method comprising:

(a) probing said nucleic acid with a plurality of recognition means, each recognition means recognizing a target nucleotide subsequence or a set of target nucleotide subsequences, in order to produce an output set of signals, each signal of said output set representing whether said target nucleotide subsequence or one of said set of target nucleotide subsequences is present in said nucleic acid; and

(b) searching a nucleotide sequence database, said database comprising a plurality of known nucleotide sequences of nucleic acids that may be present in the sample, for sequences predicted to produce said output set of signals, a sequence from said database being predicted to produce an output set of signals when the sequence from said database (i) comprises the same target nucleotide subsequences represented as present, or comprises target nucleotide subsequences that are members of the sets of target nucleotide subsequences represented as present by the output set of signals, and (ii) does not comprise the target nucleotide subsequences not represented as present or that are members of the sets of target nucleotide subsequences not represented as present by the output set of signals,

whereby the nucleic acid is identified or classified.

82. The method of claim 81 wherein the set of signals are represented by a hash code which is a binary number.

83. The method of claim 81 wherein the step of probing produces an output set of signals further representing the numbers of occurrences of said target nucleotide subsequences or of members of said sets of target nucleotide subsequences in said nucleic acid.

84. The method of claim 83 wherein a nucleotide sequence from said database is predicted to produce said output set of signals when the sequence from said database (i) comprises the same target nucleotide subsequences with the same number of occurrences in said sequence, or comprises target nucleotide subsequences that are members of the same sets of target nucleotide subsequences with the same number of occurrences in said sequence, represented as present by said output set of signals, and (ii) does not comprise the target nucleotide subsequences not represented as present or that are members of the sets of target nucleotide subsequences not represented as present by said output set of signals.

85. The method of claim 81 wherein said plurality of nucleic acids are DNA.

86. The method of claim 85 wherein the recognition means comprise detectably labeled oligomers of nucleotides, universal nucleotides, nucleotide-mimics, or combinations of nucleotides, universal nucleotides, and nucleotide-mimics, and the step of probing comprises hybridizing said nucleic acid with said oligomers.

87. The method of claim 86 wherein said detectably labeled oligomers are detected by a method comprising detecting light emission from a fluorochrome label on said oligomers, or arranging said labeled oligomers to cause light to scatter from a light pipe and detecting said scattering.

88. The method of claim 86 wherein the recognition means are oligomers of peptido-nucleic acids.

89. The method of claim 86 wherein the recognition means are DNA oligomers, DNA oligomers comprising universal nucleotides, or sets of partially degenerate DNA oligomers.

90. The method of claim 85 wherein the step of searching comprises:

(a) predicting a pattern of sets of one or more signals that can be produced and the sequences capable of generating each set of signals in said pattern by simulating the step of probing using sequences in said database of nucleotide sequences; and

(b) determining one or more nucleotide sequences that are predicted to produce said output set of signals by finding in said pattern those sets of signals that comprise a representation of the presence of the same target nucleotide subsequences as are represented as present or target nucleotide subsequences that are members of the sets of target nucleotide subsequences represented as present by the output set of signals and (ii) does not represent as present the target nucleotide subsequences not represented as present or that are members of the sets of target nucleotide subsequences not represented as present by the output set of signals.

91. The method of claim 85 wherein the target nucleotide subsequences are selected according to the further steps comprising:

(a) predicting a pattern of sets of signals that can be produced and the sequences predicted to produce each set of signals in said pattern by simulating the step of probing using sequences in said database of nucleotide sequences;

(b) ascertaining an amount of information in said determined pattern of sets of signals, said amount being indicated by the value of an information measure, said information measure being computed from said determined pattern of sets of signals and the sequences predicted to produce each such set of signals in said pattern; and

(c) choosing the target nucleotide subsequences in order to predict a new pattern that maximizes said amount of information indicated by the information measure.

92. The method of claim 91 wherein the information measure is the number of sets of signals in the pattern which are predicted to be produced by one or more sequences in said database.

93. The method of claim 91 wherein the information measure is the number of sets of signals in the pattern which are predicted to be produced by only one sequence in said database.

94. The method of claim 91 wherein said choosing step is by a method comprising searching all combination of target nucleotide subsequences of length less than approximately 10.

95. The method of claim 91 wherein said choosing step is by a method comprising simulated annealing, according to which a state defined by said target nucleotide subsequences is annealed with respect to an energy function depending on said information measure.

96. The method of claim 90 or 91 wherein the step of predicting by simulating the probing further comprises:

(a) searching for said target nucleotide subsequences or sequences in said sets of target nucleotide subsequences in nucleotide sequences in said database of nucleotide sequences; and

(b) storing in said pattern of sets of signals predicted to be produced from said sequences in said database information representing that said nucleotide sequences can produce sets of signals comprising a representation of the identities of said target nucleotide subsequences or said sets of target nucleotide subsequences found in said searching step.

97. The method of claim 96 where the step of searching is carried out by a string search.

98. The method of claim 96 wherein the step of searching comprises counting the number of occurrences of said target nucleotide subsequences in each nucleotide sequence.

99. The method of claim 81 wherein the target nucleotide subsequences have a probability of occurrence in a nucleotide sequence in said database of nucleotide sequences of from 0.01 to 0.6.

100. The method of claim 99 wherein the target nucleotide subsequences are such that the presence of one target nucleotide subsequence in a nucleotide sequence in said database of nucleotide sequences is substantially independent of the presence of any other target nucleotide subsequence in the nucleotide sequence.

101. The method of claim 99 wherein fewer than approximately 50 target nucleotide subsequences are selected.

138. The method of claim 81 wherein said step of searching is performed by a method comprising searching sequences in said nucleotide sequence database sequence by sequence.

141. The method of claim 81 wherein said target nucleotide subsequences have a probabilities of occurrence in said nucleic acids of said sample of nucleic acids of at least 0.05.

102. A method for identifying, classifying, or quantifying DNA molecules in a sample of DNA molecules having a plurality of different nucleotide sequences, the method comprising the steps of:

(a) digesting said sample 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;

(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 longer oligodeoxynucleotide;

(c) ligating said longer oligodeoxynucleotides to said 5'"'"' overhangs on said DNA fragments to produce ligated DNA fragments and removing said shorter oligodeoxynucleotides from said ligated DNA fragments;

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

(e) amplifying said blunt-ended double stranded DNA fragments by a method comprising contacting said DNA 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 DNA fragments; and

(g) 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.

103. The method of claim 102 wherein the sequence of each primer oligodeoxynucleotide further comprises 3'"'"' to and contiguous with the sequence of the longer oligodeoxynucleotide the portion of the recognition site of said one or more restriction endonucleases remaining on a DNA fragment terminus after digestion, said remaining portion being 5'"'"' to and contiguous with one or more additional nucleotides, and wherein a sequence from said database is predicted to produce a fragment of determined length when the sequence from said database comprises subsequences that are the recognition sites of said one or more restriction endonucleases contiguous with said one or more additional nucleotides and when the subsequences are spaced apart by the determined length.

104. The method of claim 102 wherein said determining step further comprises detecting the amplified DNA fragments by a method comprising staining said fragments with silver.

105. The method of claim 102 wherein said oligodeoxynucleotide primers are detectably labeled, wherein the determining step further comprises detection of said detectable labels, and wherein a sequence from said database is predicted to produce a fragment of determined length when the sequence from said database comprises recognition sites of the one or more restriction endonucleases, said recognition sites being that are identified by the detectable labels of said oligodeoxynucleotide primers, said recognition sites being spaced apart by the determined length.

106. The method of claim 102 wherein said determining step further comprises detecting the amplified DNA fragments by a method comprising labeling said fragments with a DNA intercalating dye or detecting light emission from a fluorochrome label on said fragments.

107. The method of claim 102 further comprising, prior to said determining step, the step of hybridizing the amplified DNA fragments with a detectably labeled oligodeoxynucleotide complementary to a subsequence, said subsequence differing from said recognition sites of said one or more restriction endonucleases, wherein the determining step further comprises detecting said detectable label of said oligodeoxynucleotide, and wherein a sequence from said database is predicted to produce a fragment of determined length when the sequence from said database further comprises said subsequence between the recognition sites of said one or more restriction endonucleases.

108. The method of claim 102 wherein the one or more restriction endonucleases are pairs of restriction endonucleases, the pairs being selected from the group consisting of Acc56I and HindIII, Acc65I and NgoMI, BamHI and EcoRI, BglII and HindIII, BglII and NgoMI, BsiWI and BspHI, BspHI and BstYI, BspHI and NgoMI, BsrGI and EcoRI, EagI and EcoRI, EagI and HindIII, EagI and NcoI, HindIII and NgoMI, NgoMI and NheI, NgoMI and SpeI, BglII and BspHI, Bsp120I and NcoI, BssHII and NgoMI, EcoRI and HindIII, and NgoMI and XbaI.

109. The method of claim 102 wherein the step of ligating is performed with T4 DNA ligase.

110. The method of claim 102 wherein the steps of digesting, contacting, and ligating are performed simultaneously in the same reaction vessel.

111. The method of claim 102 wherein the steps of digesting, contacting, ligating, extending, and amplifying are performed in the same reaction vessel.

112. The method of claim 102 wherein the step of determining the length is performed by electrophoresis.

113. The method of claim 102 wherein the step of searching said DNA database comprises:

(a) predicting a pattern of fragments that can be produced and the sequences in said DNA database predicted to produce each such fragment by simulating the steps of digesting with said one or more restriction endonucleases, contacting, ligating, extending, amplifying, and determining using sequences in said DNA database; and

(b) determining the sequences that are predicted to produce said one or more fragments of determined length by finding in said pattern one or more fragments that have the same length and recognition sites as said one or more fragments of determined length.

114. The method of claim 102 wherein the steps of digesting and ligating go substantially to completion.

115. The method of claim 102 wherein the DNA sample is cDNA of RNA from a tissue or a cell type derived from a plant, a single celled animal, a multicellular animal, a bacterium, a virus, a fungus, or a yeast.

116. The method of claim 102 wherein the DNA sample is cDNA of RNA from one or more cell types of a mammal.

117. The method of claim 102 wherein the mammal is a human.

118. The method of claim 102 wherein the mammal is a human having or suspected of having a diseased condition.

119. The method of claim 118 wherein the diseased condition is a malignancy.

120. The method of claim 102 wherein said DNA sample is cDNA prepared from mRNA.

139. The method of claim 102 wherein said step of searching is performed by a method comprising searching sequences in said nucleotide sequence database sequence by sequence.

121. A method for identifying, classifying, or quantifying DNA molecules in a sample of DNA molecules with a plurality of nucleotide sequences, the method comprising the steps of:

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

(b) contacting said fragments with shorter and longer oligodeoxynucleotides, each said longer oligodeoxynucleotide consisting of a first and second contiguous portion, said first portion being a 3'"'"' end subsequence complementary to the overhang produced by one of said restriction endonucleases, each said shorter oligodeoxynucleotide complementary to the 3'"'"' end of said second portion of said longer oligodeoxynucleotide stand;

(c) ligating said longer oligodeoxynucleotides to said DNA fragments to produce a ligated fragments and removing said shorter oligodeoxynucleotides from said ligated DNA fragments;

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

(e) amplifying said double stranded DNA fragments by use of a DNA polymerase and primer oligodeoxynucleotides to produce amplified DNA fragments, each said primer oligodeoxynucleotide having a sequence comprising that of a longer oligodeoxynucleotide;

(f) determining the length of the amplified DNA fragments; and

(g) 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 sequences in said sample are identified, classified, or quantified.

135. The method of claim 135 wherein the mammal is a human.