Algorithms for Computational Biology by Unknown

Author:Unknown
Language: eng
Format: epub
ISBN: 9783030422660
Publisher: Springer International Publishing

2 Preliminaries

Definition 1

A phylogenetic semi-binary network N is a DAG with one outdegree-1 source (the root), a set L(N) of indegree-1 sinks (leaves) bijectively labelled with a set X, and all other nodes are either of indegree-1 and outdegree-2 (tree nodes) or of indegree at least 2 and outdegree-1 (reticulations).

A network is binary if all reticulations have indegree-2. In this paper, all networks we consider are phylogenetic semi-binary networks unless stated otherwise, so we call these networks for short. Furthermore, all networks have the leaf set , unless stated otherwise.

An edge feeding into reticulations is called a reticulation edge. Given an edge uv in N, we say that u is a parent of v and that v is a child of u. The node u is above v if there is a directed path from u to v in N. The network N is tree-child if every non-leaf node in N is a parent of a tree node or a leaf. The reticulation number is the total number of reticulation edges minus the total number of reticulations.

Let N and be tree-child networks on the same set of taxa X. Then N contains if can be obtained from N by deleting reticulation edges and suppressing degree-2 nodes. We now formally define the Tree-child Network Containment problem.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.