Journal of Bioinformatics and Computational Biology · 2003 · 48 citations · 11 references
Life SciencesBioinformaticsMolecular BiologyGenomic Data AnalysisGenomicsSequence AnalysisDna SequencingGenome SequencingMotif DiscoveryOligonucleotide ChemistrySequence Similarity SearchHigh-throughput Oligonucleotide SynthesisLongest Common SubsequenceLongest Common SubstringLongest Prefix MatchingMicroarray AnalysisOligonucleotide Array AnalysisOligonucleotide Library SynthesisPostprocessing Techniques
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.
11
Suffix Arrays: A New Method for On-Line String Searches
Udi Manber, Gene Myers · SIAM Journal on Computing · 1993 · 2K citations
Algorithms on strings, trees, and sequences
Dan Gusfield · 1997 · 1.7K citations
Laurie Issel‐Tarver, Karen Christie, Kara Dolinski et al. · Methods in enzymology on CD-ROM/Methods in enzymology · 2002 · 672 citations