  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.
