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
Linear graph vs. partial order graph. Aligning five trajectories (IDs 1 to 5) using (a) a linear graph, and (b) a partial order graph. Symbols in the circles are the node IDs and numbers on edges are trajectory IDs. Note that the linear alignment in (a) will not be able to record the partial similarity between curves 3 and 4, which is maintained in (b) (i.e, node d).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 1: Linear graph vs. partial order graph. Aligning five trajectories (IDs 1 to 5) using (a) a linear graph, and (b) a partial order graph. Symbols in the circles are the node IDs and numbers on edges are trajectory IDs. Note that the linear alignment in (a) will not be able to record the partial similarity between curves 3 and 4, which is maintained in (b) (i.e, node d).

Mentions: In this paper, we propose and develop a sensitive MCC algorithm, called the EPO (enhanced partial order) algorithm, to compare a set of diverse high dimensional curves. Our algorithm follows a similar framework as the POA algorithm [3,28] to encode the similarities of aligned curves in a partial order graph, instead of in a linear structure used by many traditional MSTA algorithms. This has the advantage that other than similarities among all curves, similarities among a subset of input curves can also be encoded in this graph. See Figure 1 for an example, where nodes in both graphs represent a group of aligned points from input curves.


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)

Linear graph vs. partial order graph. Aligning five trajectories (IDs 1 to 5) using (a) a linear graph, and (b) a partial order graph. Symbols in the circles are the node IDs and numbers on edges are trajectory IDs. Note that the linear alignment in (a) will not be able to record the partial similarity between curves 3 and 4, which is maintained in (b) (i.e, node d).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 1: Linear graph vs. partial order graph. Aligning five trajectories (IDs 1 to 5) using (a) a linear graph, and (b) a partial order graph. Symbols in the circles are the node IDs and numbers on edges are trajectory IDs. Note that the linear alignment in (a) will not be able to record the partial similarity between curves 3 and 4, which is maintained in (b) (i.e, node d).
Mentions: In this paper, we propose and develop a sensitive MCC algorithm, called the EPO (enhanced partial order) algorithm, to compare a set of diverse high dimensional curves. Our algorithm follows a similar framework as the POA algorithm [3,28] to encode the similarities of aligned curves in a partial order graph, instead of in a linear structure used by many traditional MSTA algorithms. This has the advantage that other than similarities among all curves, similarities among a subset of input curves can also be encoded in this graph. See Figure 1 for an example, where nodes in both graphs represent a group of aligned points from input curves.

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