Who is Who in Phylogenetic Networks

Publications related to 'integer linear programming'   Order by:   Type | Year

Only And Or     related to:

Associated keywords

abstract-network agreement-forest APX-hard characterization circular-split-system cluster-containment duplication explicit-network FPT from-binary-characters from-clusters from-network from-rooted-trees from-sequences from-triplets galled-tree heuristic History-bound hybridization integer-linear-programming level-k-phylogenetic-network loss minimum-number NP-complete parsimony phylogenetic-network phylogeny polynomial Program-Dendroscope Program-HapBound Program-HybridNumber Program-ILPEACE Program-MPNet Program-SHRUB Program-SPRDist pyramid recombination reconstruction SAT software split-network SPR-distance tanglegram visualization weak-hierarchy

Article (Journal)

1 Mareike Fischer, Leo van Iersel, Steven Kelk and Celine Scornavacca. On Computing The Maximum Parsimony Score Of A Phylogenetic Network. In SIDMA, Vol. 29(1):559-585, 2015. Keywords: APX hard, cluster containment, explicit network, FPT, from network, from sequences, integer linear programming, level k phylogenetic network, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, Program MPNet, reconstruction, software. Note: http://arxiv.org/abs/1302.2430.

InProceedings

2 Yun S. Song, Yufeng Wu and Dan Gusfield. Efficient computation of close lower and upper bounds on the minimum number of recombinations in biological sequence evolution. In ISMB05, Vol. 21:i413-i422 of BIO, 2005. Keywords: integer linear programming, minimum number, Program HapBound, Program SHRUB, recombination. Note: http://dx.doi.org/10.1093/bioinformatics/bti1033.         Toggle abstract "Motivation: We are interested in studying the evolution of DNA single nucleotide polymorphism sequences which have undergone (meiotic) recombination. For a given set of sequences, computing the minimum number of recombinations needed to explain the sequences (with one mutation per site) is a standard question of interest, but it has been shown to be NP-hard, and previous algorithms that compute it exactly work either only on very small datasets or on problems with special structure. Results: In this paper, we present efficient, practical methods for computing both upper and lower bounds on the minimum number of needed recombinations, and for constructing evolutionary histories that explain the input sequences. We study in detail the efficiency and accuracy of these algorithms on both simulated and real data sets. The algorithms produce very close upper and lower bounds, which match exactly in a surprisingly wide range of data. Thus, with the use of new, very effective lower bounding methods and an efficient algorithm for computing upper bounds, this approach allows the efficient, exact computation of the minimum number of needed recombinations, with high frequency in a large range of data. When upper and lower bounds match, evolutionary histories found by our algorithm correspond to the most parsimonious histories. © The Author 2005. Published by Oxford University Press. All rights reserved." 3 Yufeng Wu and Jiayin Wang. Fast Computation of the Exact Hybridization Number of Two Phylogenetic Trees. In ISBRA10, Vol. 6053:203-214 of LNCS, springer, 2010. Keywords: agreement forest, explicit network, from rooted trees, hybridization, integer linear programming, minimum number, phylogenetic network, phylogeny, Program HybridNumber, Program SPRDist, SPR distance. Note: http://www.engr.uconn.edu/~ywu/Papers/ISBRA10WuWang.pdf.         Toggle abstract "Hybridization is a reticulate evolutionary process. An established problem on hybridization is computing the minimum number of hybridization events, called the hybridization number, needed in the evolutionary history of two phylogenetic trees. This problem is known to be NP-hard. In this paper, we present a new practical method to compute the exact hybridization number. Our approach is based on an integer linear programming formulation. Simulation results on biological and simulated datasets show that our method (as implemented in program SPRDist) is more efficient and robust than an existing method. © 2010 Springer-Verlag Berlin Heidelberg." 4 Celine Scornavacca, Franziska Zickmann and Daniel H. Huson. Tanglegrams for Rooted Phylogenetic Trees and Networks. In ISMB11, Vol. 27(13):i248-i256 of BIO, 2011. Keywords: from network, heuristic, integer linear programming, phylogenetic network, phylogeny, Program Dendroscope, tanglegram, visualization. Note: http://dx.doi.org/10.1093/bioinformatics/btr210.         Toggle abstract "Motivation: In systematic biology, one is often faced with the task of comparing different phylogenetic trees, in particular in multi-gene analysis or cospeciation studies. One approach is to use a tanglegram in which two rooted phylogenetic trees are drawn opposite each other, using auxiliary lines to connect matching taxa. There is an increasing interest in using rooted phylogenetic networks to represent evolutionary history, so as to explicitly represent reticulate events, such as horizontal gene transfer, hybridization or reassortment. Thus, the question arises how to define and compute a tanglegram for such networks. Results: In this article, we present the first formal definition of a tanglegram for rooted phylogenetic networks and present a heuristic approach for computing one, called the NN-tanglegram method. We compare the performance of our method with existing tree tanglegram algorithms and also show a typical application to real biological datasets. For maximum usability, the algorithm does not require that the trees or networks are bifurcating or bicombining, or that they are on identical taxon sets. © The Author(s) 2011. Published by Oxford University Press." 5 Dan Gusfield. Persistent Phylogeny: A Galled-Tree and Integer Linear Programming Approach. In BCB15, Pages 443-451, 2015. Keywords: explicit network, from binary characters, galled tree, integer linear programming, phylogenetic network, phylogeny, reconstruction. Note: http://arxiv.org/abs/1506.00678.         6 Hannah Brown, Lei Zuo and Dan Gusfield. Comparing Integer Linear Programming to SAT-Solving for Hard Problems in Computational and Systems Biology. In AlCoB2020, Vol. 12099:63-76 of LNCS, Springer, 2020. Keywords: from binary characters, History bound, integer linear programming, minimum number, phylogeny, SAT. Note: https://doi.org/10.1007/978-3-030-42266-0_6.

PhdThesis

7 Philippe Gambette. Méthodes combinatoires de reconstruction de réseaux phylogénétiques. PhD thesis, Université Montpellier 2, France, 2010. Keywords: abstract network, characterization, circular split system, explicit network, FPT, from clusters, from triplets, integer linear programming, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, Program Dendroscope, pyramid, reconstruction, split network, weak hierarchy. Note: http://tel.archives-ouvertes.fr/tel-00608342/en/.

Misc

8 Leo van Iersel, Celine Scornavacca and Steven Kelk. Exact reconciliation of undated trees. 2014. Keywords: duplication, explicit network, integer linear programming, loss, phylogenetic network, phylogeny, Program ILPEACE, reconstruction. Note: https://arxiv.org/abs/1410.7004.