Limits...
An enhanced partial order curve comparison algorithm and its application to analyzing protein folding trajectories.

Sun H, Ferhatosmanoglu H, Ota M, Wang Y - BMC Bioinformatics (2008)

Bottom Line: Current computation power enables researchers to produce a huge amount of folding simulation data.Hence there is a pressing need to be able to interpret and identify novel folding features from them.We demonstrate its generality and effectiveness by applying it to aligning multiple protein structures with low similarities.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science and Engineering, The Ohio State University, Columbus, OH 43210, USA. sun.82@osu.edu

ABSTRACT

Background: Understanding how proteins fold is essential to our quest in discovering how life works at the molecular level. Current computation power enables researchers to produce a huge amount of folding simulation data. Hence there is a pressing need to be able to interpret and identify novel folding features from them.

Results: In this paper, we model each folding trajectory as a multi-dimensional curve. We then develop an effective multiple curve comparison (MCC) algorithm, called the enhanced partial order (EPO) algorithm, to extract features from a set of diverse folding trajectories, including both successful and unsuccessful simulation runs. The EPO algorithm addresses several new challenges presented by comparing high dimensional curves coming from folding trajectories. A detailed case study on miniprotein Trp-cage 1 demonstrates that our algorithm can detect similarities at rather low level, and extract biologically meaningful folding events.

Conclusion: The EPO algorithm is general and applicable to a wide range of applications. We demonstrate its generality and effectiveness by applying it to aligning multiple protein structures with low similarities. For user's convenience, we provide a web server for the algorithm at http://db.cse.ohio-state.edu/EPO.

Show MeSH
A POG G of 5 nodes. Note that there is a partial order constraint a ≺d even though there is no edge between them. Both ⟨ a, b, c, d, e⟩ and ⟨a, c, b, d, e⟩ are valid partial order lists w.r.t. G.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC2571979&req=5

Figure 5: A POG G of 5 nodes. Note that there is a partial order constraint a ≺d even though there is no edge between them. Both ⟨ a, b, c, d, e⟩ and ⟨a, c, b, d, e⟩ are valid partial order lists w.r.t. G.

Mentions: Before we formally define the MCC problem, we introduce some necessary notations. Given a set of elements V = {v1,..., vl}, a relation ≺ over V is transitive if vi ≺vj and vj ≺vk imply that vi ≺vk. In this paper, we also refer to vi ≺vj as a partial order constraint. A partial order graph (POG) G = (V, E) is a directed acyclic graph with V = {v1,..., vl}, where vi ≺vj if there is an edge (vi, vj). Note that by the transitivity of this relation, two nodes may have a partial order constraint even when there is no edge between them in G. Let R be the set of partial order constraints induced by G. We say that a permutation Π(V) of V is a partial order list w.r.t. G if for any vi ≺vj ∈ R, we have that vi appears before vj in the permutation Π(V). In other words, the linear order in Π(V) is a total order satisfying all partial order constraints induced from G. See Figure 5 for an example.


An enhanced partial order curve comparison algorithm and its application to analyzing protein folding trajectories.

Sun H, Ferhatosmanoglu H, Ota M, Wang Y - BMC Bioinformatics (2008)

A POG G of 5 nodes. Note that there is a partial order constraint a ≺d even though there is no edge between them. Both ⟨ a, b, c, d, e⟩ and ⟨a, c, b, d, e⟩ are valid partial order lists w.r.t. G.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC2571979&req=5

Figure 5: A POG G of 5 nodes. Note that there is a partial order constraint a ≺d even though there is no edge between them. Both ⟨ a, b, c, d, e⟩ and ⟨a, c, b, d, e⟩ are valid partial order lists w.r.t. G.
Mentions: Before we formally define the MCC problem, we introduce some necessary notations. Given a set of elements V = {v1,..., vl}, a relation ≺ over V is transitive if vi ≺vj and vj ≺vk imply that vi ≺vk. In this paper, we also refer to vi ≺vj as a partial order constraint. A partial order graph (POG) G = (V, E) is a directed acyclic graph with V = {v1,..., vl}, where vi ≺vj if there is an edge (vi, vj). Note that by the transitivity of this relation, two nodes may have a partial order constraint even when there is no edge between them in G. Let R be the set of partial order constraints induced by G. We say that a permutation Π(V) of V is a partial order list w.r.t. G if for any vi ≺vj ∈ R, we have that vi appears before vj in the permutation Π(V). In other words, the linear order in Π(V) is a total order satisfying all partial order constraints induced from G. See Figure 5 for an example.

Bottom Line: Current computation power enables researchers to produce a huge amount of folding simulation data.Hence there is a pressing need to be able to interpret and identify novel folding features from them.We demonstrate its generality and effectiveness by applying it to aligning multiple protein structures with low similarities.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science and Engineering, The Ohio State University, Columbus, OH 43210, USA. sun.82@osu.edu

ABSTRACT

Background: Understanding how proteins fold is essential to our quest in discovering how life works at the molecular level. Current computation power enables researchers to produce a huge amount of folding simulation data. Hence there is a pressing need to be able to interpret and identify novel folding features from them.

Results: In this paper, we model each folding trajectory as a multi-dimensional curve. We then develop an effective multiple curve comparison (MCC) algorithm, called the enhanced partial order (EPO) algorithm, to extract features from a set of diverse folding trajectories, including both successful and unsuccessful simulation runs. The EPO algorithm addresses several new challenges presented by comparing high dimensional curves coming from folding trajectories. A detailed case study on miniprotein Trp-cage 1 demonstrates that our algorithm can detect similarities at rather low level, and extract biologically meaningful folding events.

Conclusion: The EPO algorithm is general and applicable to a wide range of applications. We demonstrate its generality and effectiveness by applying it to aligning multiple protein structures with low similarities. For user's convenience, we provide a web server for the algorithm at http://db.cse.ohio-state.edu/EPO.

Show MeSH