CA2441634A1 - Molecular tagging system - Google Patents

Abstract

A mixture of microparticles is described. Each microparticle has polynucleotides of a population attached thereto such that substantially all different polynucleotides in the population are attached to different microparticles.
The polynucleotides are selected from cDNAs and genomic DNA fragments.

Description

~~(;ilI aR TAGGING SYSTEM
Field of the ' vention . The. invention relates generally to methods for identifying, sorting, and/or tracking molecules, especially polynucleotides, with oIigonucleotide labels, and more particularly, to a method of sorting polynucleotides by specific hybridization to oligonucleotide tags.
$A('.KGROUND ' Specific hybridization of oligonucleotides and their analogs is a fundamental process that is employed in a wide variety of research, medical, and industrial applications, including the identification of disease-related polynucleotides in diagnostic assays, screening for clones of novel target polynucleoades. identification of specific polynucleotides in blots of mixtures of polynucleotides, amplification of specific target polynucleotides, therapeutic blocking of inappropriately expressed genes. DNA sequencing. and the Like, e.g. Sambrook et al, Mo)ecular Cloning: A Laboratory Manual. 2nd Edition (Cold Spiing Harbor Laboratory, New York, 1989); Keller and Manak, DNA Probes. 2nd Edition (Stockton Press, New York, 1993): Milligan et al; J. Med. Chem., 36: 1923-193_7 (1993);
Drmanac et al, Science: 260: 1649-1652 (1993); Bains, J. DNA Sequencing and Mapping, 4:

( I 993).
Specific hybridization has also been proposed as a method of tracking, retrieving, and identifying compounds labeled with oligonucleotide tags. For example, in multiplex DNA sequencing oligonucleotide tags are used to identify electrophoretically separated bands on a gel that consist of DNA fragments generated in the same sequencing reaction.
In this~way, DNA fragments from many sequencing reactions are separated on the same lane oC a gel which is then blotted with separate solid phase materials on which the fragment bands from the separate sequencing reactions are visualized with oligonucleotide probes that specifically hybridize to complementary tags. Church et a1. Science, 240:

(1988). Similar uses of oligonucleotide tags have also been proposed for identifying explosives, potential pollutants, such as crude oil, and currencv fear prevention and detection 3U of counterfeiting, e.g. reviewed by Dollinger. pages 265-27.~ in Mullis et al, editors, The Polymerase Chain Reaction lBirkhauser, Boston, 1994). More recently, systems employing oligonucleotide tags have also been proposed as a means of manipulating and identifying individual molecules in complex combinatorial chemical libraries. for example, as an aid to screening such libraries for drug candidates. Brenner and Lerner, Pros. Nail.
Acad. Sci.. 89:
5381-5383 (1993): AIper, Science. 264: 1399-1401 (1994): and Needels et al, Proc. NatI.
Acad. Sci.. 90: 10700-107()4 (1993).
The successful implementatit~n of such tagging schemes depends in large part on the success in achieving specific hybridization between a tag and its complementary probe.

That is, for an oligonucleotide tag to successfully identify a substance, the number of false positive and false negative signals must be minimized. Unfortunately, such spurious signals are not uncommon because base .pairing and base stacking free energies vary widely among nucleotides in a duplex or triplex structure. For example, a duplex consisting of a repeated sequence of deoxyadenine (A) and thymidine (T) bound to its complement may have less stability than an equal-length duplex consisting of a repeated sequence of deoxyguanidine (G) and deoxycytidine (C) bound to a partially complementary target containing a mismatch. Thus, if a desired compound from a large combinatorial chemical library were tagged with the former oligonucleotide, a significant possibility would exist that, under hybridization conditions designed to detect perfectly matched AT-rich duplexes, undesired compounds labeled with the GC-rich oligonucleotide--even in a mismatched duplex--would be detected along with the perfectly matched duplexes consisting of the AT-rich tag. In the molecular tagging system proposed by Brenner et al (cited above), the related problem of mis-hybridizations of 1 S closely related tags was addressed by employing a so-called "comma-less"
code, which ensures that: a probe out of register (or frame shifted) with respect to its complementary tag would result in a duplex with one or more mismatches for each of its five or more three-base words, or "codons."
Even though reagents, such as tetramethylammonium chloride, are available to negate base-specific stability differences of oligonucleotide duplexes, the effect of such reagents is often limited and their presence can be incompatible with, or render more difficult, further manipulations of the selected compounds, e.g. ampliFcation by polymetase chain reaction (PCR), or the like.
Such problems have made the simultaneous use of multiple hybridization probes in the analysis of multiple or complex genetic loci, e.g. via multiplex PCR, reverse dot blotting, or the like, very difficult. As a result, direct sequencing of certain loci, e.g. HLA
. genes. has been promoted as a reliable alternative to indirect methods employing specific hybridization for the identification of genoryges, e.g. Gyllensten et aI.
Proc. Natl. Acad.
Sci.: 85: 7652-7656 (19A8).
The ability to sort cloned and identically tagged DNA fragments onto distinct solid .phase supports would facilitate such sequencing, particularly when coupled wiith a non geI-based sequencing methodology simultaneously applicable to many samples in parallel.
In view of the above, it would be useful if there were available an oligonucleotide based tagging system which provided a large repertoire of tags, but which also minimized the occurrence of false positive and false negative signals without the need to employ special reagents f~7r altering natural base pairing and base stacking free energy differences.
Such a tagging system would find applications in many are;~s. including construction and ~2-use of combinatorial chemical libraries, large-scale mapping and sequencing of DNA, genetic identification, medical diagnostics, and the Like.
Summate of the Invention .An object of my invention is to provide a molecular tagging system for tracking, retrieving; and identifying compounds.' Another object of my invention is to provide a method for sorting identical molecules; or subclasses of molecules, especially polynucleotides, onto surfaces of solid phase materials by the specific hybridization of oligonucleotide tars and their tompIements.
A further object of my invention is to provide a combinatorial chemical library whose member compounds are identified by the specific hybridization of.oligonucleotide tags and their complements.
A still further object of my invention is to provide a system for tagging and sorting many thousands of fragments, especially randomly overlapping fragments, of a target polynucleotide for simultaneous analysis andlor sequencing.
Another object of my invention is to provide a rapid and reliable method for sequencing target polynucleotides having~a length in the range of a few hundred basepairs to several tens of thousands of basepairs.
My invention achieves these and other objects by providing a method and materials for tracking, identifying, andlor sorting classes or subpopulations of molecules by the use of oligonucleotide tags. An oligonticleotide tag of the invention consists of a plurality of subunits, each subunit consisting of an oligonucleotide of 3 to 6 nucleotides in length.
~ Subunits of. an oligonucleotide tag are selected from a minimally cross-hybridizing set. In such a set, a duplex or triplex consisting of a subunit of the set and the complement of any other subunit of the set contains at least two mismatches. In other words, a subunit of a minimally cross-hybridizing set at best forms a duplex or triplex having two mismatches with the complement of any other subunit of the same set. The number of oligonucleotide tags available in a particular embodiment depends on the number of subunies per tag and on the length of the subunit. The number is generally much less than the number of all possible sequences the length of the tag, which for a tag n nucleotides Long would be 4n.
Mere preferably, subunits are oligonucleotides from 4 to 5 nucleotides in length.
In one aspect of my invention, complements of oligonucleotide tags attached to a solid phase support are used to sort polynucleotides from a mixture of polynucleotides each containin; a tag. In this embodiment, complements of the oliaoniicleotide tags are synthesized on the surface of a solid phase support, such as a microscopic bead or a specific locaticin on an array of synthesis locations on a single support, such that populations of .identical sequences are produced iri specific regions. That is, the surface of each support, in the case of a bead, or of each region, in the case of an array, is derivatized by only one type of complement which has a particular sequence.
The population of such beads or regions Contains a repertoire of complements with distinct sequences, the size of the-repertoire depending on the number of subunits per oligonucleotide tag,and the length of the subunits employed. Similarly, the polynucleotides to be sorted each comprises an oligonucieotide tag in the repertoire, such that identical polynucleotides have the same tag and differerit polynucleotides have different togs. As explained more fully below, this condition is achieved by taking a IO sufficiently.small sample of tagged polynucleotides from the full ensemble of tagged polynucleotides. Thus, when the populations of supports and polynucleotides are mixed under conditions which permit specific hybridization of the oligonucleotide tags with their respective complements, subpopulations of identical polynucleotides are sorted onto particular beads or regions. The subpopulations of polynucleotides can then be IS manipulated on the solid phase support by micro-biochemical techniques.
Generally, the method of my invention comprises the following steps: (a) attaching an oligonucleotide tag from a repertoire of tags to each molecule in a population of molecules (l) such that substantially all the same molecules or same subpopulation of molecules in the population have the same oligonucleotide tag attached and substantially 20 all different molecules -or different subpopulations of molecules in the population have different oligonucleotide tags attached and (ii) such that each oligonucleotide tag from the repenoire comprises a plurality of subunits and each subunit of the plurality consists of an oiigonucleotide having a length from three to six nucleotides or from three to six basepairs, the subtinits being selected from a minimally cross-hybridizing set; and (b) 25 sorting the molecules or subpopuladons of molecules of the population by specifically hybridizing the oligonucleotide tags with their respective complements.
An important aspect of my invention is the use of the oligonucleotide tags to sort polynucleotides for parallel sequence determination. Preferably, such sequencing is carried out by the following seeps: (a) generating from the target polynucleotide a 3U plurality of fragments that cover the target polynucleotide; (b) attaching an oligonucleotide tag from a repertoire of tags to each fragment of the plurality (l) such that substantially all the same fragments have the same oligonucleotide tag attached and substantially all different fragments have different oligonucleotide tags attached and (ii) such that each oligonucleotide tag from the repertoire comprises a plurality of subunits 35 and each subunit of the plurality consists of an oligonucleotide having a length from three to six nucleotides or from three to six basepairs, the subunits being selected from a minimally cross-hyhridizing sec:

