{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T15:59:46Z","timestamp":1742399986551},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"16","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,8,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p><jats:p>Contact: \u00a0eyke@mathematik.uni-marburg.de<\/jats:p><jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp144","type":"journal-article","created":{"date-parts":[[2009,3,14]],"date-time":"2009-03-14T00:49:45Z","timestamp":1236991785000},"page":"2110-2117","source":"Crossref","is-referenced-by-count":19,"title":["Evolutionary construction of multiple graph alignments for the structural analysis of biomolecules"],"prefix":"10.1093","volume":"25","author":[{"given":"Thomas","family":"Fober","sequence":"first","affiliation":[{"name":"1 Department of Mathematics and Computer Science and 2Department of Pharmaceutical Chemistry, Philipps-Universit\u00e4t Marburg, Marburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Mernberger","sequence":"additional","affiliation":[{"name":"1 Department of Mathematics and Computer Science and 2Department of Pharmaceutical Chemistry, Philipps-Universit\u00e4t Marburg, Marburg, Germany"},{"name":"1 Department of Mathematics and Computer Science and 2Department of Pharmaceutical Chemistry, Philipps-Universit\u00e4t Marburg, Marburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerhard","family":"Klebe","sequence":"additional","affiliation":[{"name":"1 Department of Mathematics and Computer Science and 2Department of Pharmaceutical Chemistry, Philipps-Universit\u00e4t Marburg, Marburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eyke","family":"H\u00fcllermeier","sequence":"additional","affiliation":[{"name":"1 Department of Mathematics and Computer Science and 2Department of Pharmaceutical Chemistry, Philipps-Universit\u00e4t Marburg, Marburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2009,3,13]]},"reference":[{"key":"2023013112094563400_B1","volume-title":"Experimental Research in Evolutionary Computation: The New Experimentalism.","author":"Bartz-Beielstein","year":"2006"},{"key":"2023013112094563400_B2","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1093\/nar\/gkh121","article-title":"The Pfam protein families database","volume":"32","author":"Bateman","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023013112094563400_B3","doi-asserted-by":"crossref","first-page":"14689","DOI":"10.1073\/pnas.0305199101","article-title":"Local graph alignment and motif search in biological networks","volume":"101","author":"Berg","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013112094563400_B4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1023\/A:1015059928466","article-title":"Evolution strategies: a comprehensive introduction","volume":"1","author":"Beyer","year":"2002","journal-title":"J. Nat. Comput."},{"key":"2023013112094563400_B5","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1021\/jm981062r","article-title":"Three-dimensional quantitative structure-activity relationship analyses using comparative molecular field analysis and comparative molecular similarity indices analysis to elucidate selectivity differences of inhibitors binding to trypsin, thrombin, and factor xa","volume":"42","author":"B\u00f6hm","year":"1999","journal-title":"J. Med. Chem."},{"key":"2023013112094563400_B6","doi-asserted-by":"crossref","first-page":"i95","DOI":"10.1093\/bioinformatics\/btg1012","article-title":"MASS: multiple structural alignment by secondary structures","volume":"19","author":"Dror","year":"2003","journal-title":"Bioinformatics"},{"key":"2023013112094563400_B7","doi-asserted-by":"crossref","DOI":"10.1002\/3527601643","volume-title":"Chemoinformatics.","author":"Gasteiger","year":"2003"},{"key":"2023013112094563400_B8","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/S0959-440X(96)80058-3","article-title":"Surprising similarities in structure comparison","volume":"6","author":"Gibrat","year":"1996","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023013112094563400_B9","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/S1093-3263(98)00002-3","article-title":"LIGSITE: automatic and efficient detection of potential small molecule-binding sites in proteins","volume":"15","author":"Hendlich","year":"1997","journal-title":"J. Mol. Graph. Model."},{"key":"2023013112094563400_B10","doi-asserted-by":"crossref","first-page":"3256","DOI":"10.1016\/S0021-9258(18)69064-7","article-title":"The binding of L-valyl-L-tryptophan to crystalline thermolysin illustrates the mode of interaction of a product of peptide hydrolysis","volume":"263","author":"Holden","year":"1988","journal-title":"J. Biol. Chem."},{"key":"2023013112094563400_B11","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1021\/bi00646a016","article-title":"Esterase activity of zinc neutral proteases","volume":"15","author":"Holmquist","year":"1976","journal-title":"Biochemistry"},{"key":"2023013112094563400_B12","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1002\/prot.10339","article-title":"A new bioinformatic approach to detect common 3D sites in protein structures","volume":"52","author":"Jambon","year":"2003","journal-title":"Protein Struct. Funct. Genet."},{"key":"2023013112094563400_B13","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1107\/S0567739476001873","article-title":"A solution of the best rotation to relate two sets of vectors","volume":"32","author":"Kabsch","year":"1976","journal-title":"Acta Crystallogr."},{"key":"2023013112094563400_B14","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1110\/ps.041080105","article-title":"Identification of the ligand binding sites on the molecular surface of proteins","volume":"14","author":"Kinoshita","year":"2005","journal-title":"Protein Sci."},{"key":"2023013112094563400_B15","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1089\/106652701300312896","article-title":"MUSTA-A general, efficient, automated method for multiple structure alignment and detection of common motifs: application to proteins","volume":"8","author":"Leibowitz","year":"2001","journal-title":"J. Comput. Biol."},{"key":"2023013112094563400_B16","doi-asserted-by":"crossref","first-page":"3141","DOI":"10.1002\/1521-3773(20010903)40:17<3141::AID-ANIE3141>3.0.CO;2-X","article-title":"From structure to function: a new approach to detect functional similarity among proteins independent from sequence and fold homology","volume":"40","author":"Schmitt","year":"2001","journal-title":"Angew. Chem. Int. Edit."},{"key":"2023013112094563400_B17","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/S0022-2836(02)00811-2","article-title":"A new method to detect related function among proteins independent of sequence and fold homology","volume":"323","author":"Schmitt","year":"2002","journal-title":"J. Mol. Biol."},{"key":"2023013112094563400_B18","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1093\/bib\/3.3.246","article-title":"Prodom: automated clustering of homologous domains","volume":"3","author":"Servant","year":"2002","journal-title":"Brief. Bioinform."},{"key":"2023013112094563400_B19","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/543613.543620","article-title":"Algorithmics and applications of tree and graph searching","volume-title":"Proceedings of the 21th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.","author":"Shasha","year":"2002"},{"key":"2023013112094563400_B20","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1002\/prot.10628","article-title":"A method for Simultaneous Alignment of Multiple Protein Structures","volume":"56","author":"Shatsky","year":"2004","journal-title":"Protein Struct. Funct. Bioinform."},{"key":"2023013112094563400_B21","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1089\/cmb.2006.13.407","article-title":"The multiple common point set problem and its application to molecule binding pattern detection","volume":"13","author":"Shatsky","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023013112094563400_B22","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1021\/ci0255984","article-title":"Searching for patterns of amino acids in 3D protein structures","volume":"43","author":"Spriggs","year":"2003","journal-title":"J. Chem. Inform. Comp. Sci."},{"key":"2023013112094563400_B23","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","article-title":"Clustal W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice","volume":"22","author":"Thompson","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"2023013112094563400_B24","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1109\/TCBB.2007.1024","volume":"4","author":"Weskamp","year":"2007","journal-title":"IEEE Trans. Comput. Biol. Bioinform."},{"key":"2023013112094563400_B25","first-page":"335","article-title":"Graph indexing: a frequent structure-based approach","volume-title":"ACM SIGMOD International Conference on Management of Data.","author":"Yan","year":"2004"},{"key":"2023013112094563400_B26","first-page":"766","article-title":"Substructure similarity search in graph databases","volume-title":"ACM SIGMOD International Conference on Management of Data.","author":"Yan","year":"2005"},{"key":"2023013112094563400_B27","article-title":"Searching substructures with superimposed distance","volume-title":"International Conference on Data Engineering","author":"Yan","year":"2006"},{"key":"2023013112094563400_B28","first-page":"966","article-title":"Treepi: a novel graph indexing method","volume-title":"23th International Conference on Data Engineering.","author":"Zhang","year":"2007"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/16\/2110\/48993983\/bioinformatics_25_16_2110.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/16\/2110\/48993983\/bioinformatics_25_16_2110.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T16:51:27Z","timestamp":1710175887000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/16\/2110\/204070"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,13]]},"references-count":28,"journal-issue":{"issue":"16","published-print":{"date-parts":[[2009,8,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp144","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,8,15]]},"published":{"date-parts":[[2009,3,13]]}}}