Limits...
TreeKO: a duplication-aware algorithm for the comparison of phylogenetic trees.

Marcet-Houben M, Gabaldón T - Nucleic Acids Res. (2011)

Bottom Line: To overcome this, we have developed treeKO, an algorithm that enables the comparison of tree topologies, even in the presence of duplication and loss events.To do so treeKO recursively splits gene trees into pruned trees containing only orthologs to subsequently compute a distance based on the combined analyses of all pruned tree comparisons.In addition treeKO, implements the possibility of computing phylome support values, and reconciliation-based measures such as the number of inferred duplication and loss events.

View Article: PubMed Central - PubMed

Affiliation: Centre for Genomic Regulation, UPF, Doctor Aiguader 88, 08003 Barcelona, Spain.

ABSTRACT
Comparisons of tree topologies provide relevant information in evolutionary studies. Most existing methods share the drawback of requiring a complete and exact mapping of terminal nodes between the compared trees. This severely limits the scope of genome-wide analyses, since trees containing duplications are pruned arbitrarily or discarded. To overcome this, we have developed treeKO, an algorithm that enables the comparison of tree topologies, even in the presence of duplication and loss events. To do so treeKO recursively splits gene trees into pruned trees containing only orthologs to subsequently compute a distance based on the combined analyses of all pruned tree comparisons. In addition treeKO, implements the possibility of computing phylome support values, and reconciliation-based measures such as the number of inferred duplication and loss events.

Show MeSH
Example of how treeKO derives pruned trees from a tree containing duplications. The initial tree (tree on the left) contains two duplication nodes (in black) marked as node 1 and node 2. treeKO splits the tree by node 1 and generate two different trees, each one of them containing one of the daughter partitions of node 1. This results in pruned tree 1 and an intermediate pruned tree that still contains duplication (node 2). treeKO will then scan these pruned trees for more duplications. In this case one of the pruned trees has a second duplication and the subtree will be once again split and reconstructed, resulting in pruned trees 2 and 3. treeKO will repeat this process until no resulting subtree contains further duplication nodes.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 1: Example of how treeKO derives pruned trees from a tree containing duplications. The initial tree (tree on the left) contains two duplication nodes (in black) marked as node 1 and node 2. treeKO splits the tree by node 1 and generate two different trees, each one of them containing one of the daughter partitions of node 1. This results in pruned tree 1 and an intermediate pruned tree that still contains duplication (node 2). treeKO will then scan these pruned trees for more duplications. In this case one of the pruned trees has a second duplication and the subtree will be once again split and reconstructed, resulting in pruned trees 2 and 3. treeKO will repeat this process until no resulting subtree contains further duplication nodes.

Mentions: The tree decomposition algorithm implemented in treeKO, proceeds as follows (Figure 1): given an input rooted tree with n labelled duplication nodes, the tree is traversed from the root to the most external nodes. At each duplication node, two daughter trees are produced by alternatively pruning each of the two post-duplication branches. Note that these trees are partially overlapping, since all pre-duplication nodes are retained in both pruned trees. This algorithm is applied recursively on each produced pruned tree that still contains duplications, until no duplication nodes are contained in the resulting set of pruned trees.Figure 1.


TreeKO: a duplication-aware algorithm for the comparison of phylogenetic trees.

Marcet-Houben M, Gabaldón T - Nucleic Acids Res. (2011)

Example of how treeKO derives pruned trees from a tree containing duplications. The initial tree (tree on the left) contains two duplication nodes (in black) marked as node 1 and node 2. treeKO splits the tree by node 1 and generate two different trees, each one of them containing one of the daughter partitions of node 1. This results in pruned tree 1 and an intermediate pruned tree that still contains duplication (node 2). treeKO will then scan these pruned trees for more duplications. In this case one of the pruned trees has a second duplication and the subtree will be once again split and reconstructed, resulting in pruned trees 2 and 3. treeKO will repeat this process until no resulting subtree contains further duplication nodes.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 1: Example of how treeKO derives pruned trees from a tree containing duplications. The initial tree (tree on the left) contains two duplication nodes (in black) marked as node 1 and node 2. treeKO splits the tree by node 1 and generate two different trees, each one of them containing one of the daughter partitions of node 1. This results in pruned tree 1 and an intermediate pruned tree that still contains duplication (node 2). treeKO will then scan these pruned trees for more duplications. In this case one of the pruned trees has a second duplication and the subtree will be once again split and reconstructed, resulting in pruned trees 2 and 3. treeKO will repeat this process until no resulting subtree contains further duplication nodes.
Mentions: The tree decomposition algorithm implemented in treeKO, proceeds as follows (Figure 1): given an input rooted tree with n labelled duplication nodes, the tree is traversed from the root to the most external nodes. At each duplication node, two daughter trees are produced by alternatively pruning each of the two post-duplication branches. Note that these trees are partially overlapping, since all pre-duplication nodes are retained in both pruned trees. This algorithm is applied recursively on each produced pruned tree that still contains duplications, until no duplication nodes are contained in the resulting set of pruned trees.Figure 1.

Bottom Line: To overcome this, we have developed treeKO, an algorithm that enables the comparison of tree topologies, even in the presence of duplication and loss events.To do so treeKO recursively splits gene trees into pruned trees containing only orthologs to subsequently compute a distance based on the combined analyses of all pruned tree comparisons.In addition treeKO, implements the possibility of computing phylome support values, and reconciliation-based measures such as the number of inferred duplication and loss events.

View Article: PubMed Central - PubMed

Affiliation: Centre for Genomic Regulation, UPF, Doctor Aiguader 88, 08003 Barcelona, Spain.

ABSTRACT
Comparisons of tree topologies provide relevant information in evolutionary studies. Most existing methods share the drawback of requiring a complete and exact mapping of terminal nodes between the compared trees. This severely limits the scope of genome-wide analyses, since trees containing duplications are pruned arbitrarily or discarded. To overcome this, we have developed treeKO, an algorithm that enables the comparison of tree topologies, even in the presence of duplication and loss events. To do so treeKO recursively splits gene trees into pruned trees containing only orthologs to subsequently compute a distance based on the combined analyses of all pruned tree comparisons. In addition treeKO, implements the possibility of computing phylome support values, and reconciliation-based measures such as the number of inferred duplication and loss events.

Show MeSH