ISIPhyNC - Class: binary FU-stable
Definition
A phylogenetic network is
binary FU-stable if it is
binary and it is
FU-stable. [
reference]
Bibliographic references on the Who is who in phylogenetic networks
Relationships with other phylogenetic network classes
Maximum subclasses
- binary distinct-cluster (Suppose by contradiction there exists a network N which is binary distinct-cluster but not FU-stable. Then either it contains two vertices u and v with the same sets of children, but then they also have the same cluster, even after any contraction of an arc from a hybrid vertex to its tree-node child. Or it contains a hybrid vertex u with a hybrid parent v, which both have the same cluster, even after any contraction of an arc from a hybrid vertex to its tree-node child.)
- binary genetically stable (The class of binary genetically stable networks is a subclass of the classes of binary compressed networks and binary tree-sibling networks, which implies, according to Corollary 1 of [HMSW2016], that it is also a subclass of binary FU-stable networks.)
Minimum superclasses
Problems
Positive results proved for this class
Positive results deduced from superclasses
- Phylogenetic Network Isomorphism, positive result on binary: The phylogenetic network isomorphism problem can be solved in O(n^{4}) time on binary networks. Simulations show that the algorithm is practical, with instances of 500 vertices solved in less than one tenth of a second. [reference]
Negative results proved for this class
Negative results deduced from subclasses
Properties
Properties proved for this class
Properties deduced from superclasses
No property could be deduced from superclasses.
Properties deduced from subclasses
No property could be deduced from subclasses.
Examples of networks
In this class
proved directly:
network #11 : No reticulation vertex has a reticulation vertex as its parent, and no two vertices have the same sets c(u) and c(v) of children: c(r)={a,f}, c(a)={b,c}, c(b)={1}, c(c)={d}, c(d)={b,e}, c(e)={2}, c(f)={e}.
network #1 : No reticulation vertex has a reticulation vertex as its parent, and no two vertices have the same set of children
network #4 :
Deduced from class inclusions: network #5 (deduced from the inclusion of "binary unicyclic" in this class), network #9 (deduced from the inclusion of "binary distinct-cluster" in this class), network #7 (deduced from the inclusion of "binary normal" in this class), network #13 (deduced from the inclusion of "binary normal" in this class), network #22 (deduced from the inclusion of "binary normal" in this class), network #24 (deduced from the inclusion of "binary regular" in this class), network #2 (deduced from the inclusion of "binary regular" in this class), network #8 (deduced from the inclusion of "binary regular" in this class), network #4 (deduced from the inclusion of "binary genetically stable" in this class), network #15 (deduced from the inclusion of "binary normal" in this class)
Not in this class
Proved directly:
network #14 : Vertices a and d have the same set of children: {b, c}.
Deduced from class inclusions: network #12 (deduced from the inclusion of this class in "binary compressed"), network #10 (deduced from the inclusion of this class in "binary tree-based"), network #3 (deduced from the inclusion of this class in "binary tree-based")
About this website
This website was programmed and is maintained by Philippe Gambette.
It was started during the internship of Maxime Morgado at LIGM, in June-July 2015,
and also contains contributions made from Narges Tavassoli from November 2016 to January 2017.
Please contact Philippe Gambette if you have any suggestions about this website, especially about problems, properties, results or subclasses to add.
How to cite
P. Gambette, M. Morgado, N. Tavassoli & M. Weller (2018)
ISIPhyNC, an Information System on Inclusions of Phylogenetic Network Classes, manuscript in preparation.
Database content
73 classes of phylogenetic networks including 35 classes of binary phylogenetic networks (defined in a total of 20 bibliographic references), 51 inclusion relationships proved directly between classes (including some found in a total of 9 bibliographic references), 24 networks (68 memberships to a class, 56 non-memberships to a class), 3 problems considered, 3 properties considered, 37 theorems proved directly (including some found in a total of 17 bibliographic references) including 26 positive results (which can be extended to subclasses) and 11 negative results (which can be extended to superclasses).