Small Coupling Expansion for Multiple Sequence Alignment

Abstract

The alignment of biological sequences such as DNA, RNA, and proteins, is one of the basic tools that allow to detect evolutionary patterns, as well as functional/structural characterizations between homologous sequences in different organisms. Typically, state-of-the-art bioinformatics tools are based on profile models that assume the statistical independence of the different sites of the sequences. Over the last years, it has become increasingly clear that homologous sequences show complex patterns of long-range correlations over the primary sequence as a consequence of the natural evolution process that selects genetic variants under the constraint of preserving the functional/structural determinants of the sequence. Here, we present a new alignment algorithm based on message passing techniques that overcomes the limitations of profile models. Our method is based on a new perturbative small-coupling expansion of the free energy of the model that assumes a linear chain approximation as the $0^{\mathrm{th}}$-order of the expansion. We test the potentiality of the algorithm against standard competing strategies on several biological sequences.

arXiv comment22 pages, 10 figures

References in corpus (11)

• Direct-coupling analysis of residue co-evolution captures native contacts across many protein families
• Quantification of the effect of mutations using a global probability model of natural sequence variation
• Coevolutionary landscape inference and the context-dependence of mutations in beta-lactamase TEM-1
• Inverse Statistical Physics of Protein Sequences: A Key Issues Review
• Fast and accurate multivariate Gaussian modeling of protein families: Predicting residue contacts and protein-interaction partners
• Efficient generative modeling of protein sequences using simple autoregressive models
• Dissecting the Specificity of Protein-Protein Interaction in Bacterial Two-Component Signaling: Orphans and Crosstalks
• Inter-protein sequence co-evolution predicts known physical interactions in bacterial ribosomes and the trp operon
• Zero Temperature Properties of RNA Secondary Structures
• Near optimal configurations in mean field disordered systems
• Aligning biological sequences by exploiting residue conservation and coevolution