
Leo van Iersel,
Judith Keijsper,
Steven Kelk,
Leen Stougie,
Ferry Hagen and
Teun Boekhout. Constructing level2 phylogenetic networks from triplets. In RECOMB08, Vol. 4955:450462 of LNCS, springer, 2008. Keywords: explicit network, from triplets, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, polynomial, Program Level2, reconstruction. Note: http://homepages.cwi.nl/~iersel/level2full.pdf. An appendix with proofs can be found here http://arxiv.org/abs/0707.2890.
Toggle abstract
"Jansson and Sung showed that, given a dense set of input triplets T (representing hypotheses about the local evolutionary relationships of triplets of taxa), it is possible to determine in polynomial time whether there exists a level1 network consistent with T, and if so, to construct such a network [24]. Here, we extend this work by showing that this problem is even polynomial time solvable for the construction of level2 networks. This shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily nontreelike. This further strengthens the case for the use of tripletbased methods in the construction of phylogenetic networks. We also implemented the algorithm and applied it to yeast data. © 2009 IEEE."



Rune Lyngsø,
Yun S. Song and
Jotun Hein. Accurate Computation of Likelihoods in the Coalescent with Recombination via Parsimony. In RECOMB08, Vol. 4955:463477 of LNCS, springer, 2008. Keywords: coalescent, likelihood, phylogenetic network, phylogeny, recombination, statistical model. Note: http://dx.doi.org/10.1007/9783540788393_41.
Toggle abstract
"Understanding the variation of recombination rates across a given genome is crucial for disease gene mapping and for detecting signatures of selection, to name just a couple of applications. A widelyused method of estimating recombination rates is the maximum likelihood approach, and the problem of accurately computing likelihoods in the coalescent with recombination has received much attention in the past. A variety of sampling and approximation methods have been proposed, but no single method seems to perform consistently better than the rest, and there still is great value in developing better statistical methods for accurately computing likelihoods. So far, with the exception of some twolocus models, it has remained unknown how the true likelihood exactly behaves as a function of model parameters, or how close estimated likelihoods are to the true likelihood. In this paper, we develop a deterministic, parsimonybased method of accurately computing the likelihood for multilocus input data of moderate size. We first find the set of all ancestral configurations (ACs) that occur in evolutionary histories with at most k crossover recombinations. Then, we compute the likelihood by summing over all evolutionary histories that can be constructed only using the ACs in that set. We allow for an arbitrary number of crossing over, coalescent and mutation events in a history, as long as the transitions stay within that restricted set of ACs. For given parameter values, by gradually increasing the bound k until the likelihood stabilizes, we can obtain an accurate estimate of the likelihood. At least for moderate crossover rates, the algorithmbased method described here opens up a new window of opportunities for testing and finetuning statistical methods for computing likelihoods. © 2008 SpringerVerlag Berlin Heidelberg."


