Email updates

Keep up to date with the latest news and content from Proteome Science and BioMed Central.

This article is part of the supplement: Selected articles from the IEEE International Conference on Bioinformatics and Biomedicine 2010

Open Access Open Badges Proceedings

Applications of graph theory in protein structure identification

Yan Yan12, Shenggui Zhang1 and Fang-Xiang Wu2*

Author Affiliations

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

For all author emails, please log on.

Proteome Science 2011, 9(Suppl 1):S17  doi:10.1186/1477-5956-9-S1-S17

Published: 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.