Have a personal or library account? Click to login

On a matching distance between rooted phylogenetic trees

International Journal of Applied Mathematics and Computer Science
Volume 23 (2013): Issue 3 (September 2013)
By:
Open Access
|Sep 2013

References

  1. Alberich, R., Cardona, G., Rosselló, F. and Valiente, G. (2009). An algebraic metric for phylogenetic trees, Applied MathematicsLetters 22(9): 1320-1324.10.1016/j.aml.2009.03.003
    Search in Google Scholar
  2. Aldous, D.J. (1991). The continuum random tree II: An overview, in M.T. Barlow and N. H. Bingham (Eds.), StochasticAnalysis, Cambridge University Press, Cambridge, pp. 23-70.10.1017/CBO9780511662980.003
    Search in Google Scholar
  3. Bansal, M., Burleigh, J.G., Eulenstein, O. and Fernández-Baca, D. (2010). Robinson-Foulds supertrees, Algorithms forMolecular Biology 5(1): 18.10.1186/1748-7188-5-18284695220181274
    Search in Google Scholar
  4. Bansal, M.S., Dong, J. and Fernández-Baca, D. (2011). Comparing and aggregating partially resolved trees, TheoreticalComputer Science 412(48): 6634-6652.10.1016/j.tcs.2011.08.027
    Search in Google Scholar
  5. Biedrzycki, R. and Arabas, J. (2012). KIS: An automated attribute induction method for classification of DNA sequences, International Journal of Applied Mathematicsand Computer Science 22(3): 711-721, DOI: 10.2478/v10006-012-0053-2.10.2478/v10006-012-0053-2
    Search in Google Scholar
  6. Bininda-Emonds, O.R.P., Cardillo, M., Jones, K.E., MacPhee, R. D.E., Beck, R.M.D., Grenyer, R., Price, S.A., Vos, R.A., Gittleman, J.L. and Purvis, A. (2007). The delayed rise of present-day mammals, Nature 446(7135): 507-512.10.1038/nature0563417392779
    Search in Google Scholar
  7. Blum, M.G.B., François, O. and Janson, S. (2006). The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance, The Annals of Applied Probability16(4): 2195-2214.10.1214/105051606000000547
    Search in Google Scholar
  8. Boc, A., Philippe, H. and Makarenkov, V. (2010). Inferring and validating horizontal gene transfer events using bipartition dissimilarity, Systematic Biology 59(2): 195-211.10.1093/sysbio/syp10320525630
    Search in Google Scholar
  9. Bogdanowicz, D. and Giaro, K. (2012). Matching split distance for unrooted binary phylogenetic trees, IEEE/ACM Transactionson Computational Biology and Bioinformatics9(1): 150-160.10.1109/TCBB.2011.4821383415
    Search in Google Scholar
  10. Bogdanowicz, D., Giaro, K. and Wróbel, B. (2012). TreeCmp: Comparison of trees in polynomial time, Evolutionary Bioinformatics8: 475-487.10.4137/EBO.S9657
    Search in Google Scholar
  11. Bolikowski, L. and Gambin, A. (2007). New metrics for phylogenies, Fundamenta Informaticae 78(2): 199-216.
    Search in Google Scholar
  12. Boorman, S.A. and Olivier, D.C. (1973). Metrics on spaces of finite trees, Journal of Mathematical Psychology10(1): 26-59.10.1016/0022-2496(73)90003-5
    Search in Google Scholar
  13. Bordewich, M. and Semple, C. (2005). On the computational complexity of the rooted subtree prune and regraft distance, Annals of Combinatorics 8(4): 409-423.10.1007/s00026-004-0229-z
    Search in Google Scholar
  14. Brinkmeyer, M., Griebel, T. and Böcker, S. (2011). Polynomial supertree methods revisited, Advances in Bioinformatics2011: 524182.10.1155/2011/524182324959222229028
    Search in Google Scholar
  15. Bryant, D. (1997). Building Trees, Hunting for Trees, and ComparingTrees-Theory and Methods in Phylogenetic Analysis, Ph.D. thesis, University of Canterbury, Christchurch.
    Search in Google Scholar
  16. Cardona, G., Llabrés, M., Rosselló, F. and Valiente, G. (2009a). Metrics for phylogenetic networks I: Generalizations of the Robinson-Foulds metric, IEEE/ACM Transactions onComputational Biology and Bioinformatics 6(1): 46-61.10.1109/TCBB.2008.7019179698
    Search in Google Scholar
  17. Cardona, G., Llabrés, M., Rosselló, F. and Valiente, G. (2009b). Metrics for phylogenetic networks II: Nodal and triplets metrics, IEEE/ACM Transactions on Computational Biologyand Bioinformatics 6(3): 454-469.10.1109/TCBB.2008.12719644173
    Search in Google Scholar
  18. Cardona, G., Rossello, F. and Valiente, G. (2009). Comparison of tree-child phylogenetic networks, IEEE/ACM Transactionson Computational Biology and Bioinformatics6(4): 552-569.10.1109/TCBB.2007.7027019875855
    Search in Google Scholar
  19. Cardona, G., Llabrés, M., Rosselló, F. and Valiente, G. (2010). Nodal distances for rooted phylogenetic trees, Journal ofMathematical Biology 61(2): 253-276.10.1007/s00285-009-0295-219760227
    Search in Google Scholar
  20. Critchlow, D.E., Pearl, D.K. and Qian, C. (1996). The triples distance for rooted bifurcating phylogenetic trees, SystematicBiology 45(3): 323-334.10.1093/sysbio/45.3.323
    Search in Google Scholar
  21. Darlu, P. and Guénoche, A. (2011). TreeOfTrees method to evaluate the congruence between gene trees, Journal ofClassification 28(3): 390-403.10.1007/s00357-011-9093-9
    Search in Google Scholar
  22. Davies, T.J., Barraclough, T.G., Chase, M.W., Soltis, P.S., Soltis, D.E. and Savolainen, V. (2004). Darwin’s abominable mystery: Insights from a supertree of the angiosperms, Proceedings of the National Academy of Sciences of theUnited States of America 101(7): 1904-1909.10.1073/pnas.030812710035702514766971
    Search in Google Scholar
  23. Felsenstein, J. (2003). Inferring Phylogenies, Sinauer Associates, Sunderland, MA.
    Search in Google Scholar
  24. Fra˛ckiewicz, M. and Palus, H. (2011). KHM clustering technique as a segmentation method for endoscopic colour images, International Journal of Applied Mathematicsand Computer Science 21(1): 203-209, DOI: 10.2478/v10006-011-0015-0.10.2478/v10006-011-0015-0
    Search in Google Scholar
  25. Gabow, H.N. and Tarjan, R.E. (1989). Faster scaling algorithms for network problems, SIAM Journal on Computing18(5): 1013-1036.10.1137/0218069
    Search in Google Scholar
  26. Górecki, P. and Eulenstein, O. (2012). A Robinson-Foulds measure to compare unrooted trees with rooted trees, in L. Bleris, I.Mandoiu, R. Schwartz and J.Wang (Eds.), BioinformaticsResearch and Applications, Lecture Notes in Computer Science, Vol. 7292, Springer, Berlin/Heidelberg, pp. 115-126.10.1007/978-3-642-30191-9_12
    Search in Google Scholar
  27. Gusfield, D. (1991). Efficient algorithms for inferring evolutionary trees, Networks 21(1): 19-28.10.1002/net.3230210104
    Search in Google Scholar
  28. Hayes, M., Walenstein, A. and Lakhotia, A. (2009). Evaluation of malware phylogeny modelling systems using automated variant generation, Journal in Computer Virology5(4): 335-343.10.1007/s11416-008-0100-6
    Search in Google Scholar
  29. Hillis, D.M., Heath, T.A. and John, K.S. (2005). Analysis and visualization of tree space, Systematic Biology54(3): 471-482.10.1080/10635150590946961
    Search in Google Scholar
  30. Kennedy, M., Page, R. D.M. and Prum, R. (2002). Seabird supertrees: Combining partial estimates of procellariiform phylogeny, The Auk 119(1): 88-108.10.1093/auk/119.1.88
    Search in Google Scholar
  31. Lin, Y., Rajan, V. and Moret, B.M.E. (2012). A metric for phylogenetic trees based on matching, IEEE/ACM Transactionson Computational Biology and Bioinformatics9(4): 1014-1022.10.1109/TCBB.2011.157
    Search in Google Scholar
  32. Ma, B., Li, M. and Zhang, L. (1998). On reconstructing species trees from gene trees in term of duplications and losses, Proceedings of the 2nd Annual International Conferenceon Computational Molecular Biology, RECOMB’98, NewYork, NY, USA, pp. 182-191.
    Search in Google Scholar
  33. McKenzie, A. and Steel, M. (2000). Distributions of cherries for two models of trees, Mathematical Biosciences164(1): 81-92.10.1016/S0025-5564(99)00060-7
    Search in Google Scholar
  34. Munzner, T., Guimbretière, F., Tasiran, S., Zhang, L. and Zhou, Y. (2003). TreeJuxtaposer: Scalable tree comparison using focus+context with guaranteed visibility, ACM Transactionson Graphics 22(3): 453-462.10.1145/882262.882291
    Search in Google Scholar
  35. Nguyen, N., Mirarab, S. and Warnow, T. (2012). MRL and SuperFine+MRL: New supertree methods, Algorithms forMolecular Biology 7(1): 3.10.1186/1748-7188-7-3
    Search in Google Scholar
  36. Nye, T.M., Liò, P. and Gilks,W.R. (2006). A novel algorithm and web-based tool for comparing two alternative phylogenetic trees, Bioinformatics 22(1): 117-119.10.1093/bioinformatics/bti720
    Search in Google Scholar
  37. Orlin, J.B. and Ahuja, R.K. (1992). New scaling algorithms for the assignment and minimum mean cycle problems, MathematicalProgramming 54(1-3): 41-56.10.1007/BF01586040
    Search in Google Scholar
  38. Penny, D., Watson, E.E. and Steel, M.A. (1993). Trees from languages and genes are very similar, Systematic Biology42(3): 382-384.10.1093/sysbio/42.3.382
    Search in Google Scholar
  39. Pompei, S., Loreto, V. and Tria, F. (2011). On the accuracy of language trees, PLoS ONE 6(6): e20109.10.1371/journal.pone.0020109
    Search in Google Scholar
  40. Restrepo, G., Héber, M. and Llanos, E.J. (2007). Three dissimilarity measures to contrast dendrograms, Journal ofChemical Information and Modeling 47(3): 761-770.10.1021/ci6005189
    Search in Google Scholar
  41. Robinson, D.F. and Foulds, L.R. (1981). Comparison of phylogenetic trees, Mathematical Biosciences53(1-2): 131-147.10.1016/0025-5564(81)90043-2
    Search in Google Scholar
  42. Sackin, M.J. (1972). “Good” and “bad” phenograms, SystematicZoology 21(2): 225-226.
    Search in Google Scholar
  43. Semple, C. and Steel, M. (2003). Phylogenetics, Oxford University Press, Oxford.
    Search in Google Scholar
  44. Shao, K.-T. and Sokal, R.R. (1990). Tree balance, SystematicZoology 39(3): 266-276.10.2307/2992186
    Search in Google Scholar
  45. Steel, M. A. and Penny, D. (1993). Distributions of tree comparison metrics-some new results, Systematic Biology42(2): 126-141.10.1093/sysbio/42.2.126
    Search in Google Scholar
  46. Stockham, C., Wang, L.-S. and Warnow, T. (2002). Statistically based postprocessing of phylogenetic analysis by clustering, Bioinformatics 18(suppl 1): S285-S293.10.1093/bioinformatics/18.suppl_1.S285
    Search in Google Scholar
  47. Suri, R. and Warnow, T. (2010). Spruce, Website, http://www.cs.utexas.edu/~phylo/software/spruce/.
    Search in Google Scholar
  48. Swenson, M.S., Suri, R., Linder, C.R. and Warnow, T. (2011). An experimental study of Quartets MaxCut and other supertree methods, Algorithms for Molecular Biology6(1): 7.10.1186/1748-7188-6-7310164421504600
    Search in Google Scholar
  49. Swofford, D. (2002). PAUP*. Phylogenetic Analysis UsingParsimony (*and other methods). Version 4, Sinauer Associates, Sunderland, MA.
    Search in Google Scholar
  50. Wang, J.T., Shan, H., Shasha, D. and Piel, W.H. (2005). Fast structural search in phylogenetic databases, EvolutionaryBioinformatics Online 1: 37-46. Williams, W.T. and Clifford, H.T. (1971). On the comparison of two classifications of the same set of elements, Taxon20(4): 519-522.
    Search in Google Scholar
DOI: https://doi.org/10.2478/amcs-2013-0050 | Journal eISSN: 2083-8492 | Journal ISSN: 1641-876X
Journal RSS Feed
Language: English
Page range: 669 - 684
Published on: Sep 30, 2013
Published by: University of Zielona Góra
In partnership with: Paradigm Publishing Services
Publication frequency: 4 times per year
Keywords:
phylogenetic tree,
phylogenetic tree metric,
phylogenetic tree comparison,
matching cluster distance,
matching split distance
Related subjects:
Mathematics,
Applied mathematics

© 2013 Damian Bogdanowicz, Krzysztof Giaro, published by University of Zielona Góra
This work is licensed under the Creative Commons License.

Previous articleVolume 23 (2013): Issue 3 (September 2013)Next article