Nucleic Acids Research, 2005, Vol. 33, Web Server issue W543 (16)]. Moreover, transition-constrained seeds have been shown to be more sensitive in detecting alignments of real genomic sequences [Table 3 in (16)]. YASS has been compared with bl2seq (NCBI BLAST 2.2.6) according to several criteria: running time, number of signiﬁcant alignments found (with E-value < 10 6) and num- ber of signiﬁcant alignments found exclusively by one pro- gram and their total length [Table 4 in (16)]. The results show that YASS detects more signiﬁcant alignments than bl2seq, within a smaller time for large DNA sequences. CONCLUSIONS In this paper, we have described YASS—a new DNA local alignment tool. The proposed web interface features several output formats suitable for a coup d’oeil analysis as well as for a deeper analysis of alignments. An upcoming release of YASS will include multi-seed indexing strategies and an optimized processor-cache algorithm. ACKNOWLEDGEMENTS The authors wish to thank Marie-Pierre Etienne and Pierre Valois for their help during early stages of this work, Mikhail Roytberg for his contribution to the seed design pro- blem and Christophe Valmir for improving the YASS code. The authors have been supported by the ACI IMPBio of the French Ministry of Research. They thank the reviewers for their helpful remarks. Funding to pay the Open Access publication charges for this article was provided by CNRS. Conflict of interest statement. None declared. REFERENCES 1. Smith,T. and Waterman,M. (1981) Identification of common molecular subsequences. J. Mol. Biol., 147, 195–197. 2. Lipman,D. and Pearson,W. (1988) Improved tools for biological sequence comparison. Proc. Natl Acad. Sci. USA, 85, 2444–2448. 3. Califano,A. and Rigoutsos,I. (1993) Flash: a fast look-up algorithm for string homology. Proc. Int. Conf. Intell. Syst. Mol. Biol., 1, 56–64. 4. Altschul,S., Gish,W., Miller,W., Myers,E. and Lipman,D. (1990) Basic local alignment search tool. J. Mol. Biol., 215, 403–410. 5. Altschul,S., Madden,T., Scha¨ffer,A., Zhang,J., Zhang,Z., Miller,W. and Lipman,D. (1997) Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Res., 25, 3389–3402. 6. Schwartz,S., Kent,J., Smit,A., Zhang,Z., Baertsch,R., Hardison,R., Haussler,D. and Miller,W. (2003) Human-mouse alignments with BLASTZ. Genome Res., 13, 103–107. 7. Ma,B., Tromp,J. and Li,M. (2002) PatternHunter: faster and more sensitive homology search. Bioinformatics, 18, 440–445. 8. Burkhardt,S. and Ka¨rkka¨inen,J. (2001) Better filtering with gapped q-grams. In Proceedings of the 12th Symposium on Combinatorial Pattern Matching (CPM’01), 1–4 July, Jerusalem, Israel, LNCS 2089, Springer, pp. 73–85. 9. Li,M., Ma,B., Kisman,D. and Tromp,J. (2004) PatternHunter II: highly sensitive and fast homology search. J. Bioinform. Comput. Biol., 2, 417–439. 10. Brejova,B., Brown,D. and Vinar,T. (2003) Optimal spaced seeds for hidden Markov models, with application to homologous coding regions. In Baeza-Yates,R., Chavez,E. and Crochemore,M. (eds), Proceedings of the 14th Symposium on Combinatorial Pattern Matching, 25–27 June, Morelia, Mexico, LNCS 2676, Springer, pp. 42–54. 11. Buhler,J., Keich,U. and Sun,Y. (2003) Designing seeds for similarity search in genomic DNA. In Proceedings of the 7th Annual International Conference on Computational Molecular Biology (RECOMB’03), 10–13 April, Berlin, Germany, ACM Press, pp. 67–75. 12. Choi,K.P., Zeng,F. and Zhang,L. (2004) Good spaced seeds for homology search. Bioinformatics, 20, 1053–1059. 13. Keich,U., Li,M., Ma,B. and Tromp,J. (2004) On spaced seeds for similarity search. Discrete Appl. Math., 138, 253–263. 14. Kucherov,G., Noe´,L. and Ponty,Y. (2004) Estimating seed sensitivity on homogeneous alignments. In Proceedings of the IEEE 4th Symposium on Bioinformatics and Bioengineering (BIBE2004), May 19–21, Taichung, Taiwan, IEEE Computer Society Press, pp. 387–394. 15. Kucherov,G., Noe´,L. and Roytberg,M. (2004) A unifying framework for seed sensitivity and its application to subset seeds. Rapport de recherche INRIA RR-5374. http://www.inria.fr/rrrt/rr-5374.html. 16. Noe´,L. and Kucherov,G. (2004) Improved hit criteria for DNA local alignment. BMC Bioinformatics, 5, 149. 17. Benson,G. (1999) Tandem repeats finder: a program to analyse DNA sequences. Nucleic Acids Res., 27, 573–580.