ISIPhyNC - Class: binary phylogenetic tree

Definition

Relationships with other phylogenetic network classes

Maximum subclasses

No class found

Minimum superclasses

• binary galled tree (A binary phylogenetic tree is a binary galled tree with no gall.)
• binary normal (There is no redundant arc in a phylogenetic binary tree and every vertex has no reticulation vertices as children.)
• binary time-consistent

Problems

Positive results proved for this class

No positive result found

Positive results deduced from superclasses

• Cluster Containment, positive result on binary galled network: Solvable in polynomial time. [reference] (Lemma 1. The proof is a bit more detailed in Proposition 12 of this reference.)
• Cluster Containment, positive result on binary level-2: Solvable in O(n) time [reference] (Observation 1)
• Cluster Containment, positive result on binary reticulation-visible: Solvable in O(n) time [reference]
• Cluster Containment, positive result on binary level-3: Solvable in O(n) time [reference] (Observation 1)
• Cluster Containment, positive result on binary level-k: Solvable in O(2^k.n) time [reference] (Observation 1)
• 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 normal: Solvable in polynomial time [reference] (Theorem 2)
• Tree Containment, positive result on binary tree-child: Solvable in polynomial time [reference] (Theorem 1)
• Tree Containment, positive result on binary level-2: Solvable in O(n) time [reference] (Observation 1)
• 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]
• Tree Containment, positive result on binary level-3: Solvable in O(n) time [reference] (Observation 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 level-k: Solvable in O(2^k.n) time [reference] (Observation 1)

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

No property found

Properties deduced from superclasses

• Upper bound on the number of vertices, property of binary normal: 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)
• 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 galled network: An upper bound on the number of vertices is 6n-5 and an upper bound on the number of reticulation vertices is 2n-2. Both bounds are tight. [reference] (Theorem 4.1, Figure 3 and Table 1)
• 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 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 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 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:
no network found in this class with a direct proof

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 #20 (deduced from the inclusion of this class in "binary 3-nested"), network #5 (deduced from the inclusion of this class in "binary distinct-cluster"), 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 #17 (deduced from the inclusion of this class in "binary nearly stable"), network #6 (deduced from the inclusion of this class in "binary distinct-cluster"), network #11 (deduced from the inclusion of this class in "binary level-2"), network #7 (deduced from the inclusion of this class in "binary galled tree"), network #13 (deduced from the inclusion of this class in "binary galled network"), network #9 (deduced from the inclusion of this class in "binary regular"), network #22 (deduced from the inclusion of this class in "binary time-consistent"), network #1 (deduced from the inclusion of this class in "binary level-2"), network #10 (deduced from the inclusion of this class in "binary tree-based"), network #21 (deduced from the inclusion of this class in "binary nearly stable"), network #24 (deduced from the inclusion of this class in "binary reticulation-visible"), network #19 (deduced from the inclusion of this class in "binary 2-nested"), network #8 (deduced from the inclusion of this class in "binary galled network"), network #3 (deduced from the inclusion of this class in "binary level-2"), network #2 (deduced from the inclusion of this class in "binary level-2"), network #4 (deduced from the inclusion of this class in "binary galled network"), network #16 (deduced from the inclusion of this class in "binary level-3"), network #18 (deduced from the inclusion of this class in "binary level-3"), network #23 (deduced from the inclusion of this class in "binary level-3"), network #15 (deduced from the inclusion of this class in "binary level-3")