sorting the fragments by specifically hybridizing the oligonucleotide tags with their respective complements: (c) determining the nucleotide sequence of a portion of each of the fragments of the plurality, .preferably by a single-base sequencing methodology as described below: and (d) determining the nucleotide sequence of the target polynucIeotide by collating the sequences of the fragments.
My invention overcomes a key deficiency of current methods of tagging or labeling molecules with oligonucleotides: ,'By coding the sequences of the tags in accordance with the invention, the stability of any mismatched duplex or triplex between a tag and a complement to another tag is far lower than that of any perfectly matched duplex between the tag.and its.own complement. Thus, the problem of incorrect sorting because of mismatch duplexes of GC-rich tags being more stable than perfectly matched AT-rich tags is eliminated.
When used in combination with solid phase supports, such as microscopic beads.
my invention provides a readily automated system for manipulating and sorting polynucleotides, panicularly useful in Large-scale parallel operations, such as large-scale DNA sequencing, wherein many target polynucleotides or many segments of a single target polynucleotide are sequenced and/or analyzed simultaneously.
Brief Description of the Drawines Figures la-lc illustrates structures of labeled probes employed in a preferred method of "single base" sequencing which may be used with the invention.
Figure 2 illustrates the relative positions of the nuclease recognition site, ligation site. and cleavage site in a ligated complex formed between a target polynucleotide and a prohe used in a preferred "single base", sequencing method.
Figure 3 is a flow chart illustrating a general algorithm for. generating minimally cross-hybridizing sets.
Figure 4 illustrates a scheme for synthesizing and using a combinatorial chemical library in which member compounds are labeled with oligonucleotide tags in accordance with the invention.
3U Figure 5 diagrammatically illustrates an apparatus for carrying out parallel operations, such as polynucleotide sequencing, in accordance with the invention.
. "Complement" or "tag complement" as used herein in reference to oligonucleotide tags refers to an oligonucleotide to which a oligonucleotide tag specifically hybridizes to form a, perfectly matched duplex i~r triplex. In embodiments where specific hybridization results in' a triplex, the oli~unucleotide tae may be selected to he either double stranded or single stranded. Thus, where triplexes are formed. the term,"complement" is meant to encompass either a double stranded complement of a single stranded oligonucleocide tag or a single stranded complement of a double stranded oligonucleotide tag.
The term "oligonucleotide" as used herein includes linear oligomers of natural or modified monomers or linkages, including deoxyribonucleosides.
ribonucleosides, a-anomeric forms thereof, peptide nucleic.~acids (PNAs), and the Like, capable of specifically binding to a target polynucleotide by way of a regular pattern of monomer-to-monomer interactions; such as Wacson-Crick type of base pairing, base stacking.
Hoogsteen or reverse Hoogsteen types of base pairing, or the like: Usually monomers are linked by phosphodiescer bonds or analogs thereof to form oligonucleotides ranging in size from a IU few monomeric units, e.g. 3-4, to several tens of monomeric units. Whenever an oligonucleotide is represented by a sequence of letters, such as "ATGCCTG," it will be understood that the nucleotides are in 5'--~3' order from left to right and that "A" denotes deoxyadenosine, "C" denotes deoxycytidine, "G" denotes deoxyguanosine, and "T"
denotes thymidine. unless otherwise noted. Analogs of phosphodiester linkages include 15 phosphorothioate, phosphorodithioate, phosphoranilidate, phosphoramidate, and the like.
Usually oligonucleotides of the invention comprise the four natural nucleotides: however;
they may also comprise non-natural nucleotide analogs. It is clear to those skilled in the art when oligonucleotides having natural or non-natural nucleotides may be=employed, e.g.
where processing by enzymes is called for, usually oligonucleotides consisting of natural 20 nuclebtides are required.
"Perfectly matched" in reference to a duplex means that the poly- or oligonucleotide strands making up the duplex form a double stranded structure with one other such that every nucleotide in each strand undergoes Watson-Crick basepairing with a nucleotide in the ocher strand. The term also comprehends the pairing of nucleoside 25 analogs, such as deoxyinosine, nucleosides with 2-aminopurine bases, and the like, that may be employed. In reference to a triplex, the term means that the triplex consists of a perfectly, matched duplex and a third strand in which every nucleotide undergoes Hoogsteen «r reverse Hoogsteen association with a basepair of the perfectly matched duplex. Conversely, a "mismatch" in a duplex between a tag and an oligonucleotide means 3U that a pair or triplet of nucleotides in the duplex or triplex fails tcoundergo Watson-Crick andlor Hoogsteen and/or reverse Hoogsteen bonding.
As used herein, "nucleoside" includes the natural nucleosides, including 2'-deoxy and 2'-hydroxyl forms; e.g. as~described in Kotn.berg and Baker, DNA
Replication, 2nd Ed. (Freeman. San Francisco, 1992). "Analogs" in reference to nucleosides includes 35 synthetic nucleosides having modified base moieties and/or modified sugar moieties, e.g.
described by Scheit. Nucleotide Analogs (John Wilty, New York. 198U); Uhlman and Peyman. Chemical Reviews. 90: 543-584 ( 199U), or the like. with the only proviso that they are capable of specific hybridization. Such analogs include synthetic nucleosides -. 6 -designed to enhance bindine properties, reduce degeneracy, increase specificity, and the like.
Detailed Descriptiy o~ f-the jnvention The invention provides a method of labeling and sorting molecules, particularly polynucleoti:des, by the use of oligonucleotide tags. The oligonucleotide tags of the invention comprise a plurality of "words" or'subunits selected from minimally cross-hybridizing sets of subunits. Subunits of such sets cannot form a duplex or triplex with the complement of another subunit of the same set with less than two mismatched nucleotides.
1() Thus, the sequences of any two oligonucleotide tags of a repertoire that form duplexes will never be, "closer" than differing by two nucleotides. In particular embodiments, sequences of any two oligonucleotide tags of a repertoire can be even "further" apart, e.g.
by designing a minimally cross-hybridizing set such that subunits cannot form a duplex with the complement of another subunit of the same set with less than three mismatched nucleotides, and so on. In such embodiments, greater specificity is achieved, but the total repertoire of tags is smaller. Thus, for tags of a given length and word size, a trade off must be made between the degree of specificity desired and the size of repertoire desired.
The invention is particularly useful in labeling and sorting polynucleotides for parallel operations, such as sequencing, fingerprinting or other types of analysis.

