Metrics for Phylogenetic Networks II

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Metrics for Phylogenetic Networks II: Nodal and Triplets Metrics

Full text

Pdf (799 KB)

Source

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) archive
Volume 6 , Issue 3 (July 2009) table of contents

Pages 454-469

Year of Publication: 2009

ISSN:1545-5963

Authors

Gabriel Cardona	University of the Balearic Islands, Palma de Mallorca
Merce Llabres	University of the Balearic Islands, Palma de Mallorca
Francesc Rossello	University of the Balearic Islands, Palma de Mallorca
Gabriel Valiente	Technical University of Catalonia, Barcelona

Publisher

IEEE Computer Society Press Los Alamitos, CA, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 46, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1109/TCBB.2008.127

ABSTRACT

The assessment of phylogenetic network reconstruction methods requires the ability to compare phylogenetic networks. This is the second in a series of papers devoted to the analysis and comparison of metrics for tree-child time consistent phylogenetic networks on the same set of taxa. In this paper, we generalize to phylogenetic networks two metrics that have already been introduced in the literature for phylogenetic trees: the nodal distance and the triplets distance. We prove that they are metrics on any class of tree-child time consistent phylogenetic networks on the same set of taxa, as well as some basic properties for them. To prove these results, we introduce a reduction/expansion procedure that can be used not only to establish properties of tree-child time consistent phylogenetic networks by induction, but also to generate all tree-child time consistent phylogenetic networks with a given number of leaves.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Baroni, C. Semple, and M. Steel, "Hybrids in Real Time," Systems Biology, vol. 55, no. 1, pp. 46-56, 2006.
	2	John Bluis , Dong-Guk Shin, Nodal Distance Algorithm: Calculating a Phylogenetic Tree Comparison Metric, Proceedings of the 3rd IEEE Symposium on BioInformatics and BioEngineering, p.87, March 10-12, 2003
	3	Gabriel Cardona , Mercè Llabrés , Francesc Rosselló , Gabriel Valiente, A distance metric for a class of tree-sibling phylogenetic networks, Bioinformatics, v.24 n.13, p.1481-1488, July 2008 [doi>10.1093/bioinformatics/btn231]
	4	G. Cardona, M. Llabrés, F. Rosselló, and G. Valiente, "Metrics for Phylogenetic Networks III: Comparison of Metrics," in preparation, 2009.
	5	G. Cardona, M. Llabrés, F. Rosselló, and G. Valiente, "Nodal Distances for Rooted Phylogenetic Trees," submitted for publication, 2008. Preprint available at arXiv:0806.2035v1 [q-bio.PE].
	6	G. Cardona, M. Llabrés, F. Rosselló, and G. Valiente, "Path Lengths in Tree-Child Time Consistent Hybridization Networks," to be published, 2008. Preprint available at arXiv:0807.0087v1 [q-bio.PE].
	7	Gabriel Cardona , Mercè Llabrés , Francesc Rosselló , Gabriel Valiente, Metrics for Phylogenetic Networks I: Generalizations of the Robinson-Foulds Metric, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.6 n.1, p.46-61, January 2009 [doi>10.1109/TCBB.2008.70]
	8	G. Cardona, F. Rosselló, and G. Valiente, "Tripartitions Do Not Always Discriminate Phylogenetic Networks," Math. Biosciences, vol. 211, no. 2, pp. 356-370, 2008.
	9	G. Cardona, F. Rosselló, and G. Valiente, "Comparison of Tree-Child Phylogenetic Networks," IEEE Trans. Computational Biology and Bioinformatics, preprint, Dec. 2007, doi:10.1109/ TCBB.2007.70270.
	10	D.E. Critchlow, D.K. Pearl, and C. Qian, "The Triples Distance for Rooted Bifurcating Phylogenetic Trees," Systems Biology, vol. 45, no. 3, pp. 323-334, 1996.
	11	A.J. Dobson, "Comparing the Shapes of Trees," Combinatorial Mathematics, III, pp. 95-100, Springer, 1975.
	12	J.S. Farris, "A Successive Approximations Approach to Character Weighting," Systems Zoology, vol. 18, no. 4, pp. 374-385, 1969.
	13	J.S. Farris, "On Comparing the Shapes of Taxonomic Trees," Systems Zoology, vol. 22, pp. 50-54, 1973.
	14	J. Felsenstein, Inferring Phylogenies. Sinauer Assoc., 2004.
	15	Y.-J. He, T.N.D. Huynh, J. Jansson, and W.-K. Sung, "Inferring Phylogenetic Relationships Avoiding Forbidden Rooted Triplets," J. Bioinformatics Computational Biology, vol. 4, no. 1, pp. 59-74, 2006.
	16	Jesper Jansson , Joseph H. K. Ng , Kunihiko Sadakane , Wing-Kin Sung, Rooted Maximum Agreement Supertrees, Algorithmica, v.43 n.4, p.293-307, December 2005 [doi>10.1007/s00453-004-1147-5]
	17	Jesper Jansson , Nguyen Bao Nguyen , Wing-Kin Sung, Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network, SIAM Journal on Computing, v.35 n.5, p.1098-1121, 2006 [doi>10.1137/S0097539704446529]
	18	Jesper Jansson , Wing-Kin Sung, Inferring a level-1 phylogenetic network from a dense set of rooted triplets, Theoretical Computer Science, v.363 n.1, p.60-68, 25 October 2006 [doi>10.1016/j.tcs.2006.06.022]
	19	Bernard M. E. Moret , Luay Nakhleh , Tandy Warnow , C. Randal Linder , Anna Tholse , Anneke Padolina , Jerry Sun , Ruth Timme, Phylogenetic Networks: Modeling, Reconstructibility, and Accuracy, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.1, p.13-23, January 2004 [doi>10.1109/TCBB.2004.10]
	20	V. Moulton, M. Zuker, M. Steel, R. Pointon, and D. Penny, "Metrics on RNA Secondary Structures," J. Computational Biology, vol. 7, nos. 1/2, pp. 277-292, 2000.
	21	J.B. Phipps, "Dendrogram Topology," Systems Zoology, vol. 20, no. 3, pp. 306-308, 1971.
	22	L. van Iersel, J. Keijsper, S. Kelk, L. Stougie, F. Hagen, and T. Boekhout, "Constructing Level-2 Phylogenetic Networks from Triplets," Proc. 12th Ann. Int'l Conf. Research in Computational Molecular Biology, pp. 450-462, 2008.
	23	Leo Iersel , Steven Kelk, Constructing the Simplest Possible Phylogenetic Network from Triplets, Proceedings of the 19th International Symposium on Algorithms and Computation, December 15-17, 2008, Gold Coast, Australia [doi>10.1007/978-3-540-92182-0_43]
	24	W.T. Williams and H.T. Clifford, "On the Comparison of Two Classifications of the Same Set of Elements," Taxon, vol. 20, no. 4, pp. 519-522, 1971.