Evolutionary construction of multiple graph alignments for the structural analysis of biomolecules

Both authors contributed equally to this work The concept of multiple graph alignment has recently been introduced as a novel method for the structural analysis of biomolecules. Using approximate graph matching techniques, this method enables the robust identication of approximately conserved patterns in biologically related structures. In particular, multiple graph alignment enables the characterization of functional protein families independent of sequence or fold homology. This paper rst 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 eld of evolutionary algorithms is proposed and empirically compared to a hitherto existing heuristic approach. Empirically, it is shown that the former yields signicantly better results than the latter, albeit at the cost of an increased runtime.