
HoLeung Chan,
Jesper Jansson,
TakWah Lam and
SiuMing Yiu. Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix. In JBCB, Vol. 4(4):807832, 2006. Keywords: explicit network, from distances, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/dist_ugn7_JBCB2006.pdf.
Toggle abstract
"Given a distance matrix M that specifies the pairwise evolutionary distances between n species, the phylogenetic tree reconstruction problem asks for an edgeweighted phylogenetic tree that satisfies M, if one exists. We study some extensions of this problem to rooted phylogenetic networks. Our main result is an O(n2 log n)time algorithm for determining whether there is an ultrametric galled network that satisfies M, and if so, constructing one. In fact, if such an ultrametric galled network exists, our algorithm is guaranteed to construct one containing the minimum possible number of nodes with more than one parent (hybrid nodes). We also prove that finding a largest possible submatrix M′ of M such that there exists an ultrametric galled network that satisfies M′ is NPhard. Furthermore, we show that given an incomplete distance matrix (i.e. where some matrix entries are missing), it is also NPhard to determine whether there exists an ultrametric galled network which satisfies it. © 2006 Imperial College Press."



Vladimir Makarenkov,
Dmytro Kevorkov and
Pierre Legendre. Phylogenetic Network Construction Approaches. In Applied Mycology and Biotechnology, Vol. 6:6197, 2006. Keywords: from distances, hybridization, lateral gene transfer, median network, NeighborNet, netting, Program Arlequin, Program Network, Program Pyramids, Program Reticlad, Program SplitsTree, Program T REX, Program TCS, Program WeakHierarchies, pyramid, reticulogram, split, split decomposition, split network, survey, weak hierarchy. Note: http://www.labunix.uqam.ca/~makarenv/makarenv/MKL_article.pdf.







Guillaume Bourque and
Louxin Zhang. Models and Methods in Comparative Genomics. In
ChauWen Tseng editor, Advances in Computers, Special Volume: Computational Biology, Vol. 68, Elsevier, 2006. Keywords: from distances, from rooted trees, from sequences, galled tree, phylogenetic network, phylogeny, survey. Note: http://www.math.nus.edu.sg/~matzlx/papers/CompGen_ZLX.pdf.



Mihaela Baroni and
Mike Steel. Accumulation Phylogenies. In ACOM, Vol. 10(1):1930, 2006. Keywords: abstract network, from clusters, from distances, phylogenetic network, phylogeny, polynomial, reconstruction, regular network. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.1960.
Toggle abstract
"We investigate the computational complexity of a new combinatorial problem of inferring a smallest possible multilabeled phylogenetic tree (MUL tree) which is consistent with each of the rooted triplets in a given set. We prove that even the restricted case of determining if there exists a MUL tree consistent with the input and having just one leaf duplication is NPhard. Furthermore, we show that the general minimization problem is NPhard to approximate within a ratio of n 1ε for any constant 0<ε≤1, where n denotes the number of distinct leaf labels in the input set, although a simple polynomialtime approximation algorithm achieves the approximation ratio n. We also provide an exact algorithm for the problem running in O *(7 n ) time and O *(3 n ) space. © 2009 SpringerVerlag Berlin Heidelberg."


