Efficient alternatives to PSI-BLAST

National audienceIn this paper we present two algorithms that may serve as e fficient alternatives to the well-known PSI BLAST tool: SeedBLAST and CTX-PSI Blast. Both may bene t from the knowledge about amino acid composition speci c to a given protein family: SeedBLAST uses a advisedly designed seed, while CTX-PSI BLAST extends PSI BLAST with the context-speci c substitution model. The seeding technique became central in the theory of sequence alignment. There are several e cient tools applying seeds to DNA homology search, but not to protein homology search. In this paper we ll this gap. 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 specifi cally designed for a given protein family. The seeds are represented by deterministic finite automata (DFAs) and built into the NCBI-BLAST software. This extended tool, named SeedBLAST, is compared to the original BLAST and PSI-BLAST on several protein families. Our results demonstrate a superiority of SeedBLAST in terms of e ciency, especially in the case of twilight zone hits. The contextual substitution model has been proven to increase sensitivity of protein alignment. In this paper we perform a next step in the contextual alignment program. We announce a contextual version of the PSI-BLAST algorithm, an iterative version of the NCBI-BLAST tool. The experimental evaluation has been performed demonstrating a signi cantly higher sensitivity compared to the ordinary PSI-BLAST algorithm