title: Solving the Secondary Structure Matching Problem in Cryo-EM De Novo Modeling Using a Constrained K-Shortest Path Graph Algorithm.
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 Å. 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)N(2)2(N)) 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.
authors.forename: Kamal
authors.initials: K
authors.lastname: Al Nasr
authors.forename: Desh
authors.initials: D
authors.lastname: Ranjan
authors.forename: Mohammad
authors.initials: M
authors.lastname: Zubair
authors.forename: Lin
authors.initials: L
authors.lastname: Chen
authors.forename: Jing
authors.initials: J
authors.lastname: He
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D020285:Cryoelectron Microscopy / Q000379:methods*; D021621:Imaging, Three-Dimensional; D008958:Models, Molecular; D017433:Protein Structure, Secondary; D011506:Proteins / Q000737:chemistry*
chemical_list: D011506:Proteins