ISIPhyNC - Class: binary time-consistent

Definition

A phylogenetic network is binary time-consistent if it is binary and it is time-consistent. Also called binary temporal networks. [reference]

Bibliographic references on the Who is who in phylogenetic networks

Problems

Positive results proved for this class

No positive result found

Positive results deduced from superclasses

• Phylogenetic Network Isomorphism, positive result on binary: The phylogenetic network isomorphism problem can be solved in O(n4) 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 deduced from subclasses

No negative result could be deduced from subclasses.

Properties

Properties proved for this class

No property found

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 #7 : Here is a time-consistent labeling t:

• t(r)=0
• t(a)=t(b)=t(e)=1
• t(c)=t(d)=t(f)=t(1)=2
• t(2)=t(3)=t(4)=3

network #3 : Here is a time-consistent labeling t:
• t(r)=0
• t(a)=t(f)=1
• t(b)=t(c)=t(d)=t(e)=t(g)=t(h)=t(i)=2
• t(1)=t(2)=t(3)=t(4)=t(5)=3

network #2 : Here is a time-consistent labeling t:
• t(r)=0
• t(a)=1
• t(b)=2
• t(c)=t(d)=t(e)=t(f)=t(g)=t(h)=t(i)=3
• t(1)=t(2)=t(3)=t(4)=t(5)=4

network #8 : Here is a time-consistent labeling t:
• t(r)=0
• t(a)=1
• t(d)=t(i)=2
• t(g)=t(5)=3
• t(b)=t(e)=t(h)=4
• t(c)=t(f)=t(1)=t(4)=5
• t(2)=t(3)=6

network #23 : Here is a time-consistent labeling t:
• t(r)=0
• t(a)=t(g)=1
• t(b)=t(c)=t(d)=t(e)=t(f)=t(h)=t(i)=t(j)=2
• t(1)=t(2)=t(3)=t(4)=3

Deduced from class inclusions: no network found in this class using class inclusions

Not in this class

Proved directly:
network #5 : The redundant arc from r to c makes it impossible to build a time-consistent labeling of the vertices.
network #6 : The redundant arc from r to b makes it impossible to build a time-consistent labeling of the vertices.
network #22 : If the network is time-consistent, then there would exist a time-consistent labeling t. As a and f are b's parents, t(a)=t(b)=t(f). As c and e are d's parents, t(c)=t(d)=t(e). However, t(f)>t(e) and t(c)>t(a).
network #1 : The redundant arc from f to a makes it impossible to build a time-consistent labeling of the vertices.
network #10 : The redundant arc from a to c makes it impossible to build a time-consistent labeling of the vertices.
network #4 : The redundant arc from b to e makes it impossible to build a time-consistent labeling of the vertices.

Deduced from class inclusions: no network found outside this class using class inclusions

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.