Combinatorial scoring of phylogenetic networks

DOI10.1007/978-3-319-42634-1_45MaRDI QIDQ2817897zbMATH OpenOpenAlexWikidataFDO

Authors N. V. Alexeev, Max A. Alekseyev

Publication date 2 September 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.02841

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15)

Abstract: Construction of phylogenetic trees and networks for extant species from their characters represents one of the key problems in phylogenomics. While solution to this problem is not always uniquely defined and there exist multiple methods for tree/network construction, it becomes important to measure how well the constructed networks capture the given character relationship across the species. In the current study, we propose a novel method for measuring the specificity of a given phylogenetic network in terms of the total number of distributions of character states at the leaves that the network may impose. While for binary phylogenetic trees, this number has an exact formula and depends only on the number of leaves and character states but not on the tree topology, the situation is much more complicated for non-binary trees or networks. Nevertheless, we develop an algorithm for combinatorial enumeration of such distributions, which is applicable for arbitrary trees and networks under some reasonable assumptions.

Recommendations

• On computing the maximum parsimony score of a phylogenetic network
• Counting general phylogenetic networks
• Counting phylogenetic networks of level 1 and 2
• Counting Phylogenetic Networks with Few Reticulation Vertices: Tree-Child and Normal Networks
• New characterisations of tree-based networks and proximity measures

Cites work

• A note on convex characters, Fibonacci numbers and exponential-time algorithms
• Combinatorial algorithms on a class of graphs
• Phylogenetic graph models beyond trees
• The complexity of reconstructing trees from qualitative characters and subtrees
• Tree reconstruction from multi-state characters

Cited in

(4)

• scientific article; zbMATH DE number 5713387 (Why is no real title available?)
• Counting Phylogenetic Networks with Few Reticulation Vertices: Tree-Child and Normal Networks
• Towards the development of computational tools for evaluating phylogenetic network reconstruction methods
• Counting general phylogenetic networks

This page was built for publication: Combinatorial scoring of phylogenetic networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817897)