A pairwise alignment algorithm which favors clusters of blocks.
Pairwise sequence alignments aim to decide whether two sequences are related and, if so, to exhibit their related domains. Recent works have pointed out that a significant number of true homologous sequences are missed when using classical comparison algorithms. This is the case when two homologous sequences share several little blocks of homology, too small to lead to a significant score. On the other hand, classical alignment algorithms, when detecting homologies, may fail to recognize all the significant biological signals. The aim of the paper is to give a solution to these two problems. We propose a new scoring method which tends to increase the score of an alignment when "blocks" are detected. This so-called Block-Scoring algorithm, which makes use of dynamic programming, is worth being used as a complementary tool to classical exact alignments methods. We validate our approach by applying it on a large set of biological data. Finally, we give a limit theorem for the score statistics of the algorithm.
Nédélec
Elodie
E
Laboratoire de Mathématiques, Equipe de Probabilités, Statistique et Modélisation, UMR CNRS 8628, Université Paris-Sud, 91405 Orsay Cedex, France.
Moncion
Thomas
T
Gassiat
Elisabeth
E
Bossard
Bruno
B
Duchateau-Nguyen
Guillemette
G
Denise
Alain
A
Termier
Michel
M
D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D008969:Molecular Sequence Data; D012313:RNA / Q000737:chemistry*; D016415:Sequence Alignment; D012689:Sequence Homology, Nucleic Acid
D012313:RNA