Method, apparatus and computer program product for determining a set of non-hybridizing oligonucleotides

• US 6,138,077 A
• Filed: 06/03/1998
• Issued: 10/24/2000
• Est. Priority Date: 10/13/1994
• Status: Expired due to Term

• Current Assignee: Solexa Incorporated (Illumina Incorporated)
• Original Assignee: Lynx Therapeutics, Inc. (Illumina Incorporated)
• Inventors: Brenner, Sydney
• Primary Examiner(s): Brusca, John S.
• Assistant Examiner(s): SHIBUYA, MARK LANCE
• Application Number:
  US09/089,853
• Time in Patent Office: 874 Days
• Field of Search: 435/6, 435/440, 435/471, 435/320.1, 536/23.1, 536/25.4, 536/24.2, 536/24.3, 702/19, 702/27
• US Class Current: 702/19
• CPC Class Codes: B01J 19/0046 Sequential or parallel reactions, e.g. for the synthesis of polypeptides or polynucleotides; Apparatus and devices for combinatorial chemistry or for making molecular arrays synthesis methods per se C40B50/00
• CPC Class Codes: B01J 2219/005 Beads
• CPC Class Codes: B01J 2219/00572 Chemical means
• CPC Class Codes: B01J 2219/00605 the compounds being directly bound or immobilised to solid supports
• CPC Class Codes: B01J 2219/00612 the surface being inorganic
• CPC Class Codes: B01J 2219/00626 Covalent
• CPC Class Codes: B01J 2219/00648 by the use of solid beads
• CPC Class Codes: B01J 2219/00659 Two-dimensional arrays
• CPC Class Codes: B01J 2219/00722 Nucleotides
• CPC Class Codes: C12N 15/10 Processes for the isolation, preparation or purification of DNA or RNA chemical preparation of DNA or RNA C07H21/00; preparation of non-structural polynucleotides from microorganisms or with enzymes C12P19/34
• CPC Class Codes: C12N 15/1034 Isolating an individual clone by screening libraries
• CPC Class Codes: C12N 15/1065 Preparation or screening of tagged libraries, e.g. tagged microorganisms by STM-mutagenesis, tagged polynucleotides, gene tags
• CPC Class Codes: C12Q 1/6809 Methods for determination or identification of nucleic acids involving differential detection
• CPC Class Codes: C12Q 1/6827 for detection of mutation or polymorphism
• CPC Class Codes: C12Q 1/6837 using probe arrays or probe chips C12Q1/6874 takes precedence
• CPC Class Codes: C12Q 1/6839 Triple helix formation or other higher order conformations in hybridisation assays
• CPC Class Codes: C12Q 1/6855 Ligating adaptors
• CPC Class Codes: C12Q 1/6874 involving nucleic acid arrays, e.g. sequencing by hybridisation
• CPC Class Codes: C12Q 2521/313 Type II endonucleases, i.e. cutting outside recognition site
• CPC Class Codes: C12Q 2521/501 Ligase
• CPC Class Codes: C12Q 2525/161 : incorporating target specific and non-target specific sites
• CPC Class Codes: C12Q 2525/191 : incorporating an adaptor
• CPC Class Codes: C12Q 2525/204 : specific length of the oligonucleotides
• CPC Class Codes: C12Q 2563/107 : fluorescence
• CPC Class Codes: C12Q 2563/185 : Nucleic acid dedicated to use as a hidden marker/bar code, e.g. inclusion of nucleic acids to mark art objects or animals
• CPC Class Codes: C12Q 2565/501 : being an array of oligonucleotides
• CPC Class Codes: C12Q 2565/518 : characterised by the immobilisation of the nucleic acid sample or target
• CPC Class Codes: C12Q 2565/519 : characterised by the capture moiety being a single stranded oligonucleotide
• CPC Class Codes: C40B 40/06 : Libraries containing nucleotides or polynucleotides, or derivatives thereof
• CPC Class Codes: C40B 70/00 : Tags or labels specially adapted for combinatorial chemistry or libraries, e.g. fluorescent tags or bar codes
• CPC Class Codes: C40B 80/00 : Linkers or spacers specially adapted for combinatorial chemistry or libraries, e.g. traceless linkers or safety-catch linkers

