2014AlNasr Secondary

Citation

Al Nasr, K.; Ranjan, D.; Zubair, M.; Chen, L.; He, J. K. Solving the Secondary Structure Matching Problem in Cryo-EM De Novo Modeling Using a Constrained K-Shortest Path Graph Algorithm. IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 11, no. 2, pp. 419-430, March-April 2014, doi: 10.1109/TCBB.2014.2302803.

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 AA$. At this resolution range, major $alpha$-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({rm Delta }^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 $alpha{hbox{-}}beta$ proteins up to five helices and 12 $beta$-strands. The correct match was ranked within the top 35 for 19 of the 20 α-proteins and all nine $alpha {hbox{-}}beta$ 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.

Links

https://ieeexplore.ieee.org/document/6727403