Aligning biological sequences by exploiting residue conservation and coevolution

Abstract

Sequences of nucleotides (for DNA and RNA) or amino acids (for proteins) are central objects in biology. Among the most important computational problems is that of sequence alignment, i.e. arranging sequences from different organisms in such a way to identify similar regions, to detect evolutionary relationships between sequences, and to predict biomolecular structure and function. This is typically addressed through profile models, which capture position-specificities like conservation in sequences, but assume an independent evolution of different positions. Over the last years, it has been well established that coevolution of different amino-acid positions is essential for maintaining three-dimensional structure and function. Modeling approaches based on inverse statistical physics can catch the coevolution signal in sequence ensembles; and they are now widely used in predicting protein structure, protein-protein interactions, and mutational landscapes. Here, we present DCAlign, an efficient alignment algorithm based on an approximate message-passing strategy, which is able to overcome the limitations of profile models, to include coevolution among positions in a general way, and to be therefore universally applicable to protein- and RNA-sequence alignment without the need of using complementary structural information. The potential of DCAlign is carefully explored using well-controlled simulated data, as well as real protein and RNA sequences.

arXiv comment20 pages, 11 figures + Supplementary Information

References in corpus (20)

• Direct-coupling analysis of residue co-evolution captures native contacts across many protein families
• Identification of direct residue contacts in protein-protein interaction by message passing
• Quantification of the effect of mutations using a global probability model of natural sequence variation
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Improved contact prediction in proteins: Using pseudolikelihoods to infer Potts models
• Coevolutionary landscape inference and the context-dependence of mutations in beta-lactamase TEM-1
• Inverse statistical problems: from the inverse Ising problem to data science
• Inverse Statistical Physics of Protein Sequences: A Key Issues Review
• The Ising Model for Neural Data: Model Quality and Approximate Methods for Extracting Functional Connectivity
• Fast pseudolikelihood maximization for direct-coupling analysis of protein structure from many homologous amino-acid sequences
• Inferring interaction partners from protein sequences
• How pairwise coevolutionary models capture the collective residue variability in proteins
• Fast and accurate multivariate Gaussian modeling of protein families: Predicting residue contacts and protein-interaction partners
• Simultaneous identification of specifically interacting paralogs and inter-protein contacts by Direct-Coupling Analysis
• Small-correlation expansions for the inverse Ising problem
• Direct-Coupling Analysis of nucleotide coevolution facilitates RNA secondary and tertiary structure prediction
• Dissecting the Specificity of Protein-Protein Interaction in Bacterial Two-Component Signaling: Orphans and Crosstalks
• Pseudolikelihood Decimation Algorithm Improving the Inference of the Interaction Network in a General Class of Ising Models
• Inter-protein sequence co-evolution predicts known physical interactions in bacterial ribosomes and the trp operon
• Potts Glass on Random Graphs

Cited by in corpus (4)

• Interpretable Neural Networks based classifiers for categorical inputs
• Ancestral Sequence Reconstruction for Co-evolutionary models
• DCAlign v1.0: Aligning biological sequences using co-evolution models and informed priors
• Small Coupling Expansion for Multiple Sequence Alignment