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
The merging algorithm.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 9: The merging algorithm.

Mentions: A high level pseudocode of the merging process is shown in Figure 9. It augments better aligned nodes from the current POG G by processing first the nodes with larger size. We perform this procedure a few times till there is no significant increase in the quality of the resulting alignment. In practice, to speed up the algorithm, we merge neighbors to a node o only if its size is greater than some threshold (fixed at half of the size threshold, i.e, τ/2, in our experiments), as otherwise, there is low probability that o will become a heavy node later.


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)

The merging algorithm.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 9: The merging algorithm.
Mentions: A high level pseudocode of the merging process is shown in Figure 9. It augments better aligned nodes from the current POG G by processing first the nodes with larger size. We perform this procedure a few times till there is no significant increase in the quality of the resulting alignment. In practice, to speed up the algorithm, we merge neighbors to a node o only if its size is greater than some threshold (fixed at half of the size threshold, i.e, τ/2, in our experiments), as otherwise, there is low probability that o will become a heavy node later.

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