Abstract

The invention provides a computerized method, associated apparatus, and computer program product for determining a set of non-hybridizing oligonucleotides. The invention represents a first oligonucleotide in the computer'"'"'s memory, generates a set of oligonucleotides, including the first oligonucleotide, that meet a specified condition that determines whether the generated oligonucleotides will not hybridize with the first oligonucleotide. The invention also examines each of the generated oligonucleotides in the set to remove oligonucleotides from the set that hybridize with other nucleotides in the set. Thus, the invention develops a minimally cross-hybridizing set of oligonucleotides that can be used for tracking, identifying, and/or sorting classes or subpopulations of molecules by the user of oligonucleotide tags.

Claims

1. A computer program product comprising:

a computer usable storage medium having computer readable code embodied therein for causing a computer to generate a set of non-hybridizing oligonucleotides of a given length, said computer readable code comprising;

computer readable program code configured to cause said computer to effect an assignment mechanism configured to assign a plurality of identifying data values representing different nucleotides;

computer readable program code configured to cause said computer to effect a sequence generation mechanism configured to provide in a memory, from said plurality of identifying data values, a data-value sequence in a first set of possible sequences, where each possible sequence in said first set of possible sequences represents an oligonucleotide having a specified nucleotide at a specified residue position in said oligonucleotide of said given length;

computer readable program code configured to cause said computer to effect a sequence comparison mechanism configured to compare in said memory said data-value sequence from said first set of possible sequences with a data-value sequence in a second set of possible sequences, on the basis of number of positions at which said data-value sequence from said first set of possible sequences and said data-value sequence in said second set of possible sequences have different data values;

computer readable program code configured to cause said computer to effect a sequence inclusion mechanism configured to add said data-value sequence from said first set of possible sequences to said second set of possible sequences if the sequence comparison mechanism determined that said data-value sequence from said first set of possible sequences and said data-value sequence in said second set of possible sequences differ by at least N positions, where N is a specified value greater than one;

computer readable program code configured to cause said computer to effect a sequence pair comparison mechanism configured to compare each pair of data-value sequences in said second set of possible sequences on the basis of number of positions at which each data-value sequence in said pair of data-value sequences have different data values;

computer readable program code configured to cause said computer to effect a sequence retention mechanism configured to retain in said second set of possible sequences, data-value sequences that differ by said at least N positions from all other data-value sequences in said second set of possible sequences; and

computer readable program code configured to cause said computer to effect a first iterative mechanism configured to repetitively invoke the sequence generation mechanism, the sequence comparison mechanism, the sequence inclusion mechanism, the sequence pair comparison mechanism and the sequence retention mechanism until a desired number of data-value sequences have been retained within said second set of possible sequences.

2. The computer program product of claim 1 wherein said first set of possible sequences includes permutations of data-value sequences having said given length.

3. The computer program product of claim 1 wherein the sequence generation mechanism generated a list of possible data-value sequences of said given length and the sequence generation mechanism further comprises:

computer readable program code configured to cause said computer to effect a selection mechanism configured to select said data-value sequence from said list of possible data-value sequences.

4. The computer program product of claim 1 wherein:

the sequence generation mechanism includes computer readable program code configured to cause said computer to effect a selection mechanism configured to arbitrarily select said data-value sequence from said first set of possible sequences;

if said data-value sequence has been placed in said second set of possible sequences by the subsequent sequence generation mechanism, the sequence inclusion mechanism includes computer readable program code configured to cause said computer to effect a set comparison mechanism configured to compare said data-value sequence with all other data-values sequences within said second set of possible sequences; and

the sequence retention mechanism is configured to retain said data-value sequence within said second set of possible sequences only if the set comparison mechanism determines that said data-value sequence differs in data values from all other sequences in said second set of possible sequences by said at least N positions.

5. The computer program product of claim 3 that further includes computer readable program code configured to cause said computer to effect a second iterative mechanism configured to repetitively invoke the sequence generation mechanism, the sequence comparison mechanism, the sequence inclusion mechanism, the sequence pair comparison mechanism and the sequence retention mechanism until each data-value sequence in said first set of possible sequences has been compared with at least one data-value sequence in said second set of possible sequences.