Limits...
Introducing TreeCollapse: a novel greedy algorithm to solve the cophylogeny reconstruction problem.

Drinkwater B, Charleston MA - BMC Bioinformatics (2014)

Bottom Line: This approach offers a significant speed-up compared to previous methods, running in linear time.As a result, we argue that the newly proposed algorithm is a valuable addition to the field of coevolutionary research.Not only does it offer a significantly faster method to estimate the cost of cophylogeny mappings but by using this approach, in conjunction with existing heuristics, it can assist in recovering a larger subset of the Pareto front than has previously been possible.

View Article: PubMed Central - HTML - PubMed

ABSTRACT

Background: Cophylogeny mapping is used to uncover deep coevolutionary associations between two or more phylogenetic histories at a macro coevolutionary scale. As cophylogeny mapping is NP-Hard, this technique relies heavily on heuristics to solve all but the most trivial cases. One notable approach utilises a metaheuristic to search only a subset of the exponential number of fixed node orderings possible for the phylogenetic histories in question. This is of particular interest as it is the only known heuristic that guarantees biologically feasible solutions. This has enabled research to focus on larger coevolutionary systems, such as coevolutionary associations between figs and their pollinator wasps, including over 200 taxa. Although able to converge on solutions for problem instances of this size, a reduction from the current cubic running time is required to handle larger systems, such as Wolbachia and their insect hosts.

Results: Rather than solving this underlying problem optimally this work presents a greedy algorithm called TreeCollapse, which uses common topological patterns to recover an approximation of the coevolutionary history where the internal node ordering is fixed. This approach offers a significant speed-up compared to previous methods, running in linear time. This algorithm has been applied to over 100 well-known coevolutionary systems converging on Pareto optimal solutions in over 68% of test cases, even where in some cases the Pareto optimal solution has not previously been recoverable. Further, while TreeCollapse applies a local search technique, it can guarantee solutions are biologically feasible, making this the fastest method that can provide such a guarantee.

Conclusion: As a result, we argue that the newly proposed algorithm is a valuable addition to the field of coevolutionary research. Not only does it offer a significantly faster method to estimate the cost of cophylogeny mappings but by using this approach, in conjunction with existing heuristics, it can assist in recovering a larger subset of the Pareto front than has previously been possible.

Show MeSH

Related in: MedlinePlus

Jane's Mapping The mapping produced by Jane for the primate / malaria tanglegram.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
getmorefigures.php?uid=PMC4290644&req=5

Figure 9: Jane's Mapping The mapping produced by Jane for the primate / malaria tanglegram.

Mentions: The mappings recovered for the primate-malaria tanglegram for TreeCollapse, Jane and CoRe-PA can be seen in Figures 8, 9 and 10. The respective parsimony scores for each of these mappings were 24 for both TreeCollapse and Jane and 23 for CoRe-PA. Figure 10 highlights that CoRe-PA's reduced parsimony score compared to Jane and TreeCollapse is due to the time-inconsistent switch (coloured in red), which gives rise to three additional codivergence events. Jane and TreeCollpase, however, both reported solutions which are time-consistent but portray contrasting views of the origin of the parasite divergence within the host phylogeny, with TreeCollapse suggesting a longer evolutionary history between primates and malaria. This mapping further indicates a higher number of codivergence events, resulting in a more congruent reconstruction.


Introducing TreeCollapse: a novel greedy algorithm to solve the cophylogeny reconstruction problem.

Drinkwater B, Charleston MA - BMC Bioinformatics (2014)

Jane's Mapping The mapping produced by Jane for the primate / malaria tanglegram.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
Show All Figures
getmorefigures.php?uid=PMC4290644&req=5

Figure 9: Jane's Mapping The mapping produced by Jane for the primate / malaria tanglegram.
Mentions: The mappings recovered for the primate-malaria tanglegram for TreeCollapse, Jane and CoRe-PA can be seen in Figures 8, 9 and 10. The respective parsimony scores for each of these mappings were 24 for both TreeCollapse and Jane and 23 for CoRe-PA. Figure 10 highlights that CoRe-PA's reduced parsimony score compared to Jane and TreeCollapse is due to the time-inconsistent switch (coloured in red), which gives rise to three additional codivergence events. Jane and TreeCollpase, however, both reported solutions which are time-consistent but portray contrasting views of the origin of the parasite divergence within the host phylogeny, with TreeCollapse suggesting a longer evolutionary history between primates and malaria. This mapping further indicates a higher number of codivergence events, resulting in a more congruent reconstruction.

Bottom Line: This approach offers a significant speed-up compared to previous methods, running in linear time.As a result, we argue that the newly proposed algorithm is a valuable addition to the field of coevolutionary research.Not only does it offer a significantly faster method to estimate the cost of cophylogeny mappings but by using this approach, in conjunction with existing heuristics, it can assist in recovering a larger subset of the Pareto front than has previously been possible.

View Article: PubMed Central - HTML - PubMed

ABSTRACT

Background: Cophylogeny mapping is used to uncover deep coevolutionary associations between two or more phylogenetic histories at a macro coevolutionary scale. As cophylogeny mapping is NP-Hard, this technique relies heavily on heuristics to solve all but the most trivial cases. One notable approach utilises a metaheuristic to search only a subset of the exponential number of fixed node orderings possible for the phylogenetic histories in question. This is of particular interest as it is the only known heuristic that guarantees biologically feasible solutions. This has enabled research to focus on larger coevolutionary systems, such as coevolutionary associations between figs and their pollinator wasps, including over 200 taxa. Although able to converge on solutions for problem instances of this size, a reduction from the current cubic running time is required to handle larger systems, such as Wolbachia and their insect hosts.

Results: Rather than solving this underlying problem optimally this work presents a greedy algorithm called TreeCollapse, which uses common topological patterns to recover an approximation of the coevolutionary history where the internal node ordering is fixed. This approach offers a significant speed-up compared to previous methods, running in linear time. This algorithm has been applied to over 100 well-known coevolutionary systems converging on Pareto optimal solutions in over 68% of test cases, even where in some cases the Pareto optimal solution has not previously been recoverable. Further, while TreeCollapse applies a local search technique, it can guarantee solutions are biologically feasible, making this the fastest method that can provide such a guarantee.

Conclusion: As a result, we argue that the newly proposed algorithm is a valuable addition to the field of coevolutionary research. Not only does it offer a significantly faster method to estimate the cost of cophylogeny mappings but by using this approach, in conjunction with existing heuristics, it can assist in recovering a larger subset of the Pareto front than has previously been possible.

Show MeSH
Related in: MedlinePlus