title: Evolutionary construction of multiple graph alignments for the structural analysis of biomolecules.
abstract: The concept of multiple graph alignment (MGA) 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 particular, MGA enables the characterization of functional protein families independent of sequence or fold homology. This article first recalls the concept of MGA and then addresses the problem 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 with a hitherto existing heuristic approach. Empirically, it is shown that the former yields significantly better results than the latter, albeit at the cost of an increased runtime.
authors.affiliation: Department of Mathematics and Computer Science, Philipps-Universität Marburg, Marburg, Germany.
authors.forename: Thomas
authors.initials: T
authors.lastname: Fober
authors.forename: Marco
authors.initials: M
authors.lastname: Mernberger
authors.forename: Gerhard
authors.initials: G
authors.lastname: Klebe
authors.forename: Eyke
authors.initials: E
authors.lastname: Hüllermeier
mesh_terms: D000465:Algorithms; D001665:Binding Sites; D019295:Computational Biology / Q000379:methods*; D003196:Computer Graphics; D030562:Databases, Protein; D025941:Protein Interaction Mapping; D011506:Proteins / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods; D020539:Sequence Analysis, Protein / Q000379:methods
chemical_list: D011506:Proteins