On the complexity of comparing evolutionary trees | SpringerLink
Skip to main content
Springer Nature Link
Log in

On the complexity of comparing evolutionary trees

Extended abstract

  • Conference paper
  • First Online:
Combinatorial Pattern Matching (CPM 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 937))

Included in the following conference series:

Abstract

We study the computational complexity and approximation of several problems arising in the comparison of evolutionary trees. It is shown that the maximum agreement subtree (MAST) problem for three trees with unbounded degree cannot be approximated within ratio \(2^{\log ^\delta n}\)in polynomial time for any δ < 1, unless NP \(\subseteq\)DTIME[2polylog n], and MAST with edge contractions for two binary trees is NP-hard. This answers two open questions posed in [1]. For the maximum refinement subtree (MRST) problem involving two trees, we show that it is polynomialtime solvable when both trees have bounded degree and is NP-hard when one of the trees can have an arbitrary degree. Finally, we consider the problem of optimally transforming a tree into another by transferring subtrees around. It is shown that computing the subtree-transfer distance is NP-hard and an approximation algorithm with performance ratio 3 is given.

Supported in part by NSERC Research Grant OGP0046613 and NSERC/MRC C-GAT Grant GO-12278.

Supported in part by NSERC Research Grant OGP0046373.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. A. Amir and D. Keselman, Maximum agreement subtree in a set of evolutionary trees — metrics and efficient algorithms, IEEE FOCS'94, 1994.

    Google Scholar 

  2. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems, Proc. 33rd IEEE Symp. Found. Comp. Sci., 14–23, 1992.

    Google Scholar 

  3. G. Estabrook, C. Johnson and F. McMorris, A mathematical foundation for the analysis of cladistic character compatibility, Math. Biosci. 29, 181–187, 1976.

    Article  Google Scholar 

  4. M. Farach and M. Thorup, Fast comparison of evolutionary trees, in Proc. 5ith Annual ACM-SIAM Symposium on Discrete Algorithms, 1994.

    Google Scholar 

  5. M. Farach and M. Thorup, Optimal evolutionary tree comparison by sparse dynamic programming, IEEE FOCS'94, 1994.

    Google Scholar 

  6. C. Finden and A. Gordon, Obtaining common pruned trees, Journal of Classification 2, 255–276, 1985.

    Google Scholar 

  7. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.

    Google Scholar 

  8. D. Gusfield, Efficient algorithms for inferring evolutionary trees, Networks 21, 19–28, 1991.

    Google Scholar 

  9. J. Hein, Reconstructing evolution of sequences subject to recombination using parsimony, Math. Biosci. 98, 185–200, 1990

    PubMed  Google Scholar 

  10. J. Hein, A heuristic method to reconstruct the history of sequences subject to recombination, Journal Molecular Evolution 36, 396–405, 1993.

    Google Scholar 

  11. T. Jiang and M. Li, On the approximation of shortest common supersequences and longest common subsequences, to appear in SIAM J. Comput.; also presented at ICALP'94.

    Google Scholar 

  12. T. Jiang, L. Wang and K. Zhang, Alignment of trees — an alternative to tree edit, Theoretical Computer Science 143-1, 137–148, 1995.

    Article  Google Scholar 

  13. V. Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters 37, 27–35, 1991.

    Article  Google Scholar 

  14. J. Kececioglu and D. Gusfield, Reconstructing a history of recombinations from a set of sequences, Proc. 5th ACM-SIAM SODA, 1994.

    Google Scholar 

  15. C.H. Papadimitriou and M. Yannakakis, Optimization, Approximation, and complexity classes, Journal of Computer and System Sciences 43, 425–440, 1991.

    Article  Google Scholar 

  16. M. Steel and T. Warnow, Kaikoura tree theorems: computing the maximum agreement subtree, Information Processing Letters 48, 77–82, 1993.

    Article  Google Scholar 

  17. T. Warnow, Tree compatibility and inferring evolutionary history, J. of Algorithms 16, 388–407, 1994.

    Google Scholar 

  18. T. Warnow, Private communication, 1994.

    Google Scholar 

  19. K. Zhang and D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM J. Comput. 18, 1245–1262, 1989.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute for Genetics and Ecology, Aarhus University, 8000 C, Denmark

    Jotun Hein

  2. Department of Computer Science, McMaster University, L8S 4K1, Hamilton, Ont., Canada

    Tao Jiang

  3. Department of Electrical and Computer Engineering, McMaster University, L8S 4K1, Hamilton, Ont., Canada

    Lusheng Wang

  4. Department of Computer Science, University of Western Ontario, N6A 5B7, London, Ont., Canada

    Kaizhong Zhang

Authors
  1. Jotun Hein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tao Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lusheng Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Kaizhong Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Zvi Galil Esko Ukkonen

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hein, J., Jiang, T., Wang, L., Zhang, K. (1995). On the complexity of comparing evolutionary trees. In: Galil, Z., Ukkonen, E. (eds) Combinatorial Pattern Matching. CPM 1995. Lecture Notes in Computer Science, vol 937. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60044-2_42

Download citation

  • DOI: https://doi.org/10.1007/3-540-60044-2_42

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60044-2

  • Online ISBN: 978-3-540-49412-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation