This article is part of the supplement: Selected articles from the IEEE International Conference on Bioinformatics and Biomedicine 2010
Applications of graph theory in protein structure identification
1 Department of Applied Mathematics, Northwestern Polytechnical University, Xi’an, Shaanxi 710072, P.R. China
2 Division of Biomedical Engineering, University of Saskatchewan, Saskatoon, SK S7N 5A9, Canada
Proteome Science 2011, 9(Suppl 1):S17 doi:10.1186/1477-5956-9-S1-S17Published: 14 October 2011
There is a growing interest in the identification of proteins on the proteome wide scale. Among different kinds of protein structure identification methods, graph-theoretic methods are very sharp ones. Due to their lower costs, higher effectiveness and many other advantages, they have drawn more and more researchers’ attention nowadays. Specifically, graph-theoretic methods have been widely used in homology identification, side-chain cluster identification, peptide sequencing and so on. This paper reviews several methods in solving protein structure identification problems using graph theory. We mainly introduce classical methods and mathematical models including homology modeling based on clique finding, identification of side-chain clusters in protein structures upon graph spectrum, and de novo peptide sequencing via tandem mass spectrometry using the spectrum graph model. In addition, concluding remarks and future priorities of each method are given.