RAPTOR: optimal protein threading by linear programming. This paper presents a novel linear programming approach to do protein 3-dimensional (3D) structure prediction via threading. Based on the contact map graph of the protein 3D structure template, the protein threading problem is formulated as a large scale integer programming (IP) problem. The IP formulation is then relaxed to a linear programming (LP) problem, and then solved by the canonical branch-and-bound method. The final solution is globally optimal with respect to energy functions. In particular, our energy function includes pairwise interaction preferences and allowing variable gaps which are two key factors in making the protein threading problem NP-hard. A surprising result is that, most of the time, the relaxed linear programs generate integral solutions directly. Our algorithm has been implemented as a software package RAPTOR–RApid Protein Threading by Operation Research technique. Large scale benchmark test for fold recognition shows that RAPTOR ignificantly outperforms other programs at the fold similarity level. The CAFASP3 evaluation, a blind and public test by the protein structure prediction community, ranks RAPTOR as top 1, among individual prediction servers, in terms of the recognition capability and alignment accuracy for Fold Recognition (FR) family targets. RAPTOR also performs very well in recognizing the hard Homology Modeling (HM) targets. RAPTOR was implemented at the University of Waterloo.

References in zbMATH (referenced in 17 articles )

Showing results 1 to 17 of 17.
Sorted by year (citations)

  1. Frausto-Solís, Juan; Sánchez-Pérez, Mishael; Lińan-García, Ernesto; Sánchez-Hernández, Juan Paulo: Threshold temperature tuning simulated annealing for protein folding problem in small peptides (2013)
  2. Collet, G.; Andonov, R.; Yanev, N.; Gibrat, J.-F.: Local protein threading by mixed integer programming (2011)
  3. Łukasiak, Piotr; Błaẓewicz, Jacek; Miłostan, Maciej: Some operations research methods for analyzing protein sequences and structures (2010)
  4. McAllister, Scott R.; Floudas, Christodoulos A.: An improved hybrid global optimization method for protein tertiary structure prediction (2010)
  5. Althaus, Ernst; Klau, Gunnar W.; Kohlbacher, Oliver; Lenhof, Hans-Peter; Reinert, Knut: Integer linear programming in computational biology (2009)
  6. Li, Ming: Can we determine a protein structure quickly? (2009)
  7. Berger, Bonnie; Singh, Rohit; Xu, Jinbo: Graph algorithms for biological systems analysis (2008)
  8. Li, Guojun; Liu, Zhijie; Guo, Jun-Tao; Xu, Ying: An algorithm for simultaneous backbone threading and side-chain packing (2008)
  9. Yanev, Nicola; Andonov, Rumen; Veber, Philippe; Balev, Stefan: Lagrangian approaches for a class of matching problems in computational biology (2008)
  10. Ma, Bin; Wu, Lieyu; Zhang, Kaizhong: Improving the sensitivity and specificity of protein homology search by incorporating predicted secondary structures (2005)
  11. Waldispühl, Jér^ome; Steyaert, Jean-Marc: Modeling and predicting all-$\alpha$ transmembrane proteins including helix-helix pairing (2005)
  12. Xu, Jinbo: Rapid protein side-chain packing via tree decomposition (2005)
  13. Andonov, Rumen; Balev, Stefan; Yanev, Nicola: Protein threading: from mathematical models to parallel implementations (2004)
  14. Xu, Jinbo; Li, Ming; Xu, Ying: Protein threading by linear programming: theoretical analysis and computational results (2004)
  15. Xu, Jinbo; Li, Ming; Kim, Dongsup; Xu, Ying: RAPTOR: optimal protein threading by linear programming (2003)
  16. Xu, Jinbo; Li, Ming; Lin, Guohin; Kim, Dongsup; Xu, Ying: Protein threading by linear programming (2002)
  17. Akutsu, Tatsuya; Tashimo, Hiroshi; Dunker, A.K.; Konagaya, A.; Miyano, S.; Takagi, T.: Protein threading using a score function derived by a linear programming based method (1997)