A New Graph Theoretic Approach for Protein Threading

• Autorzy: Song Y. , Qu J. , Xu Y. , Cai L.

Identyfikatory

DOI

10.3233/FI-2016-1352

• Języki publikacji: EN

Abstrakty

EN

In this paper, we develop a novel graph theoretic approach for protein threading. In order to perform the protein sequence-structure alignment in threading both efficiently and accurately, we develop a graph model to describe the tertiary structure of a protein family and the alignment between a sequence and a family can be efficiently computed with a dynamic programming algorithm when the tree width of the graph model is a small integer. Our experiments show that this new approach is significantly faster than existing tools for threading and can achieve comparable prediction accuracy.

Słowa kluczowe

EN

dynamic programming; graph theoretic approach; protein threading

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 2
• Strony: 151--170
• Opis fizyczny: Bibliogr. 46 poz., rys., tab.

Twórcy

autor

Song Y.

• School of Electronics and Information Science, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang, Jiangsu 212003, China

autor

Qu J.

• Department of Information Technology and Computer Science, Clayton State University Morrow, GA 30260, USA

autor

Xu Y.

• Department of Biochemistry and Molecular Biology, University of Georgia Athens, GA 30602, USA

autor

Cai L.

• Department of Biochemistry and Molecular Biology, University of Georgia Athens, GA 30602, USA

Bibliografia

