Algorithms for Building Consensus MUL-trees | SpringerLink
Skip to main content
Springer Nature Link
Log in

Algorithms for Building Consensus MUL-trees

  • Conference paper
Algorithms and Computation (ISAAC 2011)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7074))

Included in the following conference series:

  • 1890 Accesses

Abstract

A MUL-tree is a generalization of a phylogenetic tree that allows the same leaf label to be used many times. Lott et al.  [9,10] recently introduced the problem of inferring a so-called consensus MUL-tree from a set of conflicting MUL-trees and gave an exponential-time algorithm for a special greedy variant. Here, we study strict and majority rule consensus MUL-trees, and present the first ever polynomial-time algorithms for building a consensus MUL-tree. We give a simple, fast algorithm for building a strict consensus MUL-tree. We also show that although it is NP-hard to find a majority rule consensus MUL-tree, the variant which we call the singular majority rule consensus MUL-tree is unique and can be constructed efficiently.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Aho, A.V., Sagiv, Y., Szymanski, T.G., Ullman, J.D.: Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal on Computing 10, 405–421 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  2. Day, W.H.E.: Optimal algorithms for comparing trees with labeled leaves. Journal of Classification 2(1), 7–28 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  3. Felsenstein, J.: Inferring Phylogenies. Sinauer Associates, Inc., Sunderland (2004)

    Google Scholar 

  4. Ganapathy, G., Goodson, B., Jansen, R., Le, H.-S., Ramachandran, V., Warnow, T.: Pattern identification in biogeography. IEEE/ACM Transactions on Computational Biology and Bioinformatics 3(4), 334–346 (2006)

    Article  Google Scholar 

  5. Garey, M., Johnson, D.: Computers and Intractability – A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)

    MATH  Google Scholar 

  6. Guillemot, S., Jansson, J., Sung, W.-K.: Computing a smallest multilabeled phylogenetic tree from rooted triplets. IEEE/ACM Transactions on Computational Biology and Bioinformatics 8(4), 1141–1147 (2011)

    Article  MATH  Google Scholar 

  7. Huber, K.T., Lott, M., Moulton, V., Spillner, A.: The complexity of deriving multi-labeled trees from bipartitions. J. of Comp. Biology 15(6), 639–651 (2008)

    Article  MathSciNet  Google Scholar 

  8. Huber, K.T., Spillner, A., Suchecki, R., Moulton, V.: Metrics on multilabeled trees: Interrelationships and diameter bounds. IEEE/ACM Transactions on Computational Biology and Bioinformatics 8(4), 1029–1040 (2011)

    Article  Google Scholar 

  9. Lott, M., Spillner, A., Huber, K.T., Moulton, V.: PADRE: a package for analyzing and displaying reticulate evolution. Bioinformatics 25(9), 1199–1200 (2009)

    Article  Google Scholar 

  10. Lott, M., Spillner, A., Huber, K.T., Petri, A., Oxelman, B., Moulton, V.: Inferring polyploid phylogenies from multiply-labeled gene trees. BMC Evolutionary Biology 9, 216 (2009)

    Article  Google Scholar 

  11. Margush, T., McMorris, F.R.: Consensus n-Trees. Bulletin of Mathematical Biology 43(2), 239–244 (1981)

    MathSciNet  MATH  Google Scholar 

  12. Nelson, G., Platnick, N.: Systematics and Biogeography: Cladistics and Vicariance. Columbia University Press (1981)

    Google Scholar 

  13. Page, R.D.M.: Parasites, phylogeny and cospeciation. International Journal for Parasitology 23, 499–506 (1993)

    Article  Google Scholar 

  14. Page, R.D.M.: Maps between trees and cladistic analysis of historical associations among genes, organisms, and areas. Systematic Biology 43(1), 58–77 (1994)

    Google Scholar 

  15. Scornavacca, C., Berry, V., Ranwez, V.: Building species trees from larger parts of phylogenomic databases. Information and Computation 209(3), 590–605 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  16. Sokal, R.R., Rohlf, F.J.: Taxonomic congruence in the Leptopodomorpha re-examined. Systematic Zoology 30(3), 309–325 (1981)

    Article  Google Scholar 

  17. Sung, W.-K.: Algorithms in Bioinformatics: A Practical Introduction. Chapman & Hall/CRC (2010)

    Google Scholar 

  18. Wareham, H.T.: An efficient algorithm for computing Mi consensus trees. B.Sc. Honours thesis, Memorial University of Newfoundland, Canada (1985)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. National University of Singapore, 13 Computing Drive, Singapore, 117417

    Yun Cui & Wing-Kin Sung

  2. Ochanomizu University, 2-1-1 Otsuka, Bunkyo-ku, Tokyo, 112-8610, Japan

    Jesper Jansson

  3. Genome Institute of Singapore, 60 Biopolis Street, Genome, Singapore, 138672

    Wing-Kin Sung

Authors
  1. Yun Cui
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jesper Jansson
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wing-Kin Sung
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Chuo University, Kasuga, Bunkyo-ku, 112-8551, Tokyo, Japan

    Takao Asano

  2. Gunma University, 1-5-1 Tenjin-Cho, 376-8515, Kiryu-Shi, Japan

    Shin-ichi Nakano

  3. Japan Advanced Institute of Science and Technology, 1-1 Asahidai, 923-1292, Nomi, Ishikawa, Japan

    Yoshio Okamoto

  4. Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro-ku, 152-8552, Tokyo, Japan

    Osamu Watanabe

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Cui, Y., Jansson, J., Sung, WK. (2011). Algorithms for Building Consensus MUL-trees. In: Asano, T., Nakano, Si., Okamoto, Y., Watanabe, O. (eds) Algorithms and Computation. ISAAC 2011. Lecture Notes in Computer Science, vol 7074. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25591-5_76

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-25591-5_76

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-25590-8

  • Online ISBN: 978-3-642-25591-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics