2014AlNasr Secondary

Citation

Al Nasr, K.; Ranjan, D.; Zubair, M.; Chen, L.; He, J.

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

http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6727403