IMPROVED EFFICIENCY IN CRYO-EM SECONDARY STRUCTURE TOPOLOGY DETERMINATION FROM INACCURATE DATA

摘要

The determination of the secondary structure topology is a critical step in deriving the atomicnstructure from the protein density map obtained from electron cryo-microscopy technique. Thisnstep often relies on the matching of two sources of information. One source comes from thensecondary structures detected from the protein density map at the medium resolution, such asn5u000110Å. The other source comes from the predicted secondary structures from the amino acidnsequence. Due to the inaccuracy in either source of information, a pool of possible secondarynstructure positions needs to be sampled. This paper studies the question, that is, how to reducenthe computation of the mapping when the inaccuracy of the secondary structure predictions isnconsidered.We present a method that combines the concept of dynamic graph with our previousnwork of using constrained shortest path to identify the topology of the secondary structures. Wenshow a reduction of 34.55% of run-time as comparison to the naïve way of handling the inaccuracies.nWe also show an improved accuracy when the potential secondary structure errors arenexplicitly sampled verses the use of one consensus prediction. Our framework demonstrated thenpotential of developing computationally e®ective exact algorithms to identify the optimalntopology of the secondary structures when the inaccuracy of the predicted data is considered.