article

A Metric on the Space of Reduced Phylogenetic Networks

Author:

Luay NakhlehAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 7, Issue 2

Pages 218 - 222

https://doi.org/10.1109/TCBB.2009.2

Published: 01 April 2010 Publication History

Get Access

Abstract

Phylogenetic networks are leaf-labeled, rooted, acyclic, and directed graphs that are used to model reticulate evolutionary histories. Several measures for quantifying the topological dissimilarity between two phylogenetic networks have been devised, each of which was proven to be a metric on certain restricted classes of phylogenetic networks. A biologically motivated class of phylogenetic networks, namely, reduced phylogenetic networks, was recently introduced. None of the existing measures is a metric on the space of reduced phylogenetic networks. In this paper, we provide a metric on the space of reduced phylogenetic networks that is computable in time polynomial in the size of the networks.

References

[1]

D. Robinson and L. Foulds, "Comparison of Phylogenetic Trees," Math. Biosciences, vol. 53, pp. 131-147, 1981.

Crossref

Google Scholar

[2]

L. Nakhleh, T. Warnow, and C. Linder, "Reconstructing Reticulate Evolution in Species-Theory and Practice," Proc. Eighth Ann. Int'l Conf. Computational Molecular Biology, pp. 337-346, 2004.

Digital Library

Google Scholar

[3]

H. Bunke and K. Shearer, "A Graph Distance Metric Based on the Maximal Common Subgraph," Pattern Recognition Letters, vol. 19, pp. 255-259, 1998.

Digital Library

Google Scholar

[4]

H. Bunke, X. Jiang, and A. Kandel, "On the Minimum Common Supergraph of Two Graphs," Computing, vol. 65, pp. 13-25, 2000.

Digital Library

Google Scholar

[5]

L. Nakhleh, J. Sun, T. Warnow, R. Linder, B. Moret, and A. Tholse, "Towards the Development of Computational Tools for Evaluating Phylogenetic Network Reconstruction Methods," Proc. Eighth Pacific Symp. Biocomputing, pp. 315-326, 2003.

Google Scholar

[6]

B. Moret, L. Nakhleh, T. Warnow, C. Linder, A. Tholse, A. Padolina, J. Sun, and R. Timme, "Phylogenetic Networks: Modeling, Reconstructibility, and Accuracy," IEEE/ACM Trans. Computational Biology and Bioinformatics, vol. 1, no. 1, pp. 13-23, Jan.-Mar. 2004.

Digital Library

Google Scholar

[7]

M. Baroni, C. Semple, and M. Steel, "A Framework for Representing Reticulate Evolution," Annals of Combinatorics, vol. 8, pp. 391-408, 2004.

Crossref

Google Scholar

