Solving the secondary structure matchingproblem in Cryo-EM de novo modeling using a constrained K-shortest path graph algorithm

Kamal Al Nasr, Desh Ranjan, Mohammad Zubair, Lin Chen, Jing He

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

Electron cryomicroscopy is becoming a major experimental technique in solving the structures of large molecular assemblies. More and more three-dimensional images have been obtained at the medium resolutions between 5 and 10 A°. At this resolution range, major α-helices can be detected as cylindrical sticks and β-sheets can be detected as plain-like regions. A critical question in de novo modeling from cryo-EM images is to determine the match between the detected secondary structures from the image and those on the protein sequence. We formulate this matching problem into a constrained graph problem and present an OΔ2 N2 2N) algorithm to this NP-Hard problem. The algorithm incorporates the dynamic programming approach into a constrained K-shortest path algorithm. Our method, DP-TOSS, has been tested using α-proteins with maximum 33 helices and α-β proteins up to five helices and 12 β-strands. The correct match was ranked within the top 35 for 19 of the 20 α-proteins and all nine α-β proteins tested. The results demonstrate that DP-TOSS improves accuracy, time and memory space in deriving the topologies of the secondary structure elements for proteins with a large number of secondary structures and a complex skeleton.

Original languageEnglish (US)
Article number6727403
Pages (from-to)419-430
Number of pages12
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume11
Issue number2
DOIs
StatePublished - 2014
Externally publishedYes

Keywords

  • Protein structure
  • algorithm
  • electron cryomicroscopy
  • graph
  • image
  • secondary structure

ASJC Scopus subject areas

  • Biotechnology
  • Genetics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Solving the secondary structure matchingproblem in Cryo-EM de novo modeling using a constrained K-shortest path graph algorithm'. Together they form a unique fingerprint.

Cite this