Structure and Recognition of 3,4-leaf Powers of Galled Phylogenetic Networks in Polynomial Time

Details Structure and Recognition of 3,4-leaf Powers of Galled Phylogenetic Networks in Polynomial Time Structure and Recognition of 3,4-leaf Powers of Galled Phylogenetic Networks in Polynomial Time

2010-12-18

arxiv.org/abs/1012.4084v4

Computer Science

Discrete Mathematics

Scientific paper

A graph is a $k$-leaf power of a tree $T$ if its vertices are leaves of $T$ and two vertices are adjacent in $T$ if and only if their distance in $T$ is at most $k$. Then $T$ is a $k$-leaf root of $G$. This notion was introduced by Nishimura, Ragde, and Thilikos [2002] motivated by the search for underlying phylogenetic trees. We study here an extension of the $k$-leaf power graph recognition problem. This extension is motivated by a new biological question for the evaluation of the latteral gene transfer on a population of viruses. We allow the host graph to slightly differs from a tree and allow some cycles. In fact we study phylogenetic galled networks in which cycles are pairwise vertex disjoint. We show some structural results and propose polynomial algorithms for the cases $k=3$ and $k=4$. As a consequence, squares of galled networks can also be recognized in polynomial time.

Affiliated with

Also associated with

No associations

Rating

Structure and Recognition of 3,4-leaf Powers of Galled Phylogenetic Networks in Polynomial Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Structure and Recognition of 3,4-leaf Powers of Galled Phylogenetic Networks in Polynomial Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Structure and Recognition of 3,4-leaf Powers of Galled Phylogenetic Networks in Polynomial Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-157035