Digital Biology Laboratory, Department of Computer Science, University of Missouri-Columbia Columbia, MO 6.5211, USA

摘要

Understanding how protein folds into a functional and structural configuration is arguably one of the most important and challenging problems in computational biology Currently, the protein folding mechanism is often characterized by calculating the free energy landscape versus the reaction coordinates such as the fraction of native contacts, the radius of gyration, the principal components and so on In this paper, we present a combinatorial algorithmic approach towards understanding the global state changes of the configurations The approach is based on cluster computation, each cluster being denned by a pattern of a combination of various reaction coordinates We present an algorithm of time complexity O((N + nm) log n) where JV is the size of the output and nxmis the size of the input To date, this is the best time complexity for the problem. We next demonstrate that this approach extracts crucial information about protein folding intermediate states and mechanism (1) The method recovers states previously obtained by visually analyzing free energy contour maps, (2) It also succeeds in extracting meaningful patterns and structures that had been overlooked in previous works, which provide a better understanding of the folding mechanism (of a /3-hairpin protein) These new patterns also interconnect various states in existing free energy contour maps versus different reaction coordinates (3) The approach does not require the free energy values, yet it offers analysis comparable and sometimes better than the methods that use free energy landscapes, thus validating the choice of reaction coordinates.