YASS: Similarity search in DNA sequences
Résumé
We describe YASS -- a new tool for finding local similarities in DNA sequences. The YASS algorithm first scans the sequence(s) and creates on the fly groups of (small exact repeats obtained by hashing) according to statistically-founded criteria. Then it tries to extend those groups into similarity regions on the basis of a new extension criterion. The method can be seen as a compromise between single-seed () and multiple-seed (, ) approaches, and achieves a gain in both sensitivity and selectivity. The method is flexible and can be made more efficient by using spaced seeds, and in particular transition-constrained spaced seeds. We provide examples of applying YASS to Saccharomyces Cerevisiae and Drosophila Melanogaster chromosomes.