Evolutionary Construction of Multiple Graph Alignments for the Structural

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 identification of approximately conserved patterns in biologically related structures. In par-ticular, multiple graph alignment enables the characterization of functional protein families independent of sequence or fold homology. This paper first recalls the concept of multiple graph alignment and then addresses the prob-lem of computing optimal alignments from an algorithmic point of view. In this regard, a method from the field of evolutionary algorithms is proposed and empirically compared to a hitherto existing heuristic approach. Empiri-cally, it is shown that the former yields significantly better results than the latter, albeit at the cost of an increased runtime.