






Leo van Iersel and
Steven Kelk. When two trees go to war. In JTB, Vol. 269(1):245255, 2011. Keywords: APX hard, explicit network, from clusters, from rooted trees, from sequences, from triplets, level k phylogenetic network, minimum number, NP complete, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/1004.5332.
Toggle abstract
"Rooted phylogenetic networks are used to model nontreelike evolutionary histories. Such networks are often constructed by combining trees, clusters, triplets or characters into a single network that in some welldefined sense simultaneously represents them all. We review these four models and investigate how they are related. Motivated by the parsimony principle, one often aims to construct a network that contains as few reticulations (nontreelike evolutionary events) as possible. In general, the model chosen influences the minimum number of reticulation events required. However, when one obtains the input data from two binary (i.e. fully resolved) trees, we show that the minimum number of reticulations is independent of the model. The number of reticulations necessary to represent the trees, triplets, clusters (in the softwired sense) and characters (with unrestricted multiple crossover recombination) are all equal. Furthermore, we show that these results also hold when not the number of reticulations but the level of the constructed network is minimised. We use these unification results to settle several computational complexity questions that have been open in the field for some time. We also give explicit examples to show that already for data obtained from three binary trees the models begin to diverge. © 2010 Elsevier Ltd."



Stephen J. Willson. Reconstruction of certain phylogenetic networks from the genomes at their leaves. In JTB, Vol. 252(2):185376, 2008. Keywords: labeling, polynomial. Note: http://www.public.iastate.edu/~swillson/ReconstructNormalHomopap6.pdf.
Toggle abstract
"A network N is a rooted acyclic digraph. A baseset X for N is a subset of vertices including the root (or outgroup), all leaves, and all vertices of outdegree 1. A simple model of evolution is considered in which all characters are binary and in which backmutations occur only at hybrid vertices. It is assumed that the genome is known for each member of the baseset X. If the network is known and is assumed to be "normal," then it is proved that the genome of every vertex is uniquely determined and can be explicitly reconstructed. Under additional hypotheses involving timeconsistency and separation of the hybrid vertices, the network itself can also be reconstructed from the genomes of all members of X. An explicit polynomialtime procedure is described for performing the reconstruction. © 2008 Elsevier Ltd. All rights reserved."