• [1] Altschul SF, Madden TL, Schaffer AA, Zhang J, Zhang Z, Miller W, Lipman DJ. Gapped BLAST and PSI-BLAST: A New Generation of Protein Database Search Programs. Nucleic Acids Research. 1997; 25(17):3389–3402. doi: 10.1093/nar/25.17.3389.
• [2] Amir E. Efficient Approximation for Triangulation of Minimum Treewidth. In: Proceedings of 17th Conference on Uncertainty in Artificial Intelligence, 2001. p. 7–15. ISBN:1-55860-800-1.
• [3] Arnborg S, Proskurowski A. Linear Time Algorithms for NP-hard Problems Restricted to Partial k-trees. Discrete Applied Mathematics, 1989;23:11–24. doi: 10.1016/0166-218X(89)90031-0.
• [4] Arnborg S, Corneil DG, Proskurowski A. Complexity of Finding Embeddings in A k-tree. SIAM Journal on Algebraic and Discrete Methods, 1987;8:277–284. doi: 10.1137/0608024.
• [5] Bodlaender HL, Koster AMCA. Safe Separators for Tree Width. Discrete Mathematics, 2003;306(3):337–350. doi: 10.1016/j.disc.2005.12.017.
• [6] Chen L,Wu L,Wang Y, Zhang S, ZhangX. Revealing Divergent Evolution, Identifying Circular Permutations and Detecting Active-Sites by Protein Structure Comparison. BMC Structural Biology, 2006;6(1):18. doi:10.1186/1472-6807-6-18.
• [7] Chen P, Han K, Li X, Huang DS. Predicting Key Long-Range Interaction Sites by B-factors. Protein and Peptide Letters, 2008;15(5):478–483. doi: 10.2174/092986608784567573.
• [8] Dong Q, Zhou S, Guan J. A New Taxonomy-Based Protein Fold Recognition Approach Based on Autocross-Covariance Transformation. Bioinformatics, 2009; 25(20): 2655–2662. doi: 10.1093/bioinformatics/btp500.
• [9] Eppstein D. Subgraph Isomorphism in Planar Graphs and Related Problems. Journal of Graph Algorithms and Applications, 1999;3(3):1–27. doi: 10.7155/jgaa.00014.
• [10] Godzik A, Kolinski A, Skolnick J. Topology Fingerprint Approach to The Inverse Folding Problem. Journal of Molecular Biology, 1992;227:227–238. doi:10.1016/0022-2836(92)90693-E.
• [11] Holm L, Sander C. Decision Support System for Evolutionary Classification of Protein Structures. Proceedings of International Conference on Intelligent Systems for Molecular Biology, 1997. p. 140–146. ISSN:1553-0833.
• [12] Huang DS, Huang X. Improved Performance in Protein Secondary Structure Prediction by Combining Multiple Predictions. Protein and Peptide Letters, 2006;13(10):985–991. doi: 10.2174/092986606778777551.
• [13] Huang DS, Yu H. Normalized Feature Vectors: A Novel Alignment-Free Sequence Comparison Method Based on The Numbers of Adjacent Amino Acids. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2013;10(2):457–467. doi: 10.1109/TCBB.2013.10.
• [14] Huang DS, Zheng CH. Independent Component Analysis Based Penalized Discriminant Method for Tumor Classification Using Gene Expression Data. Bioinformatics, 2006;22(15):1855–1862. doi: 10.1093/bioinformatics/btl190.
• [15] Huang X, Huang DS, ZHang GZ, Zhu YP, Li YX. Prediction of Protein Secondary Structure Using Improved Two-Level Neural Network Architecture. Protein and Peptide Letters, 2005;12(8):805–811. doi:10.2174/0929866054864328.
• [16] Kumar M, Bhasin M, Natt NK, Raghava BGPS. Prediction of _-hairpins in A Protein from Multiple Alignment Information Using ANN and SVM Techniques. Nucleic Acids Research, 2005;33(Web Server Issue):W154-159. doi: 10.1093/nar/gki588.
• [17] Jones DT. Protein Secondary Structure Prediction Based on Position-Specific Scoring Matrices. Journal of Molecular Biology, 1999;292(2):195–202. doi: 10.1006/jmbi.1999.3091.
• [18] Kim D, Xu D, Guo J, Ellrott K, Xu Y. Prospect II: Protein Structure Prediction Program for Genome-Scale Applications. Protein Engineering, 2003;16(9):641–650. doi: 10.1093/protein/gzg081.
• [19] Lathrop RH. The Protein Threading Problem with Sequence Amino Acid Interaction Preferences is NPcomplete. Protein Engineering, 1994;7(9):1059–1068. doi: 10.1093/protein/7.9.1059.
• [20] Lindahl E, Elofsson A. Identification of Related Proteins on Family, Superfamily and Fold Level. Journal of Molecular Biology, 2000;295(3):613–625. doi: 10.1006/jmbi.1999.3377.
• [21] Liu C, Song Y. Parameterized Dominating Set Problem in Chordal Graphs: Complexity and Lower Bound. Journal of Combinatorial Optimization, 2009;18(1):87–97. doi: 10.1007/s10878-008-9141-5.
• [22] Liu C, Song Y. Parameterized Complexity and Inapproximability of Dominating Set Problem in Chordal and Near Chordal Graphs. Journal of Combinatorial Optimization, 2011;22(4):684–698. doi: 10.1007/s10878-010-9317-7.
• [23] Matousek J, Thomas R. On The Complexity of Finding iso- and OtherMorphisms for Partial k-trees. Discrete Mathematics, 1992;108:343–364. doi: 10.1016/0012-365X(92)90687-B.
• [24] Robertson N, Seymour PD. Graph Minors II. Algorithmic Aspects of Tree-Width. Journal of Algorithms, 1986;7:309–322. doi: 10.1016/0196-6774(86)90023-4.
• [25] Shi J, Blundell TL, Mizuguchi K. FUGUE: Sequence-Structure Homology Recognition Using Environment-Specific Substitution Tables and Structure-Dependent Gap Penalties. Journal of Molecular Biology, 2001;310(1):243–257. doi: 10.1006/jmbi.2001.4762.
• [26] Söding J. Protein Homology Detection by HMM-HMM Comparison. Bioinformatics, 2005;21(7):951–960. doi: 10.1093/bioinformatics/bti125.
• [27] Song Y, Liu C, Huang X, Malmberg RL, Xu Y, Cai L. Efficient Parameterized Algorithms for Biopolymer Structure-Sequence Alignment. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2006;3(4):423–432. doi: 10.1109/TCBB.2006.52.
• [28] Song Y. A New Parameterized Algorithm for Rapid Peptide Sequencing. PLoS ONE, 2014; 9(2): e87476. doi: 10.1371/journal.pone.0087476.
• [29] Song Y, Chi AY. A New Approach for Parameter Estimation in The Sequence-Structure Alignment of Noncoding RNAs. Journal of Information Science and Engineering, 2015;31(2):597–607.
• [30] Song Y. An Improved Parameterized Algorithm for The Independent Feedback Vertex Set Problem. Theoretical Computer Science, 2014;536(22):25–30. doi: 10.1016/j.tcs.2014.03.031.
• [31] Tong JC, Tammi MT. Prediction of Protein Allergenicity Using Local Description of Amino Acid Sequence. Frontiers in Bioscience, 2008;13(16):6072–6078. doi: 10.2741/3138.
• [32] Wang B, Chen P, Huang DS, Li JJ, Lok TM, Lyu MR. Predicting Protein Interaction Sites from Residue Spatial Sequence Profile and Evolution Rate. FEBS Letters, 2006;580(2):380–384. doi: 10.1016/j.febslet.2005.11.081.
• [33] Wang B, Huang DS, Jiang C. A New Strategy for Protein Interface Identification Using Manifold Learning Method. IEEE Transactions on NanoBioscience, 2014;13(2):118–123. doi: 10.1109/TNB.2014.2316997.
• [34] Wang G, Dunbrack Jr RL. PISCES: a Protein Sequence Culling Server. Bioinformatics, 2000;16:257–268. doi: 10.1093/bioinformatics/btg224.
• [35] Wu S, Zhang Y. MUSTER: Improving Protein Sequence Profile-profile Alignments by Using Multiple Sources of Structure Information. Proteins, 2008;72(2):547–556. doi: 10.1002/prot.21945.
• [36] Xu Y, Xu D, Uberbacher EC. An Efficient Computational Method for Globally Optimal Threading. Journal of Computational Biology,1998;5:597–614. doi: 10.1089/cmb.1998.5.597.
• [37] Xu J, Li M, Kim D, Xu Y. RAPTOR: Optimal Protein Threading by Linear Programming. Journal of Bioinformatics and Computational Biology, 2003;1(1):95–117. doi: 10.1142/S0219720003000186.
• [38] Xu J, Li M, Kim D, Xu Y. Protein Threading by Linear Programming. In: Biocomputing: Proceedings of the 2003 Pacific Symposium, 2003. p. 264–275. doi: 10.1142/9789812776303 0025.
• [39] Xu J. Rapid Problem Side-Chain Packing via Tree Decomposition. In: Proceedings of the Ninth Annual International Conference on Research in Computational Molecular Biology, 2005. p. 423–429. doi:10.1007/11415770 32.
• [40] Xu J, Jiao F, Berger B. A Tree-Decomposition Approach to Protein Structure Prediction. In: Proceedings of the 2005 IEEE Computational Systems Bioinformatics Conference, 2005. p. 247–256. doi: 10.1109/CSB. 2005.9.
• [41] Zhang X, Wang Y, Zhan Z, Wu L, Chen L. Exploring Protein’s Optimal HP Configurations by Self-Organiziing Mapping. Journal of Bioinformatics and Computational Biology, 2006;3(2):385–400. doi: 10.1142/S0219720005001107.
• [42] Zhang GZ, Huang DS. Prediction of Inter-residue Contacts Map Based on Genetic Algorithm Optimized Radial Basis Function Neural Network and Binary Input Encoding Scheme. Journal of Computer Aided Molecular Design, 2014;18(12):797–810. doi: 10.1007/s10822-005-0578-7.
• [43] Zhang GZ, Huang DS, Zhu Y, Li Y. Improving Protein Secondary Structure Prediction by Using Residue Conformational Classes. Pattern Recognition Letters, 2005;26(15):2346–2352. doi: 10.1016/j.patrec.2005.04.010.
• [44] Zhang GZ, Huang DS. Inter-residue Spatial Distance Prediction by Using Intergrating GA with RBFNN. Protein and Peptide Letters, 2004;11(6):571-576. doi: 10.2174/0929866043406283.
• [45] Zhu L, You Z, Huang DS, Wang B. t-LSE: A Novel Robust Geometric Approach for Modeling Protein-Protein Interaction Networks. PLoS ONE, 2013;8(4):e58368. doi: 10.1371/journal.pone.0058368.
• [46] Zhu J, Weng Z. FAST: A Novel Protein Structure Alignment Algorithm. Proteins: Structure, Function and Bioinformatics, 2005;58(3): 618–627. doi: 10.1002/prot.20331.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.