ISIPhyNC - Class: binary normal
Definition
A phylogenetic network is
binary normal if it is
binary and it is
normal. [
reference]
Bibliographic references on the Who is who in phylogenetic networks
Relationships with other phylogenetic network classes
Maximum subclasses
- binary phylogenetic tree (There is no redundant arc in a phylogenetic binary tree and every vertex has no reticulation vertices as children.)
Minimum superclasses
Problems
Positive results proved for this class
Positive results deduced from superclasses
- Cluster Containment, positive result on binary reticulation-visible: Solvable in O(n) time [reference]
- 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]
- Tree Containment, positive result on binary tree-child: Solvable in polynomial time [reference] (Theorem 1)
- Tree Containment, positive result on binary nearly stable: Solvable in O(n^{2}) time [reference]
- Tree Containment, positive result on binary nearly stable: Solvable in O(n log n) time [reference]
- Tree Containment, positive result on binary nearly stable: Solvable in O(n) time [reference]
- Tree Containment, positive result on binary reticulation-visible: Solvable in O(n^{3}) time [reference]
- Tree Containment, positive result on binary reticulation-visible: Solvable in O(n) time [reference]
- Tree Containment, positive result on binary reticulation-visible: Solvable in O(n) time [reference]
Negative results proved for this class
Negative results deduced from subclasses
No negative result could be deduced from subclasses.
Properties
Properties proved for this class
- Upper bound on the number of vertices: An upper bound on the number of vertices is n^{2}-n+2 [reference] (Theorem 5.1(2), with a multiplication by 2 to take into account the number of vertices possibly added during the "decontraction" to obtain a binary phylogenetic network)
Properties deduced from superclasses
- Upper bound on the number of vertices, property of binary regular: An upper bound on the number of vertices is 2^{n}. [reference] (Theorem 5.1(3), with a multiplication by 2 to take into account the number of vertices possibly added during the "decontraction" to obtain a binary phylogenetic network)
- Upper bound on the number of vertices, property of binary tree-child: An upper bound on the number of vertices is 5n-2. [reference] (Proof of Theorem 2)
- Upper bound on the number of vertices, property of binary nearly stable: An upper bound on the number of vertices is 26n-24. [reference] (Theorem 2 (adding the number of reticulation vertices, tree vertices, the root and the leaves))
- Upper bound on the number of vertices, property of binary nearly stable: An upper bound on the number of vertices is 8n-7 and an upper bound on the number of reticulation vertices is 3n-3. Both bounds are tight. [reference] (Theorem 5.5 and Table 1)
- Upper bound on the number of vertices, property of binary nearly tree-child: An upper bound on the number of vertices is 4n. [reference] (Lemma 4)
- Upper bound on the number of vertices, property of binary reticulation-visible: An upper bound on the number of vertices is 8n-7 and an upper bound on the number of reticulation vertices is 3n-3. Both bounds are tight. [reference] (Theorem 1.2)
- Upper bound on the number of vertices, property of binary stable-child: An upper bound on the number of vertices is 16n-15 and an upper bound on the number of reticulation vertices is 7n-7. Both bounds are tight. [reference] (Theorem 6.4 and Table 1)
Properties deduced from subclasses
No property could be deduced from subclasses.
Examples of networks
In this class
proved directly:
network #7 : The network contains no redundant arc, and all parents of reticulations have a tree child: a and e, parents of b, have respectively c and f as tree child; e and f, parents of d, have respectively 2 and 4 as tree child.
network #13 : The network contains no redundant arc, and all parents of reticulations have a tree child: a and f, parents of d, have respectively b and 4 as tree child; b and e, parents of c, have respectively 1 and 3 as tree child.
network #22 : The network contains no redundant arc, and all parents of reticulations have a tree child: a and f, parents of b, have respectively c and 2 as tree child; c and e, parents of d, have respectively 3 and f as tree child.
network #15 : The network contains no redundant arc, and all parents of reticulations have a tree child: b and g, parents of c, have respectively 1 and h as tree child; d and j, parents of e, have respectively 2 and 4 as tree child; h and l, parents of i, have respectively 5 and 6 as tree child; f and m, parents of k, have respectively g and 7 as tree child; .
Deduced from class inclusions: no network found in this class using class inclusions
Not in this class
Proved directly:
no network found outside this class with a direct proof
Deduced from class inclusions: network #5 (deduced from the inclusion of this class in "binary distinct-cluster"), network #17 (deduced from the inclusion of this class in "binary nearly stable"), network #14 (deduced from the inclusion of this class in "binary FU-stable"), network #12 (deduced from the inclusion of this class in "binary compressed"), network #6 (deduced from the inclusion of this class in "binary distinct-cluster"), network #11 (deduced from the inclusion of this class in "binary distinct-cluster"), network #9 (deduced from the inclusion of this class in "binary regular"), network #21 (deduced from the inclusion of this class in "binary nearly stable"), network #1 (deduced from the inclusion of this class in "binary distinct-cluster"), network #10 (deduced from the inclusion of this class in "binary tree-based"), network #24 (deduced from the inclusion of this class in "binary reticulation-visible"), network #19 (deduced from the inclusion of this class in "binary nearly stable"), network #8 (deduced from the inclusion of this class in "binary nearly stable"), network #2 (deduced from the inclusion of this class in "binary tree-sibling"), network #3 (deduced from the inclusion of this class in "binary tree-based"), network #4 (deduced from the inclusion of this class in "binary nearly tree-child")
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).