Solving the Secondary Structure Matching Problem in Cryo-EM De Novo Modeling Using a Constrained K-Shortest Path...

Area of Science:

• Structural biology
• Computational biology
• Biophysics

Background:

• Electron cryomicroscopy (cryo-EM) is a key technique for determining the structures of large molecular assemblies.
• Medium-resolution (5-10 Å) cryo-EM images reveal secondary structure elements like alpha-helices and beta-sheets.
• Accurate matching of detected secondary structures to protein sequences is crucial for de novo modeling.

Purpose of the Study:

• To develop an efficient algorithm for matching secondary structures from cryo-EM images to protein sequences.
• To address the NP-Hard problem of de novo protein modeling from medium-resolution cryo-EM data.
• To improve the accuracy, speed, and memory efficiency of topological derivation for protein secondary structures.

Main Methods:

• Formulated the secondary structure matching problem as a constrained graph problem.
• Developed an algorithm, DP-TOSS, combining dynamic programming with a constrained K-shortest path approach.
• Tested the algorithm on alpha-proteins and alpha-beta proteins with varying numbers of helices and beta-strands.

Main Results:

• DP-TOSS correctly matched secondary structures within the top 35 rankings for 19 out of 20 alpha-proteins.
• The method achieved correct matches for all nine tested alpha-beta proteins.
• Demonstrated improved accuracy, time efficiency, and memory space compared to existing methods for complex protein structures.

Conclusions:

• DP-TOSS provides an effective solution for the de novo modeling of protein structures from cryo-EM data.
• The algorithm enhances the ability to derive secondary structure element topologies, particularly for large and complex molecular assemblies.
• This work advances the field of structural biology by improving computational approaches to protein structure determination using cryo-EM.