Problem Definition and Terminology. A phylogenetic network is a connected, rooted, simple, directed acyclic graph in which: (1) each node has outdegree at most 2; (2) each node has indegree 1 or 2, except the root node which has indegree 0; (3) no node has both indegree 1 and outdegree 1; and (4) all nodes with outdegree 0 are labeled by elements from a finite set L in such a way that no two nodes are assigned the same label. From here on, nodes of outdegree 0 are referred to as leaves and identified with their corresponding elements in L. We denote the set of all nodes and the set of leaves in a phylogenetic network N by V (N ) and Λ(N ), respectively. | Given a phylogenetic network N and a set Lj, the topological restriction of N to Lj, denoted by N Lj, is defined as the phylogenetic network obtained by first deleting all nodes which are not on any directed path from the root to a leaf in Lj along with their incident edges, and then, for every node with outdegree 1 and indegree less than 2, contracting its outgoing edge (any resulting set of multiple edges between two nodes is replaced by a single edge). network of is a phylogenetic network A such that Λ(A) i∈N Λ(N ) and N ⊆ Given a set N = {N1,..., Nk} of phylogenetic networks, an agreement sub- N i ∈ N | for every Ni , A is isomorphic to a subgraph of Ni Λ(A) in which zero or more of the edges have been deleted and each outgoing edge from a node with M 1 To evaluate a construction method , repeat the following steps a number of times. First, randomly generate a network N and evolve a sequence down the edges of N ac- cording to some chosen model of evolution, then build a network Nj for the resulting set of sequences using M, and finally measure the similarity between Nj and N . N : 0 u 1 1 uL 2 u R 0 1 2 3 3 2 2
