Methods, Systems and Computer Software For Designing and Synthesizing Sequence Arrays

• US 20080096771A1
• Filed: 12/21/2007
• Published: 04/24/2008
• Est. Priority Date: 08/17/1999
• Status: Abandoned Application

• Current Assignee: Affymetrix, Inc. (Thermo Fisher Scientific Incorporated)
• Original Assignee: Affymetrix, Inc. (Thermo Fisher Scientific Incorporated)
• Inventors: Hubbell, Earl
• Application Number:
  US11/963,284
• Publication Number:
  US 20080096771A1
• Time in Patent Office: Days
• US Class Current: 506/13
• 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/00432 Photolithographic masks
• CPC Class Codes: B01J 2219/00529 DNA chips
• CPC Class Codes: B01J 2219/00585 Parallel processes
• CPC Class Codes: B01J 2219/0059 Sequential processes
• CPC Class Codes: B01J 2219/00596 Solid-phase processes
• 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/00659 Two-dimensional arrays
• CPC Class Codes: B01J 2219/00689 using computers
• CPC Class Codes: B01J 2219/00695 Synthesis control routines, e.g. using computer programs
• CPC Class Codes: B01J 2219/00711 Light-directed synthesis
• CPC Class Codes: B01J 2219/00722 Nucleotides
• CPC Class Codes: B82Y 30/00 Nanotechnology for materials or surface science, e.g. nanocomposites
• CPC Class Codes: C40B 40/06 Libraries containing nucleotides or polynucleotides, or derivatives thereof
• CPC Class Codes: C40B 40/10 Libraries containing peptides or polypeptides, or derivatives thereof
• CPC Class Codes: C40B 60/14 for creating libraries
• CPC Class Codes: G16B 25/00 ICT specially adapted for hybridisation; ICT specially adapted for gene or protein expression
• CPC Class Codes: G16B 25/30 Microarray design
• CPC Class Codes: G16B 35/00 : ICT specially adapted for in silico combinatorial libraries of nucleic acids, proteins or peptides
• CPC Class Codes: G16B 35/10 : Design of libraries
• CPC Class Codes: G16B 40/00 : ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16C 20/60 : In silico combinatorial chemistry

Abstract

Embodiments of the invention provides methods, computer software products and systems for arranging polymers during combinatorial polymer synthesis so that the border or edge between synthesis site is minimized. In one embodiment, travelling salesman algorithm is used to minimize the edges. In another embodiment, a locally greedy optimization method is provided. In addition, methods and software products are provided for solving the robust arrangement problem for multi-probe gene expression arrays.

Claims

1-3. -3. (canceled)

4. A computer implemented method for arranging polymers for combinatorial synthesis of the polymers on a substrate comprising:

obtaining a list of polymers to be synthesized on the substrate; and

dividing the polymers to be synthesized on the substrate into a plurality of unassigned blocks, wherein each of the unassigned block of the plurality of unassigned blocks comprises one or more related polymers from the other unassigned blocks,

assigning each of the unassigned block to an empty slot on the substrate for synthesis by minimizing edge count comprising;

selecting a subset of the blocks from the plurality of unassigned blocks; and

assigning one selected block of the unassigned blocks in the subset to the empty slot, wherein the one assigned block creates an arrangement of the polymers resulting in a least edge count among the subset of blocks.

5. The method of claim 4 further comprising repeating the steps of assigning each unassigned block to an empty slot on the substrate for synthesis by minimizing edge count until all blocks are assigned.

6. The method of claim 5 wherein the assigning each unassigned block to an empty slot on the substrate for synthesis by minimizing edge count slot further comprises:

computing a plurality of edge counts after placing each assigned block into the empty slot; and

comparing the edge counts from each assigned block and choosing the assigned block that has the least edge count.

7. The method of claim 6 wherein the unassigned blocks are ordered randomly and the selecting step comprises first selecting the subset among unassigned blocks.

8. The method of claim 7 wherein the last of the subsets of unassigned blocks has no more than 100 blocks and the created arrangement of the polymers has at least 20 blocks and no more than 100 blocks.

9. The method of claim 7 wherein the last of the subsets of unassigned blocks has no more than 1000 blocks and the created arrangement of the polymers has at least 100 blocks and no more than 1000 blocks.

10. The method of claim 7 wherein the last of the subsets of unassigned blocks has no more than 10000 blocks and the created arrangement of the polymers has at least 1000 blocks and no more than 10000 blocks.

11. The method of claim 7 further comprising synthesizing the arrangement of the polymers of all the assigned blocks wherein the polymers are oligonucleotides.

12. The method of claim 11 wherein the combinatorial synthesis is radiation directed synthesis.

13. The method of claim 12 wherein the radiation directed synthesis comprises steps of controlling irradiation to active synthesis site using a mask.

14. The method of claim 13 wherein the edge count is a weighted edge count taking into account distance to cell leaking radiation.

15-24. -24. (canceled)

25. A computer software product for arranging polymers for combinatorial synthesis of the polymers on a substrate comprising:

code for obtaining a list of polymers to be synthesized; and

code for dividing the polymers to be synthesized on the substrate into a plurality of unassigned blocks, wherein each of the unassigned blocks of the plurality of unassigned blocks comprises one or more related polymers from the other unassigned blocks, and code for assigning each of the unassigned block to an empty slot on the substrate for synthesis by minimizing edge count comprising;

code for selecting a subset of the blocks from the plurality of unassigned blocks;

and code for assigning one selected block of the unassigned blocks in the subset to the empty slot, wherein the one assigned block creates an arrangement of the polymers resulting in a least edge count among the subset of the blocks; and

a computer readable medium for storing the code.

26. The computer software product of claim 25 further comprising code for repeating execution of the codes of assigning each unassigned block to an empty slot on the substrate for synthesis by minimizing edge count until all blocks are assigned.

27. The computer software product of claim 26 wherein the code for assigning comprises:

code for computing a plurality of edge counts, each of the edge counts represents the result of assigning one block of the subset to the empty slot; and

code for comparing the edge counts and selecting a best fitting block, wherein the best fitting block has the least edge count.

28. The computer software product of claim 27 wherein the blocks are ordered randomly and the code for selecting comprises code for selecting the first subset among unassigned blocks.

29. The computer software product of claim 28 wherein the last of the subsets of unassigned blocks has no more than 100 blocks and the created arrangement of the polymers has at least 20 blocks and no more than 100 blocks.

30. The computer software product of claim 28 wherein the last of the subset of unassigned blocks has no more than 1000 blocks and the created arrangement of the polymers has at least 100 blocks and no more than 1000 blocks.

31. The computer software product of claim 28 wherein the last of the subsets of unassigned blocks has no more than 10000 blocks and the created arrangement of the polymers has at least 1000 blocks and no more than 10000 blocks.

32. The computer software product of claim 28 further comprising code for inputting size of the subsets.

33. The computer software product of claim 28 wherein the edge count is a weighted edge count taking into account distance to cell leaking radiation.

34-40. -40. (canceled)