Methods, systems and computer software for designing and synthesizing sequence arrays

• US 20040132099A1
• Filed: 07/25/2003
• Published: 07/08/2004
• 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 A.
• Application Number:
  US10/627,271
• Publication Number:
  US 20040132099A1
• Time in Patent Office: Days
• US Class Current: 435/7.1
• 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. A computer implemented method for arranging polymers for combinatorial synthesis of said polymers on a substrate comprising:

reducing edge count between said polymers comprising

computer-implemented steps for optimization of an ordered list of polymers.

2. The method of claim 1 wherein said steps for optimization comprises steps for travelling salesman optimization of said ordered list of polymers.

3. The method of claim 2 wherein said travelling salesman optimization is performed by means of a locally greedy insertion heuristic.

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

reducing edge count between said polymers comprising;

dividing said polymers into a plurality of blocks, wherein each of said block comprising one or more related polymers, wherein each of said blocks is to be assigned to one slot on said substrate; and

selecting a subset of said blocks from unassigned blocks; and

assigning one block of said blocks in said set to an empty slot, wherein said one block is the best fitting and results in a least edge count among said blocks of said subset.

5. The method of claim 4 further comprising repeating said steps of selecting and assigning until all blocks are assigned.

6. The method of claim 5 wherein said assigning comprises:

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

comparing said edge counts and selecting said best fitting block, wherein said best fitting block has said least edge count.

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

8. The method of claim 7 wherein the last of said subsets has no more than 100 blocks and other said subset has at least 20 blocks and no more than 100 blocks.

9. The method of claim 7 wherein the last of said subset has no more than 1000 blocks and other said subset has at least 100 blocks and no more than 1000 blocks.

10. The method of claim 7 wherein the last of said subsets has no more than 10000 blocks and other said subset has at least 1000 blocks and no more than 10000 blocks.

11. The method of claim 7 wherein said polymers are oligonucleotides.

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

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

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

15. A computer implemented method for arranging nucleic acid probes in a nucleic acid probe array comprising:

providing an arrangement of said nucleic acid probes;

reducing non-robust probes in said arrangement, wherein said non-robust probe is a probe that occurs as one of at least two (K) probes associated with a given gene within a specified area of said array, comprising;

removing non-robust blocks and optionally removing additional blocks, wherein said non-robust blocks comprises at least one non-robust probe and leaving empty slots in said initial arrangement; and

reassigning said blocks to empty slots of said arrangement.

16. The method of claim 15 wherein said K is at least three.

17. The method of claim 16 wherein said K is at least four.

18. The method of claim 17 wherein said K is at least five.

19. The method of claim 15 wherein said removing step comprises removing said additional blocks randomly.

20. The method of claim 19 wherein said reassigning step comprises reassigning said blocks into said empty slots randomly.

21. The method of claim 20 further comprising repeating steps of removing and reassigning.

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

code for reducing edge count between said polymers comprising

code for optimizating an ordered list of polymers; and

a computer readable medium for storing said code.

23. The computer software product claim 22 wherein said code for optimizing comprises code for travelling salesman optimization of said ordered list of polymers.

24. The computer software product of claim 23 wherein said code for travelling salesman optimization comprises code for a locally greedy insertion heuristic.

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

code for reducing edge count between said polymers comprising

code for dividing said polymers into a plurality of blocks, wherein each of said blocks comprises one or more related polymers, and wherein each of said blocks is to be assigned to one slot on said substrate; and

code for selecting a subset of said blocks from unassigned blocks; and

code for assigning one block of said blocks in said set to an empty slot, wherein said one block-is the best fitting and results in a least edge count among said blocks of said subset; and

a computer readable medium for storing said code.

26. The computer software product of claim 25 further comprising code for repeating execution of said codes of selecting and assigning until all blocks are assigned.

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

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

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

28. The computer software product of claim 27 wherein said blocks are ordered randomly and said 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 said subsets has no more than 100 blocks and other said subset has at least 20 blocks and no more than 100 blocks.

30. The computer software product of claim 28 wherein the last of said subset has no more than 1000 blocks and other said subset has at least 100 blocks and no more than 1000 blocks.

31. The computer software product of claim 28 wherein the last of said subsets has no more than 10000 blocks and other said subset 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 subsets.

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

34. A computer software product for arranging nucleic acid probes in a nucleic acid probe array comprising:

code for reducing non-robust probes in an arrangement of said probes, wherein said non-robust probe is a probe that occurs as one of at least two (K) probes associated with a given gene within a specified area of said array, comprising;

code for removing non-robust blocks and optionally additional blocks, wherein non-robust blocks comprises at least one robust probe from said arrangement and leaving empty slots in said initial arrangement;

code for reassigning said blocks to empty slots of said arrangement; and

a computer readable medium for storing said codes.

35. The computer software product of claim 34 wherein K is at least three.

36. The computer software product of claim 34 wherein said K is at least four.

37. The computer software product of claim 34 wherein said K is at least five.

38. The computer software product of claim 34 wherein said code for removing comprises code for removing said other blocks randomly.

39. The computer software product of claim 38 wherein said code for reassigning comprises code for reassigning said blocks into said empty slots randomly.

40. The computer software product of claim 34 further comprising code for repeating execution of said codes for removing and reassigning.