Evolutionary Construction of Multiple Graph Alignments for the Structural Analysis of Biomolecules

Abstract: The concept of multiple graph alignment has recently been introduced as a novel method for the structural analysis of biomolecules. Using inexact, approximate graph-matching techniques, this method enables the robust identification of appro-ximately conserved patterns in biologically related structures. In particular, multiple graph alignments enable the characterization of functional protein families indepen-dent of sequence or fold homology. This paper first recalls the concept of multiple graph alignment and then addresses the problem of computing optimal alignments from an algorithmic point of view. In this regard, a method from the field of evolu-tionary algorithms is proposed and empirically compared to a hitherto existing greedy strategy. Empirically, it is shown that the former yields significantly better results than the latter, albeit at the cost of an increased runtime.