FLEXIBLE ALGORITHM FOR DIRECT MULTIPLE ALIGNMENT OF PROTEIN STRUCTURES AND SEQUENCES

The recently described equivalence between the alignment of two protei ns and a conformation of a lattice chain on a two-dimensional square l attice is extended to multiple alignments. The search for the optimal multiple alignment between several proteins, which is equivalent to fi nding the energy minimum in the conformational space of a multidimensi onal lattice chain, is studied by the Monte Carlo approach. This metho d, while not deterministic, and for two-dimensional problems slower th an dynamic programming, can accept arbitrary scoring functions, includ ing non-local ones, and its speed decreases slowly with increasing num ber of dimensions. For the local scoring functions, the MC algorithm c an also reproduce known exact solutions for the direct multiple alignm ents. As illustrated by examples, bath for structure- and sequence-bas ed alignments, direct multidimensional alignments are able to capture weak similarities between divergent families much better than ones bui lt from pairwise alignments by a hierarchical approach.