RANKING VALID TOPOLOGIES OF THE SECONDARY STRUCTURE ELEMENTS USING A CONSTRAINT GRAPH

摘要

Electron cryo-microscopy is a fast advancing biophysical technique to derive threedimensionalnstructures of large protein complexes. Using this technique, many densitynmaps have been generated at intermediate resolution such as 6–10°A resolution.nAlthough it is challenging to derive the backbone of the protein directly from such densitynmaps, secondary structure elements such as helices and β-sheets can be computationallyndetected. Our work in this paper provides an approach to enumerate the top-rankednpossible topologies instead of enumerating the entire population of the topologies. Thisnapproach is particularly practical for large proteins. We developed a directed weightedngraph, the topology graph, to represent the secondary structure assignment problem.Wenprove that the problem of finding the valid topology with the minimum cost is NP hard.nWe developed an O(N22N) dynamic programming algorithm to identify the topologynwith the minimum cost. The test of 15 proteins suggests that our dynamic programmingnapproach is feasible to work with proteins of much larger size than we could before. Thenlargest protein in the test contains 18 helical sticks detected from the density map outnof 33 helices in the protein.