Fast large scale oligonucleotide selection using the longest common factor approach.
We present a fast method that selects oligonucleotide probes (such as DNA 25-mers) for microarray experiments on a truly large scale. For example, reliable oligos for human genes can be found within four days, a speedup of one to two orders of magnitude compared to previous approaches. This speed is attained by using the longest common substring as a specificity measure for candidate oligos. We present a space- and time-efficient algorithm, based on a suffix array with additional information, to compute matching statistics (lengths of longest matches) between all candidate oligos and all remaining sequences. With the matching statistics available, we show how to incorporate constraints such as oligo length, melting temperature, and self-complementarity into the selection process at a postprocessing stage. As a result, we can now design custom oligos for any sequenced genome, just as the technology for on-site chip synthesis is becoming increasingly mature.
Max-Planck-Institute for Molecular Genetics, Ihnestrasse 63-73, D-14195 Berlin, Germany. Sven.Rahmann@molgen.mpg.de
Sven
S
Rahmann
D000465:Algorithms; D001483:Base Sequence; D017076:Computer-Aided Design; D020869:Gene Expression Profiling / Q000379:methods*; D008969:Molecular Sequence Data; D020411:Oligonucleotide Array Sequence Analysis / Q000379:methods*; D015345:Oligonucleotide Probes / Q000138:chemical synthesis* / Q000235:genetics*; D009841:Oligonucleotides / Q000138:chemical synthesis / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid
D015345:Oligonucleotide Probes; D009841:Oligonucleotides