Optimal spaced seeds for homologous coding regions.
Optimal spaced seeds were developed as a method to increase sensitivity of local alignment programs similar to BLASTN. Such seeds have been used before in the program PatternHunter, and have given improved sensitivity and running time relative to BLASTN in genome-genome comparison. We study the problem of computing optimal spaced seeds for detecting homologous coding regions in unannotated genomic sequences. By using well-chosen seeds, we are able to improve the sensitivity of coding sequence alignment over that of TBLASTX, while keeping runtime comparable to BLASTN. We identify good seeds by first giving effective hidden Markov models of conservation in alignments of homologous coding regions. We give an efficient algorithm to compute the optimal spaced seed when conservation patterns are generated by these models. Our results offer the hope of improved gene finding due to fewer missed exons in DNA/DNA comparison, and more effective homology search in general, and may have applications outside of bioinformatics.
School of Computer Science, University of Waterloo, 200 University Ave West, Waterloo, ON N2L3G1, Canada. bbrejova@math.uwaterloo.ca
Broña
B
Brejová
Daniel G
DG
Brown
Tomás
T
Vinar
D000465:Algorithms; D000818:Animals; D019295:Computational Biology; D004247:DNA / Q000235:genetics; D004330:Drosophila / Q000235:genetics; D006801:Humans; D008390:Markov Chains; D051379:Mice; D015233:Models, Statistical; D011506:Proteins / Q000235:genetics; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000706:statistics & numerical data*; D012984:Software
D011506:Proteins; D004247:DNA