On cherry-picking and network containment
From MaRDI portal
Abstract: Phylogenetic networks are used to represent evolutionary scenarios in biology and linguistics. To find the most probable scenario, it may be necessary to compare candidate networks, to distinguish different networks, and to see when one network is contained in another. In this paper, we introduce cherry-picking networks, a class of networks that can be reduced by a sequence of two graph operations. We show that some networks are uniquely determined by the sequences that reduce them---we call these the reconstructible cherry-picking networks, and further show that given two cherry-picking networks within the same reconstructible class, one is contained in the other if a sequence for the latter network reduces the former network. By restricting our scope to tree-child networks, we show that the converse of the above statement holds, thereby showing that {sc Network Containment}, the problem of checking whether a network is contained in another, can be solved in linear time for tree-child networks. We implement this algorithm in Python and show that the linear-time theoretical bound on the input size is achievable in practice. Lastly, we provide a linear time algorithm for deciding whether two tree-child networks are isomorphic.
Recommendations
Cites work
- A class of phylogenetic networks reconstructable from ancestral profiles
- Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies
- Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies
- Combining Networks Using Cherry Picking Sequences
- Deciding the existence of a cherry-picking sequence is hard on two trees
- Determining phylogenetic networks from inter-taxa distances
- Linear time algorithm for tree-child network containment
- Locating a tree in a phylogenetic network
- Reconstructing tree-child networks from reticulate-edge-deleted subnetworks
- Seeing the trees and their branches in the network is hard
- Solving the tree containment problem for genetically stable networks in quadratic time
- Solving the tree containment problem in linear time for nearly stable phylogenetic networks
Cited in
(23)- On the existence of a cherry-picking sequence
- A unifying characterization of tree-based networks and orchard networks using cherry covers
- Novel phylogenetic network distances based on cherry picking
- Classes of explicit phylogenetic networks and their biological and mathematical significance
- Orchard networks are trees with additional horizontal arcs
- Trinets encode orchard phylogenetic networks
- Defining phylogenetic networks using ancestral profiles
- Rooted NNI moves and distance-1 tail moves on tree-based phylogenetic networks
- Linear time algorithm for tree-child network containment
- Autopolyploidy, allopolyploidy, and phylogenetic networks with horizontal arcs
- Labellable phylogenetic networks
- Finding agreement cherry-reduced subnetworks in level-1 networks
- Orienting undirected phylogenetic networks
- Generation of orchard and tree-child networks
- Phylogenetic network classes through the lens of expanding covers
- Reconstructing phylogenetic networks via Cherry picking and machine learning
- Embedding phylogenetic trees in networks of low treewidth
- Counting Cherry reduction sequences in phylogenetic tree-child networks is counting linear extensions
- Path partitions of phylogenetic networks
- Cherry picking in forests: a new characterization for the unrooted hybrid number of two phylogenetic trees
- Metrics for classes of semi-binary phylogenetic networks using -representations
- Embedding phylogenetic trees in networks of low treewidth
- When is a set of phylogenetic trees displayed by a normal network?
This page was built for publication: On cherry-picking and network containment
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2219064)
