Subset seed extension to Protein BLAST

Anna Gambin 1, 2 Slawomir Lasota 2 Michal Startek 2 Maciej Sykulski 2 Laurent Noé 3, 4 Gregory Kucherov 5
1 CMDIK - Mossakowski Medical Research Centre
2 Department of Mathematics, Computer Science and Mechanics [Warsaw]
3 BONSAI - Bioinformatics and Sequence Analysis
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
4 LIFL - Laboratoire d'Informatique Fondamentale de Lille
5 LIGM - Laboratoire d'Informatique Gaspard-Monge
Abstract : The seeding technique became central in the theory of sequence alignment and there are several efficient tools applying seeds to DNA homology search. Recently, a concept of subset seeds has been proposed for similarity search in protein sequences. We experimentally evaluate the applicability of subset seeds to protein homology search. We advocate the use of multiple subset seeds derived from a hierarchical tree of amino acid residues. Our method computes, by an evolutionary algorithm, seeds that are specifically designed for a given protein family. The representation of seeds by deterministic finite automata (DFAs) is developed and built into the NCBI-BLAST software. This extended tool, named SeedBLAST, is compared to the original NCBI-BLAST and PSI-BLAST on several protein families. Our results demonstrate a superiority of SeedBLAST in terms of efficiency, especially in the case of twilight zone hits. SeedBLAST is an open source software freely available http://bioputer.mimuw.edu.pl/papers/sblast . Supplementary material and user manual are also provided.
Keywords : Sequence Analysis Algorithms and Software Tools Sequence alignment Protein BLAST Subset seed DFA Genetic algorithm
Type de document :
Communication dans un congrès
Bioinformatics 2011 - International Conference on Bioinformatics Models, Methods and Algorithms, Jan 2011, Rome, Italy. SciTePress, pp.149-158, 2011, <http://www.lifl.fr/~noe/files/pp_BIOSTEC11.pdf>. <10.5220/0003147601490158>
Liste complète des métadonnées
https://hal.inria.fr/inria-00609791
Contributeur : Laurent Noé <>
Soumis le : mercredi 20 juillet 2011 - 10:04:38
Dernière modification le : vendredi 8 janvier 2016 - 01:07:00

Identifiants

Collections

INRIA | LIFL | LIGM | UNIV-MLV | LIGM_ALGO | ENPC | PARISTECH | UPEC-UPEM | UNIV-LILLE3 | LIGM_MOA | CRISTAL-BONSAI | CRISTAL

Citation

Anna Gambin, Slawomir Lasota, Michal Startek, Maciej Sykulski, Laurent Noé, et al.. Subset seed extension to Protein BLAST. Bioinformatics 2011 - International Conference on Bioinformatics Models, Methods and Algorithms, Jan 2011, Rome, Italy. SciTePress, pp.149-158, 2011, <http://www.lifl.fr/~noe/files/pp_BIOSTEC11.pdf>. <10.5220/0003147601490158>. <inria-00609791>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

455

Contact


archive-ouverte@inria.fr