Probabilistic sequence alignments: realistic models with efficient algorithms.
Alignment algorithms usually rely on simplified models of gaps for computational efficiency. Based on correspondences between alignments and structural models for nucleic acids, and using methods from statistical mechanics, we show that alignments with realistic laws for gaps can be computed with fast algorithms. Improved performances of probabilistic alignments with realistic models of gaps are illustrated. By contrast with optimization-based alignments, such improvements with realistic laws are not observed. General perspectives for biological and physical modelings are mentioned.
Yeramian
Edouard
E
Unité de Bio-Informatique Structurale, CNRS URA 2185, Institut Pasteur, 25-28 rue du Docteur Roux, 75724 Paris cedex 15, France. yeramian@pasteur.fr
Debonneuil
Edouard
E
D000465:Algorithms; D001483:Base Sequence; D055592:Biophysical Phenomena; D001703:Biophysics; D019295:Computational Biology; D008956:Models, Chemical; D015233:Models, Statistical; D017711:Nonlinear Dynamics; D009690:Nucleic Acid Conformation