[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.

Crossref

Google Scholar

[9]

G. Cardona, M. Llabrés, F. Rosselló, and G. Valiente, "A Distance Metric for a Class of Tree-Sibling Phylogenetic Networks," Bioinformatics, vol. 24, no. 13, pp. 1481-1488, 2008.

Digital Library

Google Scholar

[10]

G. Cardona, M. Llabrés, F. Rosselló, and G. Valiente, "Metrics for Phylogenetic Networks I: Generalizations of the Robinson-Foulds Metric," IEEE/ACM Trans. Computational Biology and Bioinformatics, vol. 6, no. 1, pp. 46-61, Jan.-Mar. 2009.

Digital Library

Google Scholar

[11]

G. Cardona, F. Rosselló, and G. Valiente, "Comparison of Tree-Child Phylogenetic Networks," IEEE/ACM Trans. Computational Biology and Bioinformatics, vol. 6, no. 4, pp. 552-569, Oct.-Dec. 2009.

Digital Library

Google Scholar

[12]

G. Cardona, M. Llabrés, F. Rosselló, and G. Valiente, "Metrics for Phylogenetic Networks II: Nodal and Triplets Metrics," IEEE/ ACM Trans. Computational Biology and Bioinformatics, vol. 6, no. 3, pp. 454-469, July-Sept. 2009.

Digital Library

Google Scholar

[13]

F. Restle, "A Metric and an Ordering on Sets," Psychometrika, vol. 24, no. 3, pp. 207-220, 1959.

Crossref

Google Scholar

Cited By

View all

Alamin MLiu KWang MYoon B(2023)Phylogenetic Placement of Aligned Genomes and Metagenomes with Non-tree-like Evolutionary HistoriesProceedings of the 14th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics10.1145/3584371.3612981(1-10)Online publication date: 3-Sep-2023
https://dl.acm.org/doi/10.1145/3584371.3612981
Yakici BOgilvie HNakhleh L(2022)Phylogenetic Network Dissimilarity Measures that Take Branch Lengths into AccountComparative Genomics10.1007/978-3-031-06220-9_6(86-102)Online publication date: 20-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-06220-9_6
Du POgilvie HNakhleh L(2019)Unifying Gene Duplication, Loss, and Coalescence on Phylogenetic NetworksBioinformatics Research and Applications10.1007/978-3-030-20242-2_4(40-51)Online publication date: 3-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-20242-2_4
Show More Cited By

Index Terms

A Metric on the Space of Reduced Phylogenetic Networks

Recommendations

Metrics for Phylogenetic Networks II: Nodal and Triplets Metrics

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 ...
Algorithms for phylogenetic footprinting
RECOMB '01: Proceedings of the fifth annual international conference on Computational biology

Phylogenetic footprinting is a technique that identifies regulatory elements by finding unusually well conserved regions in a set of orthologous non-coding DNA sequences from multiple species. In an earlier paper, we presented an exact algorithm that ...
Comparison of Tree-Child Phylogenetic Networks

Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of nontreelike evolutionary events, like recombination, hybridization, or lateral gene transfer. While much progress has been made to find practical ...

Reviews

Reviewer: Gunnar W. Klau

Reconstructing evolutionary histories is of great importance in biology. Recent research concentrates on networks instead of trees, in order to deal with evolutionary events such as recombination, hybridization, and lateral gene transfer. Moret et al. [1] introduced the concept of reduced phylogenetic networks to deal with incomplete information when constructing the phylogenies. Here, Nakhleh provides the first metric on reduced phylogenetic networks and resolves an issue with a measure introduced in Moret et al. [1] that does not satisfy the properties of a metric. Thus, this work closes a theoretical gap in the area of phylogenetic networks and is worth reading by all researchers in this field. On one hand, a real-world example to demonstrate the usefulness of the metric would have been illustrative. On the other hand, without it, the paper represents a good, concise theoretical contribution. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Information & Contributors

Information

Published In

IEEE/ACM Transactions on Computational Biology and Bioinformatics Volume 7, Issue 2

April 2010

189 pages

ISSN:1545-5963

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 April 2010

Published in TCBB Volume 7, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
165
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)2

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Alamin MLiu KWang MYoon B(2023)Phylogenetic Placement of Aligned Genomes and Metagenomes with Non-tree-like Evolutionary HistoriesProceedings of the 14th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics10.1145/3584371.3612981(1-10)Online publication date: 3-Sep-2023
https://dl.acm.org/doi/10.1145/3584371.3612981
Yakici BOgilvie HNakhleh L(2022)Phylogenetic Network Dissimilarity Measures that Take Branch Lengths into AccountComparative Genomics10.1007/978-3-031-06220-9_6(86-102)Online publication date: 20-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-06220-9_6
Du POgilvie HNakhleh L(2019)Unifying Gene Duplication, Loss, and Coalescence on Phylogenetic NetworksBioinformatics Research and Applications10.1007/978-3-030-20242-2_4(40-51)Online publication date: 3-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-20242-2_4
Mirzaei SWu Y(2016)Fast construction of near parsimonious hybridization networks for multiple phylogenetic treesIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2015.246233613:3(565-570)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1109/TCBB.2015.2462336
Cardona GLlabres MRossello FValiente G(2011)Comparison of Galled TreesIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2010.608:2(410-427)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1109/TCBB.2010.60
Huber KSpillner ASuchecki RMoulton V(2011)Metrics on Multilabeled TreesIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2010.1228:4(1029-1040)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1109/TCBB.2010.122
Cardona GLlabres MRossello FValiente G(2009)On Nakhleh's Metric for Reduced Phylogenetic NetworksIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2009.336:4(629-638)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1109/TCBB.2009.33

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Metrics for Phylogenetic Networks II: Nodal and Triplets Metrics

Algorithms for phylogenetic footprinting

Comparison of Tree-Child Phylogenetic Networks

Reviews

Access critical reviews of Computing literature here