oltstnucting,OliEonucleotide Tags from Minima ]~y~r_~ss-Hyhridizing Sets of Subunits The nucleotide sequences of. the subunits for any minimally cross-hybridizing set are conveniently enumerated by simple computer programs following the general algorithm illustrated in Fig. 3, and as exemplified by program minhx whose source code is listed in Appendix I. Minhx computes all minimally cross-hybridizing sets having subunits composed of three kinds of nucleotides and having length of four.
The algorithm of Fig. 3 is implemented by first defining the characteristic of the subunits of the minimally cross-hybridizing set i.e. length, number of base differences 3U between memhers. and composition, e.g. do they consist of two, three, or four kinds of bases. A table Mn, n=1, is generated (1U0) that consists of all possible sequences of a given length,and composition. An initial subunit S 1 is selected and compared ( 12U) with successive subunits Si for i=n+1 to the end of the table. Whenever a successive subunit has. the required number of mismatches to be a member of the minimally cross-hybridizing set, it is saved in a new table Mn+1 ( 135), that also contains subunits previously selected in prior passes through step 12(). For example. iri the first set of cpmparisons, M2 will contain S ~: in the second set e~f ce~mparisons. M~ will contain S 1 and S2:
in the third set of comparisons. M,~ will contain S l . S~. and S~: and so on. Similarly.
comparisons in table Mj will be between Sj and all successive subunits in Mj. Note that each successive table'1VI~+~ is smaller than its predecessors as subunits are eliminated in successive passes through step 13U. After every subunit of table Mn has been compared ( 1-10) the old table is replaced by the new table Mn+l, and the next round of comparisons are begun. The process stops ( 160) when a table Mn is reached that contains no successive subunits to compare to the selected subunit S.i, i.e. Mn=Mn+1-Preferably, minimally cross-hybridizing sets comprise subunits.that make approximately equivalent contributions to duplex stability as every other subunit in the set.
In this way, the stability of perfectly matched duplexes between every subunit and its complement is approximately~equal. Guidance for selecting such sets is provided by published techniques for selecting optimal PCR primers and calculating duplex stabilities, e.g. Rychlik et al, Nucleic Acids Research. 17: 8543-8551 ( 1989) and 18: 6409-( 1990: Breslauer et al. Proc. Natl. Acid. Sci.. 83: 3746-3750 ( 1986):
Wetmur; Crit. Rev.
.Biochem. Mol. Biul.. 26: 227-?59 11991 ):and the like..For shorter tags, e.a.
about 3U
nucleotides or less, the algorithm described by Rychlik and Wetmur is preferred, and for longer tags, e.g. about 30-35 nucleotides or greater, an algorithm disclosed by Suggs et al.
pages 683-693 in Brown, editor. ICN-UCLA Symp. Dev. Biol., VoI. 23 (Academic Press.
' New York, 1981) may he conveniently employed. Clearly, the are many approaches available to one skilled in the art for designing sets of minimally cross-hybridizing subunits within the scope of the invention. For example, t:o minimize the affects of different base-stacking energies of terminal nucleotides when subunits are assembled, subunits may be provided that have the same terminal nucleotides. In this way, when subunits are linked.
the sum of the base-stacking energies of all the adjoining terminal nucleotides will be the same. thereby reducing or eliminating variability in tag melting temperatures.
35 A preferred embodiment of minimally cross-hybridizing sets are those whose suhunits are made up of three of the four natural nucleotides. .As will be discussed more fully below. the absence of one type of nucleotide in the oligonucleotide tags permits target polynucleotides to be loaded onto solid phase supports by use of the 5'~3' exonuclease activity of a DNA polymerise. The following is an exemplary minimally 3() cross-hybridizing set of suhunics each comprising four nucleotides selected from the group consisting of A, G, and T: ~ -Table I
Word: w1 w-, w~ wQ
Sequence: GATT TGAT TAG:: TTTG
3;
-g.

Word: w5 w~, w~ wR
Sequence: GTAA AGTA ATGT A_~AG
In this 'set, each member would form a duplex having three mismatched bases with the complement of every other member.
Further exemplary minimally cross-hybridizing sets are listed below in Table I.
Clearly, additional sets can he generated by substituting different groups of nucleotides, or by using subsets of known minimally cross-hybridizing sets.
Table II
Fxemnlarv Minimallv Cross-Hyhridi ' , Sets of 4-mer Suhunits Set Set 2 bet 3 bet 4 Set 5 Set 6 CATT ACCC AAAC AAAG AACA AACG

CTAA AGGG ACCA ACCA ACAC ACAA

TCAT CACG AGGG AGGC AGGG AGGC

ACTA CCGA CACG CACC CAAG CAAC

TACA CGAC CCGC CCGG CCGC CCGG

TTTC GAGC CGAA CGAA CGCA CGCA

ATCT GCAG GAGA GAGA GAGA GAGA

AAAC GGCA GCAG GCAC GCCG GCCC

AAAA GGCC GGCG GGAC GGAG

Set Set 8 Set 9 bet 10 Set 11 St 12 AAGA AAGC AAGG ACAG ACCG ALGA

ACAC ACAA ACAA AACA AAAA AAAC

AGOG AGCG AGCC AGGC AGGC AGCG

CAAG CAAG CAAC CAAC CACC CACA

COCA CCCC CCCG CCGA CCGA CCAG

CGGC CGGA CGGA CGCG CGAG CGGC

GACC GACA GACA GAGG GAGG GAGG
-GCGG GCGG GCGC GCCC GCAC GCCC

GGAA GGAC GGAG GGA.~ GGCA- GGAA

The oligonucleotide tags of the invention and their complements are conveniently synthesized can an automated DNA synthesizer, e.g. an Applied Biosystems, Inc.
(Foster .
City, California) model 392 or 394 DNA/RNA Synthesizer, using standard chemistries, such as phosphoramidite chemistry, e.g. disclosed in the following references:
Beaucage and Iyer. Tetrahedron. 48: 2??3-2311 ( 1992): Molko et al, U.S. patent 4.980,460; Koster et al, LT.S. patent 4,725.677: Caruthers et al, U.S. patents 4.415,732:
4,458,066; and 4,973.679: and the like. Alternative chemistries, e.g. resulting in non-natural backbone groups. such as phosphorothioate, phosphoramidate. and the like. may also be employed 2(l provided that the resulting oligonucleotides are capable of specific hybridization. In some _9_ embodiments, tags may comprise naturally occurring nucleotides that permit processing or manipulation by enzymes, while- the corresponding tag complements may comprise non-natural nucleotide.analo~s, such as peptide nucleic acids. or like compounds.
that promote the formation of more stable duplexes during sorting.
When microparticles are used as supports, repertoires of oligonucleotide tags and tag complements are preferably generated by subunit-wise synthesis via "split and mix"
techniques, e.g. as disclosed in Shortle et al, International patent application PCT/US93/U3418. Briefly, the basic unit of the synthesis is a subunit of the oligonucleotide tag. Preferably, phosphoramidite chemistry is used and 3' phQsphoramidite oligonucleotides are prepared for each subunit in a minimally cross-hyhridizing set, e.g. for the set first listed above, there would he eight 4-mer 3'-phosphoramidites. Synthesis proceeds as disclosed by Shortle et al or in direct analogy with the techniques employed to generate diverse oligonucleotide libraries using nucleosidir monomers, e.g. as disclosed in Telenius et al. Genomics; 13: 7i8-725 (1992):
l 5 Welsh et al; Nucleic Acids Research, 19: 5275-5279 ( 1991 ); Grothues et al, Nucleic Acids Research. 21: 1321-1322 ( 1993): Hardey, European patent application '90304496.4; Lam et al, Nature, 354: 82-84 ( 1991 ): Zuckerman et al, Int. J. Pept. Protein Research, 40: 498-507 ( 1992); and the like. Generally, these techniques simply call for the application of mixtures of the activated monomers to. the growing oligonucleotide during the coupling 2U steps.
Double stranded forms of tags may be made by separately synthesizing the . complementary strands followeii by mixing under conditions that permit duplex formation.
Alternatively. double stranded tags may he formed by first synthesizing a single stranded repertoire linked to a known oligonucleotide sequence that serves as a primer binding site.
25 The second strand is then synthesized by combining the single stranded repertoire with a primer and extending with a polymerise. This latter approach is described in Oliphant et al, Gene. 4~: I77-I83 (I986). Such duplex tags may then he inserted into cloning vectors along with target polynucleotides for sorting and manipulation of the target polynucleotide in accordance with the invention.
30 In emhodimentc where specific hybridization occurs vi;l triplex formation, coding ,of tag sequences follows the same principles as for duplex-forming tags;
however, there are further constraints on the selection of subunit sequences. Generally, third strand association via Hoogsteen type of binding is most stable along homopyrimidine-homopurine tracks in a double.scranded target. Usually, base triplets form in T-A*T or C-35 G*C motifs (where "-" indicates Watscm-Crick pairing and "*" indicates Hoogsteen type of binding); however, other motifs are also possible: For example. Hoogsteen base pairing permits parallel and antiparallel orientations hetween the third strand (the Hoogsteen suand) and the purine-rich strand of the duplex to which the third strand binds, dependin_ on conditions and the cornposiuon of the strands. There is extensive guidance in the literature for selective appropriate sequences, orientation, conditions, nucleoside type (e.a.
whether ribose or deoxyribose nucleosides are employed), base modifications (e.g.
methylated cytosine, and the like) in order to maximize, or otherwise regulate, triplex stability as desired in particular embodiments, e:g. Roberts et al, Proc.
Natl. Acad. Sci., 88: 9397-9401 ( 199 I ); Robert5 et al, .Science, 258: 1463-1466 ( 1992);
Distefano et al, Proc. Natl. Acad. Sci., 90: 1179-I 183 (1993); Mergny et al, Biochemistry, 30:

( 1991 ): Cheng et al, J. Am. Chem. Soc., 1'14: 4465-4474 ( 1992); Beal and Dervan, Nucleic Acids Research, 20: 2773-2776 {1992); Beal and Dervan, J. Am. Chem.
Soc., 114: 4976-4982 (1992); Giovannangeli et al, Proc. Natl..Acad.-Sci., 89: 8631-(1992): Moser and Dervan. Science, 238.: 645-650 (1987); McShan et al. J.
Biol. Chem., 267:5712-5721 ( 1992): ~'oon et al, Proc. Natl. Acad. Sci., 89: 3840-3844 ( 1992); Blume et al. Nucleic Acids Research, 20: 1777-I784 (1992); Thuong and Helene, Angew.
Chem.
Inc. Ed. Engl. 32: 666-690 (1993); and the like. Conditions for annealing single-stranded IS or duplex tags to their single-stranded'or duplex complements are well known, e.g. Ji et al, Anal. Chem. 65: 1323-1328 (1993).
Oligonucleotide tags of the invention may range in length from 12 to 60 nucleotides or basepairs. Preferably, oligonucleotide tags range in length from 18 to 40 nucleotides or basepairs. More preferably, oligonucleotide tags range in length from 25 to 40 nucleotides or basepairs. In terms of preferred and more preferred numbers of subunits, these ranges may be expressed as follows: ' Table III
plumbers of~~h~mitt in Tads in Preferred EmhodimenL
Monomers irl,~,Subunit Nucleotides in OliEonuc~eotide Tae (12-60) (18-40) (25-40) 3 4-2() subunits 6-13 subunits 8-13 subunits 4 3-.IS subunits 4-1~ subunit-s 6-10 subunits 5 2-I2 subunits 3-8 subunits 5-8 subunits 6 2-10 subunits 3-6 subunits 4-6 subunits Most preferably. oligonucleotide tags are single~stranded and speciF~c hybridization occurs 3() via Watson-Crick pairing with a tag complement. ' gttachin,g,Ta~~o M~lecciles Oligonucleotide tags may be attached to many different classes of molecules by a variety of reactive functionalities well known in the art, e.g. Haugland, Handbook of Fluorescent Probes and Research Chemicals (Molecular Probes, Ine.. Eugene.
1992);
Khanna et aI, U.S, patent 4,318,846; or the like. Table N provides exemplary functionalities and counterparrreactive groups that may reside on oligonucleotide tags or the molecules of interest. When the functionalitics and counterpart reactants are reacted together. after activation in some cases, a linking group is formed. Moreover, as-described more fully below, tags may be synthesized simultaneously with the molecules IO undergoing selection to form combinatorial chemical libraries.
Table IV

Reactive~lanct -,'onal_it~c and art ReacLrtts Heir Courttem a nd Resu_l~ Lj~~n-g Gmuns _ Reactive Counterpart Linking Funct~gnalitv Functionality Group _ -NH2 , -COOH -CO-NH--NH2 -NCO =NHCONH-~\ ~'\
-NH, - n!H N -NH
~ ~ ~ ~N--SH -C=C-CO- -S-C-C-CO
-NHS ~ -CHO -CH~NH
-NHS -S02C1 -SO~NH--OH -OP(NCH(CH3)~)~ -OP(=O)(O)O--OP(=O)(O)S -NHC(=O)CH~Br -NHC(=O)CH~SP(=O)(0)O--IZ_ . , . . _ ..

A class of molecules particularly convenient for the generation of combinatorial chemical libraries includes linear.polymeric molecules of the form:
_ (M_L)n _ wherein L is a linker moiety and M is a monomer that may selected from a wide range of chemical stFUCtures to provide a range of functions-from serving as an inert non-sterically hindering spacer moiety to providing a reactive functionality which can serve as a branching point to attach other components, a site for attaching labels; a site for attaching oligonucleotides or ocher binding polymers for hybridizing or binding to a therapeutic target: or as a site for attaching other groups for affecting solubility, promocian of duplex and/or triplex formation, such. as intercalatars, alkylating agents.. and the like. The sequence, and therefore composition, of such linear polymeric molecules may be encoded within a polynucleotide attached to the tag, as taught by Brenner and Lemer (cited above).
However, after a selection event. instead of amplifying then sequencing the tag of the selected molecule, the tag iuelf or an additional coding segment can be sequenced directly--using a so-called "single base" approach described below--after releasing the molecule of interest, e.g. by restriction digestion of a site engineered into the tag. Clearly, any molecule produced by a sequence of chemical reaction steps compatible with the ~ simultaneous synthesis of the tag moieties can be used in the generation of combinatorial libraries.
Conveniently there is a wide diversity of phosphate-linked monomers available for generaane combinatorial libraries. The following references disclose several phosphoramidice andlor hydrogen phosphonate monomers suitahle for use in the present '?5 invention and provide guidance for their synthesis and inclusion into oligonucleotides:
Newton et al. Nucleic Acids Research, 21: l I55-I 162 ( 1993); Griffin et al, J. Am. Chem.
Sot.. I I.I: 7976-7982 ( 1992): Jaschke et al. Tetrahedron Letters, 34: 301-3()4 (1992): Ma et al. International application PCT/CA92/OU423: Zon et al. International application PCT/L,'S90/06630: Durand et al. Nucleic Acids Research. 18: 6353-635y ( 1990):
Salunkhe et al. J. Am. Chem. Sot., t 14: 8768-8 772 ( 1992): Urdea et al, U.S.
patent 5,093.232: Ruth. L.J.S, patent 4.948,882: Cruickshanlc, U.S. patent 5,091,519;
Haralambidis et al. Nucleic Acids Research, l5: 4857-4876 ( 1987); and the like. More particularly. M may he a straight chain, cyclic, or branched organic molecular structure containing from 1 to 2U carbon atoms and from U to 10 heceroatoms selected from the group consisting of oxygen, nitrogen, and sulfur. Preferably, M is alkyl, alkoxy, alkenyl, or aryl cuntaining from 1 to 16' carbon atoms: a heteroc'ycle having from 3 to 8 carbon atoms and from 1 to 3 heteroatoms selected.from the group consisting of oxygen, nitrogen, and sulfur, glycosyl: or nucleosidyl. More preferably, M is alkyl, alkoxy, alkenyl, or aryl containing from 1 to 8 carbon atoms: glycosyl; or nucleosidyl.
Preferably. L is a,phosphorus(V) linking group which may be phosphodiester, phosphotriester. methyl or ethyl phosphonate, phosphorothioate phosphorodithioate, phosphoramidate, or the:like. Generally, linkages derived from phosphoramidite or hydrogen phosphonate precursors are preferred so that the linear polymeric units of the invention can be conveniently synthesized with commercial automated DNA
synthesizers, e.g. Applied Biosystems. Inc. (Foster City, CA) model 394, or the Like.
n may vary significantly depending on the nature of M and L. Usually, n varies from about 3 to about 100. When M_ is a nucleoside~or analog thereof or a nucleoside-sized monomer and L is a phosphorus(V) linkage, then n varies from about 12 to about I00: Preferably, when M is a nucleoside or analog thereof or a nucleoside-sized monomer and L is a phosphorus(V) linkage,. then n varies from about 12 to about 40.
Peptides are another preferred class of molecules to which tags of the invention are attached. Synthesis of peptide-oligoriucleotide conjugates which may be used in the invention is taught in Nielsen et al, J. Am. Chem. Sac.. I I5: 9812-981.3 ( 1993);
Haralambidis'et al (cited above) and International patent application PCT/AU88/004417;
Truffert et al, Tetrahedron Letters, 35: 2353-2356 ( 1994); de Ia Torre et aI, Tetrahedron Letters, 35: 2733-2736 ( 1994); and like references. Preferably, peptide-oligonucleotide conjugates are synthesized as described below. Peptides synthesized in accordance with the invention may consist of the natural amino acid monomers or non-natural monomers, including the D isomers of the natural amino acids and the like.
Combinatorial chemical libraries employing tags of the invention are preferably prepared by the method disclosed in Nielsen et a1 (cited above) and illustrated in Figure 4 for a particular embodiment. Briefly, a solid phase support, such as CPG, is derivatized with a cleavable-linl:er that is compatible with boat the chemistry employed to syitchesize the tads and the chemistry employed to synthesize the molecule that will undergo some 3U selection process. Preferably, tags are synthesised using phosphoramidite chemistry as described above and with the modifications recommended by Nielsen et al (cited above);
that is. DMT-5'-O-protected 3'-phosphocamidite-derivatized subunits having methyl-protected phosphice and phosphate moieties are added in each synthesis cycle.
Library compounds are preferably monomers having Fmoc--or equivalent--protecting groups masking the functionality to which successive monomer will be coupled. A
suitable linker for chemistries employing both DMT and Fmoc protecting groups (referred to herein as a sarcosinc linker) is disclosed by Brawn et al. J: Chem. Soc. Chem: Common..
1989: 891-893 .
. 14 .

Figure 4 illustrates a scheme for generating a combinatorial chemical library of peptides conjugated to ofigonucleotide tags. Solid phase support 200 is derivatiaed by s~rcosine linker 205 (exemplified in the formula below) as taught by NieIsen et a1 (cited above), which has an extended linking moiety to facilitate reagent access.
(CPG)-N'HC(O)CN(CHI)C(O)CH,CH,C(O)O(CH,)6NHC(O)CH,(O-DMT')NC(O)-CH,O(CH,CH,O>,CH,CH,u'HC(O)CH,O(CH,CH,4),CH,CN,NH-Fmoc 1 U Here "CPG" represents a controlled-pore glass support, "DMT" represents dimethoxytrityl, and "Fmoc:" represents 9-fluorenylmethoxycarbonyl.
In a preferred embodiment, an oli~onucleotide segment 214 is synthesized initially s0 that in double stranded form a restriction endonuclease site is provided for cleaving the library compound after sorting onto a microparticle, or like substrate_ Synthesis proceeds by 1.5 successive aleernative additions of subunits S 1, S2, S3, and the like, to form tag 212, and their corresponding library compound monomers AI, A2, A3, and the like, to form library compound 216. A "split and mix" technique is employed to generate diversity.
The subunits in a minimally cross-hybridizing set code for the monomer added in the library compound. Thus, a nine word set can unambiguously encode library 20 compounds constructed from nine monomers. If some ambiguity is acceptable, then a single subunit may encode more than one monomer.
After synthesis is completed, the product is cleaved and deprotected (220) to form tagged~library compound 225, which then undergoes selection 230, e.g. binding to a predetermined target 235, such as a protein. The subset of library compounds recovered 25 from selection process 230 is then sorted (240) onto a solid phase support 24S via their , iag moieties (there complementary subunits and nucleotides are shown in italics). After Iigating oligonucleotide splint 242 to tag complement 25U to form restriction site 255, the conjugate is digested with the corresponding restriction endonuclease to cleave the library compound, a peptide in the example of Figure 4, from the oligonucleotide moiety. The 3U sequence of the tag, and hence the identity of the library compound. is then determined by the preferred single base sequencing technique of the invention, described below.
,S~lid~hase Su~~orts Solid phase supports for use with the invention may have a wide variety of forms, 35 including microparticles. beads, and membranes; slides, plates, micromachined chips, and the Iike. Likewise, solid phase supports of the invention may comprise avvide variety of compositions, including glass. plastic. silicon. alkanethiolate-derivatized gold. cellulose.
low cross-linked and high cross-Iirtled polystyrene, silica gel, polyamide.
and the like.
1~ -.

Preferably..either a population of discrete particles are employed such that each has a uniform coating, ur population, of complementary sequences of the same tag (and no other), or a single or a few supports are employed with spatially discrete regions each, containing a uniform coating, or population, of complementary sequences to the same tag (and ~no other). In the latter embodiment, the area of the regions may vary according to particular applications: usually, the regions range in area from several ttm2, e.g: 3-S, to several hundred ~tm2, e.g. 100-500. Preferably, such regions are spatially discrete so that signals generated by events, e.g. fluorescent emissions, at adjacent regions can be resolved by the detection system being employed. In some applications, it may be desirable to 1U have regions with uniform coatings of more than one tag complement, e.g.
for simultaneous sequence analysis, or for bringing separately~tagged molecules into close proximity.
Tag complements may he used with the solid phase support that they are synthesized on, or they may be separately synthesized and attached to a solid phase I S support for use, e.g. as disclosed by Lund et al. Nucleic Acids Research, 16: 10861-1088() ( 1988): Albretseti et al, Anal. Biochem.. 189: 40-50 ( 1990); Wolf et al.
Nucleic Acids Research. 15: 2911--2926 (1987); or Ghosh et al, Nucleic Acids Research, 15:

( I987). Preferably, tag complements are synthesized on and used with the same solid phase support, which may comprise a variety of forms and include a variety of linking 20 moieties. Such suppoets may comprise microparticles or arrays, or matrices, of regions where uniform populations of tag complements are synthesized. A wide variety of microparticle supports may be used with the invention, including microparticles made of conuolled pore glass (CPGj, highly cross-linked polystyrene, acrylic, copolymers, cellulose, nylon, dextrin, latex, polyacrolein, and the like, disclosed in the following 25 exemplary references: Meth. Enzymol., Section A, pages l I-147, voL,44 (Academic Press, New York, 1976): U.S. patents 4,678.814: 4,4I3,070: and 4,046:720; and Pon. . .
Chapter 19. in Agrawal. editor, Methods in Molecular Biology. Vol. 20, (Humans Press, Totowa, NJ. I993). Microparticle supports further include commercially available nucleoside-derivatized CPG and polystyrene heads (e.g. available from Applied 3() Biosystems, Foster City. CA): derivatized magnetic beads: polystyrene grafted with polyethylene glycol (e.g.. TentaGelTh'1. Rapp Polymere. Tubingen Germany): and the like.
Selection of the support characteristics, such as material, porosity, size, shape, and the like.: and the type of linking moiety employed depends on the conditions under which the tags are used. Fur example. in applications involving successive processing with enzymes;
35 supports and linkers that minimize steric hindrance of the enzymes and that facilitate access to substrate are preferred. Other important factors to be considered in selecting the most appropriate microparticle suppprt include size uniformity. efficiency as a synthesis support. degree u~ which surface aria known. and optical properties, e.g. as explain more fully below, clear smooth beads provide instrumeritational advantages when handling large numbers of beads on a surface.
Exemplary linking moieties for attaching and/or synthesizing tags on microparticle surfaces are disclosed in Pon et al, Biotechniques, 6:76$-775 (1988); Webb, U.S. patent 4,659,774: Barany et al, International patent application PCTICTS91/06103;
Brown et al. 7.
Chem. Sot. C.ommun., 1989: 891-893: Damha et al, Nucleic Acids Research, 18:

3821 (1990): Beanie et al, Clinical Chemistry, 39: 719-722 (I993): Maskos and Southern, Nucleic Acids Research, 20: 1679-1684 (1992); and the like.
As mentioned above, tag complements may also be synthesized on a single (or a 1U few) solid phase support to form an array of regions uniformly coated with tag complements. That is, within each region in such an array the same tai cotoplement is synthesized. Techniques for synthesizing such arrays are disclosed in McGaII
et al, International application PCT/US93/03767; Pease. et al,.Proc. Natl. Acad.
Sci., 91: 5022-5026 ( 1994): Southern and Maskos, International application PCT/GB89/01114;
Maskos 15 and Southern (cited ahovc): Southern et al: Genomics. I 3: I (H)R-1 l) 17 ( 1992): and Maskos and Southern. Nucleic Acids Research. 21: 4663-4669 ( 1993).
Preferably, the invention is implemented with microparticles pr beads uniformly coated with complements of the same tag sequence. Microparticle supports and methods of covaleritly or noncovalently linking oligonucleotides to their surfaces are well.known, 20 as exemplified by the following references: Beaucage and Iyer (cited above):Gait, editor, Oligonucleotide Synthesis: A Practical Approach (IRL Press, Oxford. 1984): and the references cited above. Generally, the size and shape of a microparticle is not critieal:-however: microparticles in the size range of a few, e.g. 1-2, to several hundred, e.g. 200-1000 ~tm diameter are preferable, as they facilitate the construction and manipulation of 35 large repertoires of oligonucleotide tags with minimal reagent and sample usage.
In some preferred applications, commercially available controlled-pore glass (CPG) or polystyrene supports are employed as solid phase supports in the invention.
Such supports come available with base-labile linkers and initial nucleosides attached; e.g.
Applied Biosystems (Foster City, CA). Preferably., microparticles having pore size .
3()~ between 5(X) and 1(X1(> angstroms are employed.
In uther preferred applications; non-porous microparticles are employed for their optical properties. which may be advantageously used when tracking large numbers of microparticles on planar supports, such as a microscope slide. Particularly preferred non-porous microparticles are the glycidal methacrylate (GMA) beads available from Bangs 3S Laboratories (Carmel. IN). Such microparticles are useful in a variety of sizes and derivatized with a variety of linkage groups for synthesizing. tags or tag complements.
Preferably, for massively parallel manipulations of tagged micropanicles; 6 p.m diameter.
GMA beads are employed.
_17_ Attaching Tar=aet Polynucleatides tos~,icrQOarticles An important aspect of the invention is the sorting of populations of identical polynucleotides, e.g. from a cDNA 3ibrary, and their attachment to microparricles or separate regions of a solid phase support such that each microparticle or region has only a single kind of polynucleotide: This latter condition can be essentially rnet by Iigating a repertoire of tags to a population of polynucleotides: The ligation products are then cloned, amplified, and sampled. Provided that the sample is sufficiently small, as explained more fully below, substantially all of the tag-polynucleotides conjugates of the resulting library will be unique. That is, each polynucleotide will have a unique tag, and vice versa.
The polynucleotides are then sorted by hybridizing the tags to their complements A repertoire of oligonucleotide tags can he Iigated to a population of polynucleocides in a number of ways, such as through direct enzymatic ligacion.
amplification, e.g. via PCR. using primers containing the tag sequences, and the like. The initial ligating step produces a very large population of tag-polynucleotide conjugates such that a single tag is generally attached to many different polynucleotides.
However, by takinga sufficiently small sample of the conjugates, the probability of obtaining "doubles,"
i.e. the same tag on two different polynucleotides, can be made negligible.
(Note that it is also possible ~to obtain different tags with the same polynueleotide in a sample. This case simply leads to a polynucleotide being processed, e.g. sequenced, twice, so is usually not problematic). As explain more fully below, the probability of obtaining a double in a sample can be estimated by a Poisson distribution since the number of conjugates in a sample will be large, e:g. on the order of thousands or more, and the probability of selecting a particular tag will be small because' the tag repertoire is large, e.g. on the order of tens of thousand or more. Generally, the larger the sample the greater the probability of obtaining a double. Thus, a design trade-off exists between selecting a large sample of tag=polynucleotide conjugates--which, for example, ensures adequate coverage of a target polynucleotide in a shotgun sequencing operation, and selecting a small sample which ensures that a minimal number of doubles will be present. In most embodiments, the presence of doubles merely adds an additional source of noise or. in the case of sequencing, a minor complication in scanning and signal processing, as microparticles giving multiple fluorescent signals can simply be ignored. As used herein, the term "substantially all" in reference to attaching tags to molecules, especially polynucleotides. is meant to reflect the_statistical nature of the sampling procedure employed to obt.airt a population of tag-molecule conjugates essentially free of doubles. The meaning of substantially all in terms of actual percentages of tag-molecule conjugates depends on how the tags are being employed. Preferably, for nucleic acid seduencing, substantially all means that at least eighty percent of the tags have unique pulynucleotides attached. More -18=

preferably, it means that at least ninety percent of the tags have unique polynucleotides attached. Scull more preferably, it means that at least ninety-five percent of the tags have unique polynucleotides attached. And, most preferably, it means that at least ninety-nine percent of the tags have unique polynucleotides attached.
Preferably, when the population of polynucleotides consists of messenger RNA
(mRNA?, oligonucleotides tags are attached by reverse transcribing the mRNA
with a set of primers containing complements of tag sequences. An exemplary set of such primers could have the following sequence:
I O 5 ' -mRNA- [ A] n . _ 3 , [T]19GG[W,W,W,C]gACCAGCTGATC-5'-biotin where "[W,W,W,CJ9" represents the sequence of an oligonucleotide tag of nine subunits I$ c~f four nucleotides each and "[W,W,W,CJ" represents the subunit sequences listed above, i.e. "W" represents T or A. The underlined sequences identify an optional restriction endonuclease site that can be used to release the polynucleotide from attachment to a solid phase support via the biotin, if one is employed. For the above primer, the complement attached to a microparticle could have the form:
5'-[G,W,W,W]9TGG-linker-microparticle After reverse transcription, the mRNA is removed, e.g. by RNase H digestion;
and the second strand of the cDNA is synthesized us;ng, for example, a primer of the following form:
5'-NRRGATCYNNN-3' where N is any one of A. T. G. or C: R is a purine-containing nucleotide. and Y is a pyrimidine-containing nucleotide. This particular primer creates a Bst Y 1 restriction site in the resulting double stranded DNA which, together with the Sal I
site.;facili,tates cloning into a vector with, for example. Bam HI and Xha I sites. After Bst Y 1 and Sal I
digestion, the exemplary conjugate would have the form:
5'-RCGACCA[C,W,W,W)gGG[T]Z9- cDNA -NNNR
GGT [G; W, W, W] 9CC [A] 19- rDNA -NND1'~CTAG-5 ' 9.

Preferably,, when the ligase-based method of sequencing is employed, the Bst Yl and SaI I
digested fragments are cloned into a Bam HI-/Xho I-digested vector having the following single-copy.restriction sites:
5'-GAGGATGCCTTTATGGATCCAS".TCGAGATCCCAATCCA-3' FokT BamHI XhoI
This adds 'the Fok I site which will allow initiation of the sequencing process discussed more fully below. .
A general method for exposing the single stranded tag after amplification involves digesting a target polynucleotide-containing conjugate with the S'-~3' exonuclease activity of T4 DNA polymerise, or a like enzyme. When used in the presence of a single nucleDSide triphosphate; such a polymerise will cleave nucleotides from 3' recessed ends 'present on the. ntm-template strand of a double stranded fragment until a complement of the single nucleoside triphosphate is reached on the template stnlnd. When such a nucleotide is reached the 5'--~3' digestion effectively ceases, as the polymerase's extension activity adds nucleotides at a higher rate than the excision activity removes nucleotides.
Consequently, tags constructed with three nucleotides are readily prepared for loading oneo solid phase supports.
The technique may also be used to preferentially methylate interior Fok I
sites of a target polynucleotide while leaving a single Fok I site at the terminus of the polynucleotide unmethylated. First, the terminal Fok I site is rendered single stranded using a polymerise with deoxycytidine triPhosphate. The double stranded portion of the fragment is then methylated, after which the single scranded.tertninus is filled in with a DNA
polymerise in.
the presence of all four nucleoside triphosphates, thereby regewrating the Fok I site.
Clearly, this procedure can be generalized to endonucIeases other than Fok I.
After the uligonucleotide tags are prepared for specific hybridization, e.g.
by rendering them single stranded as described above. the polynucleotides are mixed with microparticles containing the complementary sequences of the tags under conditions that favor the formation of perfectly matched duplexes between the tags and their complements. There is extensive guidance in the literature for creating these conditions.

-20~

Exemplary references providing such guidance include Wetmur;'Critical Reviews in Biochemistry and MolecularBiolagy, 26: 227-259 (1991); Sambrook et al, Molecular Cloning: A Laboratory Manual, 2nd Edition (Cold Spring Harbor Laboratory, New York, 1989); and the like. Preferably, the hybridization 'conditions are sufficiently stringent so that only perfectly matched sequences form stable duplexes. Under such conditions the polynucleotides specifically hybridized through their tags are ligated to the complementary sequences attached to the microparticles. Finally, the microparticles are washed to remove unligated polynucleotides.
When CPG micmparticles conventionally employed as synthesis supports are used, the density of tag complements on the microparticie surface is typically greater than that necessary for some sequencing operations. That is, in sequencing approaches that require successive treatment of the attached polynucleotides with a variety of enzymes, densely spaced polynucleotides may tend to inhibit access of the relatively bulky enzymes to the potynucleotides. In such cases, the polynucleoiides are preferably mixed with the microparticles so that tag complements are present in significant excess, e.g.
from 10:1 to 100: I, or greater, over the polynucIeotides. This ensures that the density of polynucleotides on the microparticie surface will not be so high as to inhibit enzyme access. Preferably, the average inter-polynucleotide spacing on the microparticle surface is on the order of 30-100 nm. Guidance in selecting ratios for standard CPG
supports and BallotiniTM beads-(a type of solid glass support) is found in Maskos and Southern, Nucleic Acids Research. 20: 1679-1684 ( 1992). Preferably, for sequencing applications, standard CPG beads of diameter in the range of 20-50 ~m are loaded with about 105 polynucleotides, and GMA beads of diameter in the range of 5-10 ~tm are loaded with a few tens of thousand polynucleotide, e.g. 4 x 104 to 6 x 104.
The above method may be used to fingerprint mRNA populations when coupled with the parallel sequencing methodology described below. Partial sequence information _ is obtained simultaneously from a large sample, e.g. ten to a hundred thousand, of cDNAs attached to separate microparticles as described in the above method. The frequency distribution of partial sequences can identify mRNA populations from different cell or tissue types, as well as from diseased tissues, such as cancers. Such mRNA
fingerprints are useful in monitoring and diagnosing disease states, e:g. International application , PCT/LrS95121944, -which describes the use of express sequence tags (ESTs) for the same purpose.
~~gle Bade DNA Scn ~ n in The present invention can be employed with conventional, methods of DNA
sequencing, e.e. as disclosed by Hultman et al, Nucleic Acids Research. 17:

( 1989. However, for parallel, or simultaneous, sequencing of multiple polynucieotides, a DNA sequencing methodology is preferred that requires neither electrophoretic separation of closely sized DNA fragments rlor analysis of cleaved nucleotides by a separate analytical procedure; as in peptide sequencing. Preferably, the methodology permits the stepwise identification of nucleotides, usually one at a time, in a sequence through successive cycles of treatment and detection. Such methodologies are referred to herein as "single base"
sequencing methods. Single base approaches are disclosed- in the f0 25 Y , 35' _ _ -21 a-following references: Cheeseman, U.S. patent 5.302,509: Tsien et aI, International application WO 91/06678; Rusenthal et al, International application WO
93121340;
Canard et al. Gene: 148: 1-b ( 1994): and Metzlcer et al. Nucleic Acids Research, 22:
4259-4267 (1994).
A "single base" method of DNA sequencing which is suitable for use with the present invention and which requires no eleccrophoretic separation of DNA
fragments is described in International application PCT/US95/03678. The method comprises the following steps: (a) ligating a probe to an end of the polynucleatide having a providing strand to farm a ligated complex. the probe having a complementary providing strand to that of the polynucleotide and the probe having a nuclease recognition site;
(b) removing unligated probe from the ligated complex; (c) identifying one or more nucleotides in the providing strand of the polynucleotide by the identity of the ligated probe;
(d) cleaving the ligated complex with a nuclease: and (e) repeating steps (a) through (d) until the nucleotide sequence of the palynucleotide is determined. As is described more fully below, identifying the one or mare nucleotides can he carried out either before or after cleavage of the ligated complex from the target poiynucleotide. Preferably, whenever natural protein endonucleases are employed, the method further includes a step of methylating the target polynucleotide at the start of a sequencing operation.
An important feature of the method is the probe ligated to the target polynucleotide: A preferred forrit of the probes is illustrated in Figure la.
Generally, the probes are double stranded DNA with a providing strand at one end 10. The probes contain at least one nuclease recognition site 12 and a..spacer region 14 between the , rec~gnitian site and the providing end 10. Preferably, probes also include a label 16T
which in this particular embodiment is illustrated at the end apposite of the providing strand. The probes may be labeled by a variety of means and at a variety of locations, the only restriction being that the labeling means selected does not interfere with the Iigatian step or with the-recognition of the probe by the nuclease.
It is not critical whether providing strand 10 of the probe is a 5' or 3' end.
However. it is important that the protruding strands of the target polynucleotide and probes he capable of farming perfectly matched duplexes to allow Car specific Iigation. If the protruding strands of the target polynucleotide and probe are different lengths the resulting gap can be filled in by a palymerase prior to ligatian, e.g. as in "gap LCR"
disclosed in Backman et al. European patent application 9110(?y59.5.
Preferably. the number of nucleotides in the respective providing strands are the same so that both strands-of the probe and target polynucleatide are capable of being ligated without a filling step. Preferably, the protruding strand of the probe is from 2 to 6 nucleotides long. As indicated helaw. the greater the length of the protruding strand. the greater the complexity - 22. -of the probe mixture that is applied to the target polynucleotide during each Iigation and cleavage cycle.
The complementary strands of the probes are conveniently synthesized on an automated DNA synthesizer, e.g. an Applied Biosystems, Inc. (Foster City, California) ' model 392 or 394 DNA/RNA Synthesizer, using standard chemistries. After synthesis, the complementary strands are combined to form a double stranded probe. Generally, the providing strand of a probe is synthesized as a mixture, so that every possible sequence is represented in the providing portion. For example, if the providing portion consisted of four nucleotides, in one embodiment four mixtures are prepared a_s follows:

' X~X2 ... XiNNNA, _ X1X2 ... XiNNNC, XIXz ... XiNNNG, and X1X2 ... XiNNNT
where the "NNNs" represent every possible 3-mer and the "Xs" represent the duplex forming portion of the strand. Thus, each of the four probes listed above contains 43 or 64 distinct sequences; or, in other words. each of the four probes has a degeneracy of 64.
For example, X1X2 ... XiNNNA contains the following sequences:

XIX2 ... XiAAAA

X1X~ ... XiAACA

2S XZX2 ... XiAAGA

X1X2 ... XiAATA

X1X2 ... XiACAA

3O .
X1X2 ... XiTGTA

X1X2 ... XiTTAA

35 X1X2 ... XiTTCA
' X~X2 . . XiTTGA
.

X1X2 ... XiTTTA

Such mixtures are readily synthesized using well known techniques, e.g. as disclosed in Telenius et al (cited above). Generally, these techniques simply ca71 for the application of mixtures of the activated monomers to the growing oligonucleotide during the coupling steps where one desires to introduce the degeneracy. In some embodiments it may be desirable to reduce the degeneracy of the probes. This can be accomplished using degeneracy reducing analogs, such as deoxyinosine, 2-aminopurine; or the like, e.g. as taught in Kong Thoo Lin et al, Nucleic Acids Research, 20: 5149-5152, or by U.S. patent 5.002.867.
Preferably, for oligonucleotides with phosphodiester linkages, the duplex forming region of a probe is between about I2 w about 30 basepairs in length: more preferably, its length is between about 15 to about 25 basepairs.
When conventional ligases are employed in the invention, as described more fully belong, the S' end of the probe may be phosphorylated in some embodiments. A
5' monophosphate can be attached tp a second otigonucleotide either chemically or enzymatically with a kinase, e.g. Sambrook et al (cited above). Chemical phosphorylation is described by Horn and,Urdea. Tetrahedron Lett., 27: 4705 ( 1986), and reagents for carrying out the disclosed protocols are commercially available, e.g. 5' Phosphate-ONTM
from Clontech Laboratories (Palo Alto, California). Thus, in some embodiments, probes may have the forth:
5 ' -X 1.X2 , . . X i'I"I'GA
YlY2 ~ ~ . YiP
where the Y's are the complementary nucleotides of the X's and "p" is a monophosphate group.
The shove probes can be labeled in a variety.of ways. including the direct or indirect attachment of radioactive moieties, fluorescent moieties, colorimetric moieties, chemiluminescent markers, and the like. Many comprehensive reviews of methodologies for labeling DNA and constructing DNA pmbes provide guidance applicable to 3() corisweting probes of the present invention. Such reviews include Kricka.
editor, Nonisotopic DNA Probe Techniques (Academic Press, San Diegu, 1992): Haugland, Handbocok of Fluorescent Probes and Research Chemicals (Molecular Probes, Inc., Eugene, 1992): Kelley and Manak, DNA Probes. 2nd Edition (Stockton Press, New York.
1993): and Ec;kscein, editor. Oligonucleotides and Analogues: A Practical Approach (IRL
3S Press. Oxford, 1991 ): Kessler, editor. Nonradioactive Labeling and Detecuon of Biomolecules (Springer-Verlag, Berlin, 1992): Wetmur (cited above); and the-Iike.
Preferably, the probes are labeled with one or more fluorescent dyes, e.g. as disci-~~sed by Menehen et al. U.S. patent 5.188.934: Begot et al International application PCT/US9U/()5565.
-2.4-In accordance with the method, a probe is ligated to an end of a target polynucleotide to form a ligated complex in each cycle of ligation and cleavage. The ligated complex is the double stranded structure farmed after the providing strands of the target polynucleotide and probe anneal and at least one pair of the identically oriented strands of the probe and target are ligated, i.e. are caused to be covalently linked to one ' another. Ligation can be accomplished either enzymatically or chemically.
Chemical ligation methods are well known in the art, e.g. Ferris et al, Nucleosides &
Nucleotides, 8: 407-414 ( 1989); Shabarova et al, Nucleic Acids Research, 19: 4247-4251 ( 1991 ); and the like. Preferably, however, ligation is carried out enzymatically using a lipase in a standard protocol, Many ligases are known and are suitable for use in the invention, e:g.
Lehman. Science, 186: 790-797 ( 1974); Engler et al, DNA Ligases, pages 3-30 in Boyer, editor, The Enzymes, Vol. 15B (Academic Press, New York, 1982): and the like.
Preferred ligases include T4 DNA lipase, T7 DNA lipase, E. coli DNA lipase, Taq lipase, Pfu lipase: and Tth lipase. Protocols for their use are well known, e.g.
Sambrook et al (cited above): Barony. PCR Methods and Applications, 1: 5-16 (1991); Marsh et aI, Strategies; 5: 73-76 (1992); and the like. Generally, ligases require that a 5' phosphate group he present for ligation to the 3' hydroxyl of an abutting strand. This is conveniently provided for at least one strand of the target polynucleotide by selecting a nuclease which leaves a 5' phosphate, e.g. as Fok I.
In an embodiment of the sequencing method employing unphosphorylated probes,' the step of ligating includes (r) ligating the probe to the target polynucleotide with a lipase so that a ligated complex is formed having a nick on one strand, (ii) phosphorylating the 5' hydroxyl at the nick with a kinase using conventional protocols, e.g. Sambrook et al (cited, above), and (iii) ligating again to covalently join the strands at the nick, i.e. to remove.the nick.
Ap~?aatus for OhseryinQ Fin vmatic Processes and/or Binding Events at Micronarcicle Surfaces An objective of the invention is to sort identical molecules, particularly 3(1 polynucleotides, onto the surfaces of microparticles by the specific hybridization of tags and their complements. Once such sorting has taken place, the presence of she molecules or operations performed on them can be detected in a number of ways depending on the nature of the tagged molecule. whether microparticles are detected separately or in "batches," whether repeated measurements are desired, and the like. Typically, the sorted molecules are exposed tt~ ligands for binding, e.g. in drug development, or are subjected chemical or enzymatic processes, e.g. in polynucleotide sequencing. In both of these uses ' it is often desirable to simultaneously observe signals corresponding to such events or processes on large numbers of microparticles._ Microparticles carrying sorted molecules (referred to herein as "loaded" microparticles) lend themselves to such large scale parallel operations, e.g. as demonstrated by Lam et al (cited above).
.Preferably, whenever light-generating signals, e.g. chemiluminescent, fluorescent, or the like, are employed to detect events or processes, loaded microparticles are spread on a planar substrate, e.g. a glass slide, for examination with a scanning system, such as described in International patent applications PCT/US91/09217, PCT/NL90/00081, and PCT/US95/01886. The scanning system should be able to reproducibly scan the substrate and to define the positions of each microparticle in a predetermined region by way of a coordinate system. In polynucleotide sequencing applications, it is important that the positional identification of microparticles be repeatable in successive scan steps.
Such scanning systems may be constructed from commercially available components, e.g. x-y translation table controlled by a digital computer used with a detection system comprising one or more photomultiplier tubes, or alternatively, a ~CCD
array, and appropriate optics, e.g. for exciting, collecting, and sorting fluorescent signals.
In some embodiments a confocal optical system may be desirable. An exemplary scanning system suitable for use in four-color sequencing is illustrated diagrammatically in Figure 5.
Substrate 300, e.g. a microscope slide with fixed microparticles, is placed on x-y translation table 302, which is connected to and controlled by an appropriately programmed digital computer 304 which may be any of a variety of commercially available personal computers, e.g. 486-based machines or PowerPCTM model 7100 or 8100 available Form Apple Computer (Cupertino, CA). Computer software for table translation and data collection functions can be provided by commercially available laboratory software, such as Lab WindowsTM, available from National Instruments.
Substrate 300 and table 302 are operationally associated with microscope 306 having one or more objective lenses 308 which are capable of collecting and delivering light to microparticles fixed to substrate 300. Excitation beam 310 from light source 312, which is preferably a laser, is directed to beam splitter 314, e.g. a dichroic mirror. which re-directs the beam through microscope 306 and objective lens 308 which, in turn, focuses the beam onto substrate 300. Lens 30R collects fluorescence 316 emitted from the 3U microparticles and directs it through beam splittew314 to signal distribution optics 318 which, in turn, directs fluorescence to one or more suitable opto-electronic devices for convening some fluorescence characteristic, e.g. intensity, lifetime, or the like, to an electrical signal. Signal distribution optics 318 may comprise a variety of components standard in the art, such as bandpass filters, fiber optics, rotating mirrors, fixed position mirrors and lenses, diffraction gratings, and the like. As illustrated in Figure 5, signal distribution optics 318 directs fluorescence 316 to four separate photomultip.lier tubes.
330. 332. 334..and 336. whose output is then directed uopre-amps and photon counters 35U. 352. 354. and 356. The output of the photon counters is collected by computer 304.

where it can be stored, analyzed, and viewed on video 360. Alternatively., signal distribution optics 318 could be a diffraction gracing which directs fluorescent signal 318 onto a CCD array.
The stability and reproducibility of the positional localization in scanning will determine, to a large extent, the resolution for separating closely spaced microparticles.
Preferably, the scanning systems should be capable of resolving closely spaced micropartieles, e.g. separated by a particle diameter or less. Thus, for most applications, - -e.g. using CPG microparticles, the scanning system should at least have the capability of resolving objects on the order of 10-100 ltm. Even higher resolution may be desirable in some embodiments,-but with increase resolution, the time required to fully scan a substrate . will increase: thus, in some embodiments a compromise may have to be made between speed and resolution. Increases in scanning time can be achieved by a system which only scans positions where microparticles are known to be located, e.g from an initial full scan.
Preferably, microparticle size and scanning system resolution are selected to permit IS resolution of fluorescently labeled microparticles randomly disposed on a plane at a density between about ten thousand to one hundred thousand microparticles per cm2. -In sequencing applications, loaded microparticles can be fixed to the surface of a substrate in variety of ways. The fixation should be strong enough to allow the microparticles to undergo successive cycles of reagent exposure and washing without significant loss. When the substrate is glass, its surface may be derivatized with an .
alkylamino-linker using commercially available reagents, e.g. Pierce Chemical, which in cum may be cross-linked to avidin, again using conventional chemistries, to form an avidinated surface. Biotin moieties can be introduced to the loaded microparticles'in a number of ways. For example, a fraction, e.g. 10-15 percent, of the cloning vectors used to attach tags to polynucleotides are engineered to contain a unique restriction site (providing sticky ends cm digestion) immediately adjacent to the polynucleotide insert at an end of the polynucleotide opposite of the tag. The site is excised with the polynucleotide and tag for loading onto microparticles. After loading, about percent of the loaded polynucleotides will possess the unique restriction site distal from 3() the microparticle surface. After digestion with the associated restriction endonuclease, an appropriate double stranded adaptar containing a biotin moiety is Iigated to the sticky end.
The resulting microparticles are then spread on the avidinated glass surface where they become fixed via the biotin-avidin linkages.
Alternatively and preferably when sequencing by ligation is employed, in the initial ligauan step a mixture of probes is applied to the loaded microparticle: a fraction of the probes contain a type Its restriction recognition site, as required by the.sequencing method, and a fraction of the probes have no such recognition site, but instead contain a biotin moiety at its non-liga(ing end. Preferably, the mixture comprises about percent of the biotinylated probe.
In still another alternative, when DNA-loaded microparticles are applied to a glass substrate, the DNA may nonspecifically adsorb to the glass surface upon several hours, e.g. 24 hours, incubation to create a bond sufficiently strong to permit repeated exposures to reagents and washes without significant loss of microparticles. Preferably, such a glass substrate is a flow cell, which may comprise a channel etched in a glass slide. Preferably, such n channel is closed so that fluids may he pumped through it and has a depth sufficiently close to the diameter of the microparticles so that a monolayer of microparticles is trapped within a defined observation region.
Parallel Sei,~ ne cing The tagging system of the invention can be used with single base sequencing methods to sequence polynucleotides up to several kilobases in length. The tagging system permits many thousands of fragments of a target polynucleotide to be sorted onto one or more solid phase supports and sequenced simultaneously. In accordance with a preferred implementation of the method; a portion of each sorted fragment is sequenced in a stepwise fashion on each of the many thousands of loaded microparticles which are fixed to a common substrate--such as a microscope slide--associated with a scanning system or an image analysis system, such as described above. The size of the portion of the fragments sequenced depends of several factors, such as the number of fragments generated and sorted, the length of the target polynucleotide, the speed and accuracy of the single hale method employed, the number of microparticles and/or discrete regions that may be monitored simultaneously: and the like. Preferably, from 12-50 bases are , identified at each microparticle or region: and more preferably. 18-30 bases are identified at each microparticle or region. With this information, the sequence of the target polynucleotide is determined by collating the 12-50 base fragments via their overlapping regions, e.g. as described in LT.S. patent 5.002.867. The following references provide additional guidance in determining the portion of the fragments that must be sequenced for successful reconstruction of a target polynucleotide of a given length: Lander and WatetTnan. Genomics. Z: 231-239 (1988): Drmanac et al. Genomics, 4: 114-128 (1989):
Bains. DNA Sequencing and Mapping. 4: 143-I50 (1993): Bains. Genomics, I.I:

( 1991 ): Drmanac et al, J. Biomolecular Structure and Dynamics. 8: 1085-1102 ( 1991 ):
and Pevzner. J. Biomolecular Structure and Dynamics. 7: 63-73 ( 1989).
Preferably, the length of the target polynucleotide is between 1 kilobase and 50 kilobases.
More preferably, the length is between 10 kilobases and~40 kilobases. Lander and Waterman (cited above) provide guidance concerning the relationship among the number of fragments that are sequenced (i.e. the sample size), the amount of sequence information obtained from each fragment, and the probability that the target polynucleotide can be reconstructed from the partial sequences without gaps, or "islands." For the present invention, maximal polynucleotide sizes that can be obtained for given sample sizes and sizes of fragment sequences are shown below:
Size of Sample Ap rox. maximal tar et polynucleotide length 30 baseslfragment ~0 baseslfragment 1,000 3 kilobases . -4 kilobases 10.000 23 kilobases 32 kilobases 20.000 40 kilobases 65 kilobases 30,000 60 kilobases 85 kilobases 100.000 180 kilobases 300 kilobases Fragments may be generated from a target polynucleotide in a variety of ways, including so-called "directed" approaches where one attempts to generate sets of fragments covering the target polynucleotide with minimal overlap, and so-called "shotgun" approaches where randomly overlapping fragments are generated.
Preferably, "shotgun" approaches to fragment generation are employed because of their simplicity and inherent redundancy. For example, randomly overlapping fragments that cover a target polynucIeotide are generated in the following conventional "shotgun"
sequencing protocol, e.g. as disclosed in Sambrook et al (cited above). As used herein, "cover' in this context means that every portion of the target polynucleotide sequence is represented in each size range, e.g. all fragments between 100 and 200 basepairs in length, of the generated fragments. Briefly, starting with a target potynucleotide as an insert in an appropriate cloning vector, e.g. h phage, the vector is expanded. purified and digested with the appropriate restriction enzymes to yield aboui 1U-15 ~tg of purified insert.
Typically. the protocol results in about 5l)n-10(~ subclones per microgram of starting DNA. The insert is separated from the vector fragments by preparative gel electrophoresis, removed from the gel by conventional methods. and resuspended in a standard buffer, such as TE (Tris-EDTA). The restticaon enzymes selected to excise the ?5 insert from the~vector preferably leave compatible sticky ends on the insert; so that the insert can be self-ligated.in preparation for generating randomly overlapping.
fragments.
As explained in Sambroak et al (cited above), the circularized DNA yields a better random distrihutian of fragments than linear DNA in the-fragmentation methods employed below.
. After self-ligacing the insert. e.g. with T4 ligase using conventional protocols, the purified 3U ligated insert is fragmented by a standard protocol, e.g. sonication or DNase I digestion in the presence of Mn+-''. After fragmentation the ends of the fragments are repair, e.g. as described in Sambrook et al (cited above), and the repaired fragments are separated by size using gel electrophoresis. Fragments in the 300-SUU basepair range are selected and eluted from the gel by conventional means, and ligated into a tag-carrying vector as described above to form a library of tag-fragment conjugates. ' As described above, a sample containing several thousand tag-fragment conjugates are taken from the library and expanded, after which the tag-fragment inserts are excised from the vector and-prepared for speck hybridization to the tag complements on microparticles, as described above. Depending of the size of the target polynucleotide, l0 multiple samples may be taken from the tag-fragment library and separately expanded, loaded onto microparticles and sequenced. The number of doubles selected will depend on the fraction of the tag repertoire represented in a sample. (The probability of obtaining triples--three different polynucleotides with the same tag-- or above can safely be ignored). As mEntioned above, the probability of doubles in a sample can be estimated 1 S from the Poisson distribution p(double)=m2e-m/2, where m is the fraction of the tag repertoire in the sample. Table V below lists probabilities of obtaining doubles in a sampte for given tag size, sample size, and repertoire diversity.
Table V

Number of Fraction of words in tag from Size of tag Size of repertoire Probability of 8 word set re noire sam to sam led double 7 '2.1 x 10 3000 1.43 x 10-- 10-8 1.68 x 107 3 x 104 1.78 x 10--~ 1.6 x 10-6 3000 1.78 x 10-4 ~ 1.6 x 10-8 9 ~ 1.~4 x 108 3 x lOS 2.24 x 10'~ 2.~ x 10-6 3 x 104 2.24 x 10''l 3.~ x 10'8 1.07 x 10y ' :~ x 106 2.8 x 10-~ 3.9 x 10-6 :~ x 10-5 ?.8 x 1 (1-'t . ~.9 x 10-8 In any case, the loaded micropanicles are then dispersed and fixed onto a glass microscope slide, preferably via an avidin-biotin coupling. Preferably. at least 15-2U
nucleotides of each of the random fragments are simultaneously sequenced with a single base method. The sequence of the target polynucleotide is then reconsweted by collating the partial sequences of the random fragments by way of their overlapping portions, using algorithms similar to those used for assembling.~ontigs, ur as developed for sequencing by hybridization, disclosed in the above references.

Ki~e for Implemgn_~~; the Method of the Invention The invention includes ki.cs for carrying out the various embodiments of the invention. Preferably, kits of the invention include a repertoire of tag complements attached to a solid phase support. Additionally, kits of the invention may include the corresponding repertoire of tags, e.g. as primers for amplifying the polynucleotides to be sorted or as elements of cloning vectors which can also be used to amplify the polynucleotides to be sorted. Preferably, the repertoire of tag complements are attached to micropanicles. Kits may also contain appropriate buffers for enzymatic processing, detection chemistries, e.g. fluorescent or chemiluminescent tags, and the like, instructions IO for use, processing enrymes, such as ligases; polymerises, transferases, and so on. In an important embodiment far sequencing, kits may also include substrates, such as a avidinated microscope slides, for fixing loaded microparticles for processing.
I~gntification of Novel PQlynucleotides in c A Libraries Novel polynucleotides in a cDNA library can be identified by constructing a library of cDNA molecules attached to microparticles, as described above. A Large fraction of the .library, or even the entire library, can then be partially sequenced in parallel. After isolation of mRNA, and perhaps normalization of the population as taught by Soares et al, 2() Proc. Natl. Acid. Sci., 91: 9228-9232 (1994), or like references, the following primer may by hybridized to the polyA tails for first strand synthesis with a reverse tianscriptase using conventional protocols:
5,_~A_(A]n _3.
(T]lg-(primer site]-GG[W,W,W,C]gACCAGCTGATC-5' where [W,W,W,C]g represents a tag as described above, "ACCAGCTGATC" is an optional seduence forming a restrictiori site in double stranded form, and "primer site" is a sequence common to all members of the library that is later used as a primer binding site 3t1 for amplifying polynucleotides of interest by PCR. , After reverse transcription and second strand synthesis by conventional techniques.
the double stranded fragments are insened into a cloning vector as described above and amplified. The amplified library is then sampled and the sample amplified. The cloning vectors from the amplified sample are isolated, and the tagged cDNA fragments excised and purified. After rendering the tag single stranded with a polymerise as described above, the fragments are methylated and Boned onto micrQpanicles in accordance with the invention. Preferably. as descrihed above. the cloning vector is constructed so that the tagged cDNAs can be excised with an endonuclease. such as Fe~l; I. that will allow immediate sequencing by the preferred single base method after sorting and ligation to microparticles.
Stepwise sequencing is then carried out simultaneously on the whole library, or ' one or more large fractions of the library, in accordance with the invention until a sufficient number of nucleotides are identified on each cDNA for unique representation in the genome of the organism from which the library is derived. For example, if the library .
is derived from mammalian mRNA then a randomly selected sequence 14-15 nucleotides long is expected to have unique representation among the 2-3 thousand megabases of the typical mammalian genome. Of course identification ~of far fewer nucleotides would be sufficient for unique representation in a library derived from bacteria, or other lower organisms. Preferably, at least 20-30 nucleotides are identified to ensure unique representation and to permit construction of a suitable primer as described below. The tabulated sequences may then be compared to known sequences to identify unique .
cDNAs.
Unique cDNAs are then isolated by conventional techniques, e.g. constructing a probe from the PCR amplicon produced with primers directed to the prime site and the portion of the cDNA whose sequence was determined. The probe may then be,used to identify the cDNA in a library using a conventional screening protocol.
Example I
$or ~ng Multiple Target Polypucl~,~tides Derived from pUC 19 A mixture of three target pulynucleotide-tag conjugates are ubtained as follows:
First, the following six oligonucleotides are synthesized and combined pairwise to form tag 1, tag 2. and tag 3:
5'-pTCGACC(wl)(w2)lw3)!wq)(w5)Iws)(w~)(wg)(wl)A
GG(**)(**)(**).(**)i**)(**)(**)(**)(**)TTCGAp-5.
3!) Tag 1 5'-pTCGACC(w6)(w~)twg)(wl)lw2)~(w6)(wq)(w2)(wl)A
GG(**) (**) i**) (**) (**) (**) (**) (**) (**)TTCGAp-5.
Tag 2 5'-pTCGACC(w~) (w2) !w?) (w1) !w5_) (wg) (w8) (wq) (wq)A
GG(**)(**)(**)(**)(**)!**)(**)(**)(**)TTCGAp-S.
Tag 3 where "p" indicates a monophosphate, the wi's represent the subunics define in Table I, and the terms "(**)" represent their respective complements. A pUCl9 is digested with Sal I and Hind III, the large fragment is purified, and separately ligated with tags 1, 2, and 3,, to form pUC 19-1, pUC 19-2, and pUC 19-3, respectively. The three recombinants are 5 separately amplified and isolated, after which pUCl9-1 is digested with Hind III and Aat I, pUCl9-2 is digested with Hind III and Ssp I, and pUCl9-3 is digested with Hind III and Xmn I. The small fragments are isolated using conventional protocols to give three double stranded fragments about 250, 375, and 575 basepairs in length, respectively, and each having a recessed 3' strand adjacent to the tag and a blunt or 3' protruding strand at 10 the opposite end. Approximately 12 nmoles of each fragment are mixed with 5 units T4 DNA polymerise in the manufacturer's recommended reaction buffer containing 331tM
deoxycytosine triphosphate. The reaction mixture is allowed to incubate at 37oC for 30 minutes, after which the reaction is stopped by placing on ice. The fragments are then purified by conventional means.
15 CPG microparticles (37-74 mm particle size, 500 angstrom pore size, Pierce Chemical) are derivatized with the linker disclosed by Maskos and Southern, Nucleic Acids Research, 20: 1679-1684 ( 1992). After separating. into three aliquots, the complements of tags 1. 2, and 3 are synthesized on the microparticles using a conventional automated DNA synthesizer, e.g. a model 392 DNA synthesizer (Applied Biosystems, 20 Foster City, CA). Approximately 1 mg of each of the differently derivatized microparticles are placed in separate vessels.
The T4 DNA polymerise-treated fragments excised from pUCl9-l, -2, and -3 are resuspended in 50 ~tL of the manufactures s recommended buffer for Taq DNA
lipase (New England Biolabs). The mixture is then equally divided among the three vessels 2~ containing the 1 mg each of derivatized CPG microparticles. 5 units of Taq DNA lipase is added to each vessel, after which they are incubated at 55oC for 15 minutes.
The reaction is stopped by placing on ice and the microparticles are washed several times by repeated centrifugation and resuspension in TE. Finally, the microparticles are resuspended in Nde I reaction huffer (New England Biolabs) where the attached polynucleotides are digested.
3U After separation from the micropanicles the polynucieotide fragments released by Nde I
digestion are fluorescently labeled by incubating with SequenaseTM DNA
polymerise and fluorescein labeled thymidine triphosphate (Applied Biosyscems. Foster City, CA)..The fragments are then separately analyzed on a nondenaturing polyacrylamide gel using an Applied Biosystems model 373 35 DNA sequencer.

Example B
Parallel Seouencingof SV40 Fragments A repertoire of 36-mer tags consisting of nine 4-nucleotide subunits selected from Table I is prepared by separately synthesizing tags and tag complements by a split and mix approach, as described above. The repertoire is synthesized so as to permit ligation.into a Sma I/Hind IIf digested M lamp 19. Thus, as in Example I, one set of oligonucleotides begins with the addition of A followed by nine rounds of split and mix synthesis wherein the oligonucleotide is extended subunit-wise by 3'-phosphoramidite derivatived 4-mers corresponding to the suhunits of Table I. The synthesis is then completed with the nucleotide-by-nucleotide addition of one half of the Sma I recognition site (GGG), two C's, and a 5'-monophosphace, e.g. via the Phosphate-ONTM reagent available from Clontech Laboratories (Palo Alto, CA). The other set of oligonucleotides begins with the addition of three C's (portion of the Sma I recognition site) and two G's, followed by nine rounds of split and mix synthesis wherein the oligonucleotide is extended by 3'-phosphoramidite derivatized 4-mers corresponding to the complements of the subunits of Table I.
Synthesis is completed by the nucleotide-by-nucleotide additiun of the Hind III
recognition site and a 5'-monophosphate. After separation from the synthesis supports the oligonucleotideg are mixed under conditions that permit formation of the following duplexes:
5'-pGGGCC'lwi)(wi)(wi)twi)(wi)(wi)(wi)(wi)(wi)A
CCCGG(**)(**)(**)t**)(**)(**)(**)(**)(**)TTCGAp-5.
The mixture of duplexes is then ligated into a Sma IlHind III-digested M13mp19. A
repertoire of tag complements are synthesized on CPG microparticles as described above.
Next the following adaptor is prepared which contains a Fok I site and portions of Eco RI and Sma I sites:
5'-pAATTCGGATGATGCATGCATCGACCC
G~TACTACGTACGTAGCTGGGp-5' Eco PI Fok I Sma I
The adaptor is ligated into the Eco RIJSma I digested M 13 described above.
_ Separately. SV40 DNA is fragmented by sonication following the protocol set forth in Sambrook et al (cited above). The resulting fragments are repaired using standard protocols and separated by size. Fragments in, the range of 300-500 basepairs are selected and li~ated into the Sma I digested M 13 described above to form a library of fragment-tag conjugates, which is then amplified. A sample containing several thousand different -34-.

fragment-tag conjugates is taken from the library, further amplified, and the fragment-tag inserts are excised by digesting with Eco RI and Hind III. The excised fragment-tag conjugates are treated with T4 DNA polymerise in the presence of deoxycytidine triphosphate, as described in Example I, to expose the oligonucleotide tags for specific hybridization to the CPG microparticles.
After hybridization and ligation, as described in Example I, the loaded microparticles are treated with Fok I to produce a 4-nucleotide protruding strand of a predetermined sequence. A 10:1 mixture (probe l:probe 2) of the following probes are ligated to the polynucleotides on microparticles. ' Probe 1 FAM- ATCGGATGAC
TAGCCTACTGAGCT
Probe 2 biotin- ATCGGATGAC
TAGCCTACTGAGCT
FAM represents a fluorescein dye attached to the 5'-hydroxyl of the top strand of Probe 1 through an aminophosphate linker available from Applied Biosystems (Aminolinker). The biotin may also be attached through an Aminolinker moiety and optionally may be further 20 extended via polyethylene oxide linkers, e.g. Jaschke et al (cited above).
The loaded microparticles are then deposited on the surface of an avidinated glass slide to which and from which reagents and wash solutions can be delivered and removed.
The avidinated slide with the attached microparticles is examined with a scanning fluorescent microscope (e.g. Zeiss AxioskopTM equipped with a Newport Model motion controller; a Spectra-Physics Model 2020 argon ion laser producing a 488 nm excitation beam, and a 520 nm long-pass emission filter, or like apparatus).
The excitation beam and fluorescent emissions are delivered and collected, respectively, through the same objective lens. The excitation beam and collected fluorescence ire separated by a dichroic mirror which directs the collected fluorescence through a series of bandpass filters and to 3O photon-counting devices corresponding to the fluorophors being monitored, e.g.
comprising Hamamatsu model 9403-02 photomultipliers, a Stanford Research Systems model SR445 amplifier and model SR430 multichannel sealer, and digital computer, e.g. a 486-based computer. The computer generates a two dimensional map of the slide which registers the positions of the microparticles.
35 After cleavage with Fok I to remove the initial probe, the polynucleotides on the attached microparticles undergo 20 cycles of probe ligation, vrashing.
detection, cleavage.
and washing, in accordance with the preferred s-irrgle base sequencing methodology described below. Within each detection step, the scanning system records the fluorescent emission corresponding the base identified at each microparticle. Reactions and washes below are generally carried out with manufacturer's (New England Biolabs') recommended buffers for the enzymes employed, unless otherwise indicated. Standard buffers are also described in Sambrook et al (cited above).
The following four sets of mixed probes are provided for addition to the target polynucleotides:
TAMRA- ATCGGATGACATCAAC
TAGCCTACTGTAGTTGANNN
FAM- ATCGGATGACATCAAC
TAGCCTACTGTAGTTGCNNN
ROX- ATCGGATGACATCAAC
TAGCCTACTGTAGTTGGNNN
JOE- ATCGGATGACATCAAC
TAGCCTACTGTAGTTGTNNN
where TAMRA, FAM, ROX, and JOE are spectrally resolvable fluorescent labels attached 2U by way of Atninolinker IIT"' (all being available from Applied Biosystems, Inc., Foster City, California): the bold faced nucleotides are the recognition site for Fok I
endonuclease, and "N" represents any one of the four nucleotides. A. C, G, T. TAMRA
(tecrameihylrhodamine), FAM (fluorescein), ROX (rhodamine X), and JOE (2',T-dimethoxy-4',5'-dichlorofluorescein) and their attachment to oligonucleotides is also described in Fung et al, U.S. patent 4,855.225.
The above probes are incubated in approximately 5 molar excess of the target polynucleotide ends as follows: the probes are incubated for 6O minutes at 16°C with 20U
units of T4 DNA ligase and the anchored target polynucleotide in T4 DNA ligase buffer;
after washing, the target polynucleotide is then incubated with 1O0 units T4 polynucleotide kinase in the manufacturews recommended buffer for 30 minutes at 37oC.
washed, and again incubated for 30 minutes at l6oC with 2(N> units of T4 DNA
ligase and the anchored target polynucleotide in T4 DNA ligase buffer. Washing is accomplished by successively t7owing volumes of wash buffer over the slide, e.g. TE, disclosed in Samhrook et al (cited above). After the cycle of ligation-phosphorylation-ligation and a final washing. the attached microparticles are scanned for the presence of fluorescent label.
the positions and characteristics of which are recorded by the scanning system. The labeled target polynucleotide, i.e. the ligated complex, is then incubated with 10 units of . Fok I in the manufacturer's recommended buffer for 30 minutes at 37oC, followed by washing in TE.- As a result the target polynucleotide is shortened by one nucleotide on each strand and is ready for the next cycle of ii-gation and cleavage. The process is continued until twenty nucleotides are identified.

APPENDIX I
~xeTar~co ~uter~ro~am for ~en~, eratin~
minimally cross h_vbridizin~sets Program minxh c c c integer'2 subl(6),msetl(1000,6),mset~(1000,6) dimension nbase(6) c c write(- ,)'ENTER SUBUNIT LENGTH' read(-,100)nsub 100 format(il) open(l,file='sub4.dat',form='formatted', status='new') c c nset=0 do 7000 ml=1,3 do 7000 m2=1,3 do 7000 m3=1,3 do 7000 m4=1,3 subl(1)=ml subl(2)=m2 subl(3)=m3 subl(4)=m4 c c ndiff=3 c , c c Generate set of subunits differing from c subl by at least ndiff nucleotides.
c Save in msetl.
c c jj=1 do 900 j=l,nsub 900 msetl(l,j)=subl(j) c c do 1000 k1=1.3 do lOGO k2=1,3 do 1000 k3=1,3 do 1000 k4=1,3 c c nbase(1)=kl nbase(2)=k2 nbase(3)=k3 - -nbase(4)=k4 c n=,, do 1200 j=l,nsub if(subl(j).eq.l .and.nbase(j).ne.l .or.

1 subl(j) .eq.2 .a.~d.nbase(j) .rie.2 .0r_ 3 subl(j).eq.3 .and.nbase(j).ne.3) then n=n+1 endif 1200 continue c c iftn.ge.ndiff) then c c c If number of mismatches c is greater than or equal c to ndiff then record c subunit in matrix inset c c jj=jj+1 do 1100 i=l,nsub 1100 msetltjj,i)=nbase(i) endif c c 1000 ~ continue c c do 1325 j2=l,nsub mset2(1,j2)=msetl.(1,j2) 1325 mset2(2,j2)=msetlt2,j2) c c c compare subunit 2 from c msetl with each successive c subunit in msetl, i.e. 3, c 9,5, ... etc. Save those c with mismatches .ge. ndiff c in matrix mset2 starting at -c position 2.

c Next transfer contents c of mset2 into msetl and c start c comparisons again this time c starting with subunit 3.
.

c Ccntinua nail ali subunits c undergc the comparisons.

c c npass=0 c c 1700 continue kk=npass+2 nnass=mass+i r do 1500 m=nnass~2,jj 38 _ _ n=G
do 1600 j=l,nsub if(msetl(npass+l,j).eq.l.and.msetl(m,j).ne.l.or.
2 msetl(npass+l,j).eq.2.and.msetl(m,j).ne.2.or.
msetl(npass+l,j).eq.3.and.msetl(m,j).ne.3) then n=rl.~ 1 endif 1600 continue if(n.ge.ndiff) then ' kk=kk+1 do 1625 i=l,nsub 1625 mset2(kk,i)=msetl(m,i) endif 1500 continue c c kk is the number of subunits c . stored in mset2 c c Transfer contents of mset2 c into msetl for next pass.
c c do 2000 k=l,kk do 2000 m=l,nsub ' 2000 msetl(k,m)=mset2(k,m) if(kk.lt.jj) then jj=kk goto 1700 endif c c nset=nset+1 write(1,7009) 7009 format(/) do 7008 k=l,kk 7008 write(1,7010)(msetl(k,m),m=l,nsub) 701C format(4i1) write(',') write(',120) kk,nset 120 formatllx,'Subunits is set=',i5,2x,'Set No=',i5) 7000 continue close(1) c end SEQUENCE LISTING
(1) GENERAL INFORMATION
(i1 APPLICANT: Sydney Brenner (ii) TITLE OF INVENTION: Molecular Tagging System (iii) NUMBER OF SEQUENCES: 5 (iv) CORRESPONDENCE ADDRESS:
(A) ADDRESSEE: Stephen C. Macevicz, Lynx Therapeutics, Inc.
(B) STREET: 3832 Bay Center Place (C) CITY: Hayward (DI STATE: California (E) COUNTRY: USA
(F) ZIP: 94545 (v) COMPUTER READABLE FORM:
(A) MEDIUM TYPE: 3.5 inch diskette (B) COMPUTER: IBM compatible (C) OPERATING SYSTEM: Windows 3.1/D05 5.0 (D) SOFTWARE: Microsoft Word for Windows, vers. 2.0 (vi) CURRENT APPLICATION DATA:
(A) APPLICATION NUMBER:
(B) FILING DATE:
(C) CLASSIFICATION:
(vii) PRIOR APPLICATION DATA:
(A) APPLICATION NUMBER: 08/322,348 (H) FILING DATE: 13-OCT-94 (vii) PRIOR APPLICATION DATA:
(A) APPLICATION NUMBER: 08/358,810 (B) FILING DATE: 19-DEC-94 (viiil ATTORNEY/AGENT INFORMATION:
tA) NAME: Stephen C. Macevicz ($) REGISTRATION NUMBER: 30,285 (C) REFERENCEIDOCKET NUMBED: cbd3wo ,_ Iix1 TELECOMMUNICATION INFORMATION:
(A) TELEPHONE: (510) 67()-9365 (B) TELEFAX: (510) 670-9302 (2) INFORMATION FOR SEQ ID N0:
Ii) SEQUENCE CHARACTERISTICS:
(A) LENGTH: 38 nucleotides (B) TYPE: nucleic acid --lC> STRANDEDNESS: singly (D) TOPOLOGY: linear (xi) SEQUENCE DESCRIPTION: SEQ ID N0: 1:

- (2) INFORMATION FOR SEQ ID N0: 2.
(i) SEQUENCE CHARACTERISTICS:
(A) LENGTH: 26'nucleotides (B) TYPE: nucleic acid tC) STRANDEDNE55: single ID).TOPOLOGY: linear (xi) SEQUENCE DESCRIPTION: SEQ ID N0: 2:

(2) INFORMATION FOR SEQ ID NO: 3:
(i) SEQUENCE CHARACTERISTICS:
(?) LENGTH: 14 nucleotides (B) TYPE: nucleic acid (C) STRANDEDNESS: single (D) TOPOLOGY: linear (xi) SEQUENCE DESCRIPTION: SEQ ID N0: 3:

(~) INFORMATION FOR SEQ ID NO: 4: -.
( i ) SEQUENCE CH.~RP.CTERISTICS
(A) LENGTH: 16 nucleotides (B) TYPE: nucleic acid (C) STRANDEDNESS: double (D) TOPOLOGY: linear (xi) SEQUENCE DESCRIPTION: SEQ T_D N0: 4:

(~) INFORMATION FOR SEQ ID N0:
(i) SEQUENCE CHAR.ACTERIST_ICS:
(-A) LENGTH: 11 nucleotides . _ (B) TYPE: nucleic acrd (C) STRANDEDNESS: double (D) TOPOLOGY: linear (xi> SEQUENCE DESCRIPTION: SEQ ID NO: S:

Claims (3)

1. A composition of matter comprising a mixture of microparticles, each microparticle having polynucleotides of a population attached thereto such that substantially all different polynucleotides in the population are attached to different microparticles, wherein said polynucleotides are selected from the group consisting of cDNAs and genomic DNA fragments.

2. The composition of claim 1 wherein about 10 5 of said polynucleotides are attached to each of said microparticles.

3. The composition of claim 1 or 2 wherein said population has a size in the range of from ten to a hundred thousand.