Methods, systems and computer software for designing and synthesizing sequence arrays
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.
1 .- 40 . (canceled)
41 . A computer-implemented method for arranging nucleic acid probes for synthesis on a substrate, the method comprising:
providing a list of nucleic acid probes to be synthesized on a substrate, wherein the list of nucleic acid probes includes one or more groups of related nucleic acid probes;
assigning the nucleic acid probes to positions on the substrate;
analyzing the positions of the nucleic acid probes, wherein the analysis determines if nucleic acid probes of a related group have been assigned to positions within a minimum radius of one or more other nucleic acid probes of the related group; and
reassigning at least a portion of the nucleic acid probe positions for nucleic acid probes which are within the minimum radius to one or more nucleic acid probes within their related group, wherein at least the steps of assigning, analyzing and reassigning are performed by a computer, and wherein the computer comprises a computer software program.
42 . The method of claim 41 , wherein the one or more groups of related nucleic acid probes comprise a plurality of probe pairs, wherein each probe pair comprises at least one complementary probe and at least one mismatch probe, and wherein the at least one mismatch probe is different from the at least one complementary probe by one or more base mismatches.
43 . The method of claim 41 , wherein the one or more groups of related nucleic acid probes comprise a plurality of probes designed to measure expression of a gene.
44 . The method of claim 44 , wherein the one or more groups of related nucleic acid probes do not include mismatch probes.
45 . The method of claim 41 , wherein the one or more groups of related nucleic acid probes comprise blocks of probes, and wherein a block of probes includes multiple related probes.
46 . The method of claim 41 , wherein the assignment of the nucleic acid probes to positions on the substrate is a random assignment.
47 . The method of claim 41 , wherein the assignment of the nucleic acid probes comprises using, at least in part, a locally greedy algorithm, wherein the locally greedy algorithm minimizes edge count for the nucleic acid probes, wherein an edge count is a numerical value representing one or more edges between nucleic acid probes, and wherein an edge is a difference between synthesis steps for one nucleic acid probe in comparison to another nucleic acid probe.
48 . The method of claim 47 , wherein the edge count is a weighted edge count, and wherein the weighted edge count is based upon, at least in part, the edge count and a distance between the positions of the nucleic acid probes contributing to the edge count.
49 . The method of claim 47 , wherein the nucleic acid probes are randomly assigned to positions before the locally greedy algorithm is used to complete the assignment of the nucleic acid probes to positions for analysis and potential reassignment.
50 . The method of claim 41 , wherein the analysis comprises calculation of a non-robust probe quantity for at least one related group of nucleic acid probes, and wherein the non-robust probe quantity represents the nucleic acid probes of the related group which are within the minimum radius to one or more probes of the related group.
51 . The method of claim 50 , wherein nucleic acid probe positions are reassigned if the non-robust probe quantity for the related group is equal to or greater than a non-robust probe quantity threshold.
52 . The method of claim 51 , wherein the non-robust probe quantity threshold is 2 nucleic acid probes.
53 . The method of claim 51 , wherein the non-robust probe quantity threshold is 3 nucleic acid probes.
54 . The method of claim 51 , wherein the non-robust probe quantity threshold is 4 nucleic acid probes.
55 . The method of claim 51 , wherein the non-robust probe quantity threshold is 5 nucleic acid probes.
56 . The method of claim 41 , wherein the reassignment of nucleic acid probe positions additionally reassigns positions for at least one nucleic acid probe not within the minimum radius of one or more nucleic acid probes of its related group.
57 . The method of claim 56 , wherein the reassignment comprises swapping one or more positions of the nucleic acid probes within the minimum radius of one or more nucleic acid probes of their related groups with the positions of one or more nucleic acid probes not within the minimum radius of one or more nucleic acid probes of their related groups.
58 . The method of claim 41 , wherein at least the steps of analyzing and reassigning are repeated one or more times.
59 . The method of claim 58 , wherein the steps of analyzing and reassigning are repeated until no nucleic acid probes are assigned to positions within the minimum radius of positions for a nucleic acid probes of their related group.
60 . The method of claim 41 , wherein the analysis comprises calculation of a non-robust probe quantity for at least one related group of nucleic acid probes, wherein the non-robust probe quantity represents the nucleic acid probes of the related group which are within the minimum radius to one or more probes of the related group, wherein nucleic acid probe positions are reassigned if the non-robust probe quantity for the related group is equal to or greater than a non-robust probe quantity threshold, and wherein the steps of analyzing and reassigning are repeated until no non-robust probe quantity is equal to or greater than the non-robust probe quantity threshold for the nucleic acid probe positions.