ISIPhyNC - Class: binary normal

Definition

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

• binary regular
• binary tree-child

Problems

Positive results proved for this class

• Tree Containment: Solvable in polynomial time [reference] (Theorem 2)

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⁴) 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²) 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³) 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

No negative result found

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²-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ⁿ. [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")