Methods for selecting nucleic acid probes
View Patent ↗Methods and computer software products are provided for selecting nucleic acid probes. In one embodiment, dynamic programming is employed to select a set of k probes from n probes so that the selected probes have a maximum aggregate adjusted quality score.
1. A computer implemented method for selecting nucleic acid probes comprising:
inputting quality scores and locations for a plurality (n) of candidate probes;
selecting k number of probes from the n number of candidate probes, wherein the selected probes have a maximum aggregate adjusted quality score; wherein the adjusted quality score is based upon the quality score and a penalty for the overlapping of the selected probes; and
outputting the selected probes.
2. The method of claim 1 wherein the adjusted quality score is calculated according to:
S
′
=
S
(
l
-
o
)
l
,
wherein S′ is an adjusted quality score; S is the initial quality score; l is the probe length, and o is the overlap the probe has with other probes.
3. The method of claim 2 wherein k is greater than 3.
4. The method of claim 3 wherein k is greater than 5.
5. The method of claim 4 wherein k is greater than 10.
6. The method of claim 5 wherein k is greater than 15.
7. The method of claim 2 wherein the selecting step comprises performing dynamic programming optimization on the n number of candidate probes to adjust their quality scores to the extent of overlap between them to obtain an optimal k number of probes with optimal aggregate adjusted quality scores.
8. The method of claim 7 wherein the selecting comprises steps of:
calculating best adjusted quality scorns (Sccre(i,t) for probe i last with t−1 probes chosen before i and previous location j providing this best score (Last(i,k));
determining the best adjusted quality scores for Score(j, k) to select the last probe; and
selecting the next probe according to Last(the probe selected, number of probes remaining to be selected); and
repeating the selecting step until all k probes are selected.
9. A system for selecting nucleic acid probes comprising:
a processor; and
a memory coupled with the processor, the memory storing a plurality of machine instructions that cause the processor to perform logical steps, wherein the logical steps include:
inputting quality scores and locations for a plurality (n) of candidate probes;
selecting k number of probes from the n number of candidate probes, wherein the selected probes have a maximum aggregate adjusted quality score; wherein the adjusted quality score is based upon the quality score and a penalty for the overlapping of the selected probes; and
outputting the selected probes.
10. The system of claim 9 wherein the adjusted quality score is calculated according to:
S
′
=
S
(
l
-
o
)
l
,
wherein S′ is an adjusted quality score; S is a quality score; l is the probe length, o is the overlap the probe has with other probes.
11. The system of claim 10 wherein k is greater than 3.
12. The system of claim 11 wherein k is greater than 5.
13. The system of claim 12 wherein k is greater than 10.
14. The system of claim 13 wherein k is greater than 15.
15. The system of claim 14 wherein the selecting step comprises performing dynamic programming optimization on the n number of candidate probes to adjust their quality scores to the extent of overlap between them to obtain an optimal k number of probes with optimal aggregate adjusted quality scores.
16. The system of claim 15 wherein the selecting comprises steps of:
calculating best adjusted quality scores (Score(i,t)) for probe i last wit t−1 probes chosen before i and previous location j providing this best score (Last(i,k));
determining the best adjusted quality scores for Score(j, k) to select the last probe; and
selecting the next probe according to Last(the probe selected, number of probes remain to be selected); and
repeating the selecting step until all k probes are selected.
17. A computer readable medium having computer executable instructions for performing a method comprising:
inputting quality scores and locations for a plurality (n) of candidate probes;
selecting k number of probes from the n number of candidate probes, wherein the selected probes have a maximum aggregate adjusted quality score;
wherein the adjusted quality score is based upon the quality score and a penalty for the overlapping of the selected probes; and
outputting the selected probes.
18. The computer readable medium of claim 17 wherein the adjusted quality score is calculated according to:
S
′
=
S
(
l
-
o
)
l
,
wherein S′ is an adjusted quality score; S is a quality score; l is the probe length, o is the overlap the probe has with other probes.
19. The computer readable medium of claim 18 wherein k is greater than 3.
20. The computer readable medium of claim 19 wherein k is greater than 5.
21. The computer readable medium of claim 20 wherein k is greater than 10.
22. The computer readable medium of claim 21 wherein k is greater than 15.
23. The computer readable medium of claim 22 wherein the selecting step comprises performing dynamic programming optimization on the n number of candidate probes to adjust their quality scores to the extent of overlap between them to obtain an optimal k number of probes with optimal aggregate adjusted quality scores.
24. The computer readable medium of claim 23 wherein the selecting comprises steps of:
calculating best adjusted quality scores (Score(i,t)) for probe i last with t−1 probes chosen before i and previous location j providing this best score (Last(i,k));
determining the best adjusted quality scores for Score(j, k) to select the last probe; and
selecting the next probe according to Last(the probe selected, number of probes remain to be selected); and
repeating the selecting step until all k probes are selected.
25. A computer implemented method for selecting nucleic acid probes comprising:
inputting quality scores and locations for a plurality (n) of candidate probes;
selecting k number of probes from the n number of candidate probes, wherein the selected probes have a maximum aggregate adjusted quality score; wherein the adjusted quality score is based upon the quality score and a penalty for the overlapping of the selected probes; and
outputting the selected probes, wherein the outputting of the selected probe sequences is to a file.
26. A system for selecting nucleic acid probes comprising:
a processor; and
a memory coupled with the processor, the memory storing a plurality of machine instructions that cause the processor to perform logical steps, wherein the logical steps include:
inputting quality scores and locations for a plurality (n) of candidate probes;
selecting k number of probes from the n number of candidate probes, wherein the selected probes have a maximum aggregate adjusted quality score; wherein the adjusted quality score is based upon the quality score and a penalty for the overlapping of the selected probes; and
outputting the selected probes, wherein the outputting of the selected probe sequences is to a file.
27. A computer readable medium having computer executable instructions for performing a method comprising:
inputting quality scores and locations for a plurality (n) of candidate probes;
selecting k number of probes from the n number of candidate probes, wherein the selected probes have a maximum aggregate adjusted quality score;
wherein the adjusted quality score is based upon the quality score and a penalty for the overlapping of the selected probes; and
outputting the selected probes, wherein the outputting of the selected probe sequences is to a file.