title: A pairwise alignment algorithm which favors clusters of blocks.
abstract: 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.
authors.affiliation: Laboratoire de Mathématiques, Equipe de Probabilités, Statistique et Modélisation, UMR CNRS 8628, Université Paris-Sud, 91405 Orsay Cedex, France.
authors.forename: Elodie
authors.initials: E
authors.lastname: Nédélec
authors.forename: Thomas
authors.initials: T
authors.lastname: Moncion
authors.forename: Elisabeth
authors.initials: E
authors.lastname: Gassiat
authors.forename: Bruno
authors.initials: B
authors.lastname: Bossard
authors.forename: Guillemette
authors.initials: G
authors.lastname: Duchateau-Nguyen
authors.forename: Alain
authors.initials: A
authors.lastname: Denise
authors.forename: Michel
authors.initials: M
authors.lastname: Termier
mesh_terms: 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
chemical_list: D012313:RNA