Who is Who in Phylogenetic Networks

Publications related to 'NP complete' : An NP-complete problem is in the complexity class NP and every problem in NP is reducible in polynomial time to this problem (Wikipedia).   Order by:   Type | Year

Only And Or     related to:

Associated keywords

abstract-network agreement-forest approximation APX-hard branch-length characterization cherry-picking circular-split-system cluster-containment compressed-network cophylogeny duplication dynamic-programming evaluation explicit-network FPT from-binets from-clusters from-multilabeled-tree from-network from-rooted-trees from-sequences from-species-tree from-subnetworks from-trinets from-triplets from-unrooted-trees FU-stable-network galled-network galled-tree heuristic hybridization inapproximability integer-linear-programming labeling lateral-gene-transfer level-k-phylogenetic-network likelihood loss MASN minimum-number nested-network normal-network NP-complete optimal-realization parsimony perfect phylogenetic-network phylogeny planar polynomial Program-Dendroscope Program-Level2 Program-McKiTscH Program-MPNet Program-SPNet pseudo-polynomial pyramid realization recombination reconstruction regular-network software split-network SPR-distance temporal-hybridization-number time-consistent-network tree-containment tree-sibling-network tree-based-network tree-child-network uniqueness unrooted-tree-based-network visualization weak-hierarchy weakly-displaying

2020

1 Jonathan Klawitter and Peter Stumpf. Drawing Tree-Based Phylogenetic Networks with Minimum Number of Crossings. 2020. Keywords: explicit network, FPT, minimum number, NP complete, phylogenetic network, phylogeny, polynomial, visualization. Note: https://arxiv.org/abs/2008.08960.

2019

2 Steven Kelk, Fabio Pardi, Celine Scornavacca and Leo van Iersel. Finding the most parsimonious or likely tree in a network with respect to an alignment. In JOMB, Vol. 78:527-547, 2019. Keywords: APX hard, from network, from sequences, likelihood, NP complete, parsimony. Note: https://arxiv.org/abs/1707.03648.         3 Janosch Döcker, Leo van Iersel, Steven Kelk and Simone Linz. Deciding the existence of a cherry-picking sequence is hard on two trees. In DAM, Vol. 260:131-143, 2019. Keywords: cherry-picking, explicit network, hybridization, minimum number, NP complete, phylogenetic network, phylogeny, reconstruction, temporal-hybridization number, time consistent network, tree-child network. Note: https://arxiv.org/abs/1712.02965.

2018

4 Leo van Iersel, Steven Kelk, Giorgios Stamoulis, Leen Stougie and Olivier Boes. On unrooted and root-uncertain variants of several well-known phylogenetic network problems. In ALG, Vol. 80(11):2993-3022, 2018. Keywords: explicit network, FPT, from network, from unrooted trees, NP complete, phylogenetic network, phylogeny, reconstruction, tree containment. Note: https://hal.inria.fr/hal-01599716.         5 Andrew R. Francis, Katharina Huber and Vincent Moulton. Tree-based unrooted phylogenetic networks. In BMB, Vol. 80(2):404-416, 2018. Keywords: characterization, explicit network, NP complete, phylogenetic network, phylogeny, tree containment, tree-based network, unrooted tree-based network. Note: https://arxiv.org/abs/1704.02062.         6 Janosch Döcker and Simone Linz. On the existence of a cherry-picking sequence. In TCS, Vol. 714:36-50, 2018. Keywords: cherry-picking, explicit network, from rooted trees, NP complete, phylogenetic network, phylogeny, reconstruction, temporal-hybridization number, time consistent network, tree-child network. Note: https://arxiv.org/abs/1712.04127.         7 Leo van Iersel, Mark Jones and Celine Scornavacca. Improved maximum parsimony models for phylogenetic networks. In SB, Vol. 67(3):518-542, 2018. Keywords: explicit network, FPT, from sequences, NP complete, parsimony, phylogenetic network, phylogeny, reconstruction, weakly displaying. Note: https://leovaniersel.files.wordpress.com/2017/12/improved_parsimony_networks.pdf.

2017

8 Katharina Huber, Leo van Iersel, Vincent Moulton, Celine Scornavacca and Taoyang Wu. Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets. In ALG, Vol. 77(1):173-200, 2017. Keywords: explicit network, FPT, from binets, from subnetworks, from trinets, NP complete, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/1411.6804.         9 Misagh Kordi and Mukul S. Bansal. On the Complexity of Duplication-Transfer-Loss Reconciliation with Non-Binary Gene Trees. In TCBB, Vol. 14(3):587-599, 2017. Keywords: duplication, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://compbio.engr.uconn.edu/papers/Kordi_DTLreconciliationPreprint2015.pdf.         10 Leo van Iersel, Vincent Moulton, Eveline De Swart and Taoyang Wu. Binets: fundamental building blocks for phylogenetic networks. In BMB, Vol. 79(5):1135-1154, 2017. Keywords: approximation, explicit network, from binets, from subnetworks, galled tree, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1007/s11538-017-0275-4.

2016

11 Katharina Huber, Vincent Moulton, Mike Steel and Taoyang Wu. Folding and unfolding phylogenetic trees and networks. In JOMB, Vol. 73(6):1761-1780, 2016. Keywords: compressed network, explicit network, FU-stable network, NP complete, phylogenetic network, phylogeny, tree containment, tree sibling network. Note: http://arxiv.org/abs/1506.04438.         12 Maria Anaya, Olga Anipchenko-Ulaj, Aisha Ashfaq, Joyce Chiu, Mahedi Kaiser, Max Shoji Ohsawa, Megan Owen, Ella Pavlechko, Katherine St. John, Shivam Suleria, Keith Thompson and Corrine Yap. On Determining if Tree-based Networks Contain Fixed Trees. In BMB, Vol. 78(5):961-969, 2016. Keywords: explicit network, FPT, NP complete, phylogenetic network, phylogeny, tree-based network. Note: http://arxiv.org/abs/1602.02739.         13 Philippe Gambette, Leo van Iersel, Steven Kelk, Fabio Pardi and Celine Scornavacca. Do branch lengths help to locate a tree in a phylogenetic network? In BMB, Vol. 78(9):1773-1795, 2016. Keywords: branch length, explicit network, FPT, from network, from rooted trees, NP complete, phylogenetic network, phylogeny, pseudo-polynomial, time consistent network, tree containment, tree sibling network. Note: http://arxiv.org/abs/1607.06285.         14 Ioannis G. Tollis and Konstantinos G. Kakoulis. Algorithms for Visualizing Phylogenetic Networks. In GD16, Vol. 9801:183-195 of LNCS, springer, 2016. Keywords: explicit network, galled network, galled tree, NP complete, planar, visualization. Note: http://arxiv.org/abs/1609.00755.

2015

15 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.         16 Misagh Kordi and Mukul S. Bansal. On the Complexity of Duplication-Transfer-Loss Reconciliation with Non-Binary Gene Trees. In ISBRA15, Vol. 9096:187-198 of LNCS, springer, 2015. Keywords: duplication, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://compbio.engr.uconn.edu/papers/Kordi_ISBRA2015.pdf.

2014

17 Anthony Labarre and Sicco Verwer. Merging partially labelled trees: hardness and a declarative programming solution. In TCBB, Vol. 11(2):389-397, 2014. Keywords: abstract network, from unrooted trees, heuristic, NP complete, phylogenetic network, phylogeny, reconstruction. Note: https://hal-upec-upem.archives-ouvertes.fr/hal-00855669.         Toggle abstract "Intraspecific studies often make use of haplotype networks instead of gene genealogies to represent the evolution of a set of genes. Cassens et al. proposed one such network reconstruction method, based on the global maximum parsimony principle, which was later recast by the first author of the present work as the problem of finding a minimum common supergraph of a set of t partially labelled trees. Although algorithms have been proposed for solving that problem on two graphs, the complexity of the general problem on trees remains unknown. In this paper, we show that the corresponding decision problem is NP-complete for t=3. We then propose a declarative programming approach to solving the problem to optimality in practice, as well as a heuristic approach, both based on the idpsystem, and assess the performance of both methods on randomly generated data. © 2004-2012 IEEE."

2013

18 Peter J. Humphries, Simone Linz and Charles Semple. On the complexity of computing the temporal hybridization number for two phylogenies. In DAM, Vol. 161:871-880, 2013. Keywords: agreement forest, APX hard, characterization, from rooted trees, hybridization, NP complete, phylogenetic network, phylogeny, reconstruction, time consistent network. Note: http://ab.inf.uni-tuebingen.de/people/linz/publications/TAFapx.pdf.         Toggle abstract "Phylogenetic networks are now frequently used to explain the evolutionary history of a set of species for which a collection of gene trees, reconstructed from genetic material of different parts of the species' genomes, reveal inconsistencies. However, in the context of hybridization, the reconstructed networks are often not temporal. If a hybridization network is temporal, then it satisfies the time constraint of instantaneously occurring hybridization events; i.e. all species that are involved in such an event coexist in time. Furthermore, although a collection of phylogenetic trees can often be merged into a hybridization network that is temporal, many algorithms do not necessarily find such a network since their primary optimization objective is to minimize the number of hybridization events. In this paper, we present a characterization for when two rooted binary phylogenetic trees admit a temporal hybridization network. Furthermore, we show that the underlying optimization problem is APX-hard and, therefore, NP-hard. Thus, unless P=NP, it is unlikely that there are efficient algorithms for either computing an exact solution or approximating it within a ratio arbitrarily close to one. © 2012 Elsevier B.V. All rights reserved." 19 Peter J. Humphries, Simone Linz and Charles Semple. Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies. In BMB, Vol. 75(10):1879-1890, 2013. Keywords: characterization, cherry-picking, from rooted trees, hybridization, NP complete, phylogenetic network, phylogeny, reconstruction, time consistent network. Note: http://ab.inf.uni-tuebingen.de/people/linz/publications/CPSpaper.pdf.         Toggle abstract "Recently, we have shown that calculating the minimum-temporal-hybridization number for a set P of rooted binary phylogenetic trees is NP-hard and have characterized this minimum number when P consists of exactly two trees. In this paper, we give the first characterization of the problem for P being arbitrarily large. The characterization is in terms of cherries and the existence of a particular type of sequence. Furthermore, in an online appendix to the paper, we show that this new characterization can be used to show that computing the minimum-temporal hybridization number for two trees is fixed-parameter tractable. © 2013 Society for Mathematical Biology."

2011

20 Ali Tofigh, Mike Hallett and Jens Lagergren. Simultaneous Identification of Duplications and Lateral Gene Transfers. In TCBB, Vol. 8(2):517-535, 2011. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1109/TCBB.2010.14.         Toggle abstract "The incongruency between a gene tree and a corresponding species tree can be attributed to evolutionary events such as gene duplication and gene loss. This paper describes a combinatorial model where so-called DTL-scenarios are used to explain the differences between a gene tree and a corresponding species tree taking into account gene duplications, gene losses, and lateral gene transfers (also known as horizontal gene transfers). The reasonable biological constraint that a lateral gene transfer may only occur between contemporary species leads to the notion of acyclic DTL-scenarios. Parsimony methods are introduced by defining appropriate optimization problems. We show that finding most parsimonious acyclic DTL-scenarios is NP-hard. However, by dropping the condition of acyclicity, the problem becomes tractable, and we provide a dynamic programming algorithm as well as a fixed-parameter tractable algorithm for finding most parsimonious DTL-scenarios. © 2011 IEEE." 21 Leo van Iersel and Steven Kelk. When two trees go to war. In JTB, Vol. 269(1):245-255, 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 non-treelike evolutionary histories. Such networks are often constructed by combining trees, clusters, triplets or characters into a single network that in some well-defined 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 (non-treelike 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."

2010

22 Simone Linz, Charles Semple and Tanja Stadler. Analyzing and reconstructing reticulation networks under timing constraints. In JOMB, Vol. 61(5):715-737, 2010. Keywords: explicit network, from rooted trees, hybridization, lateral gene transfer, NP complete, phylogenetic network, phylogeny, reconstruction, time consistent network. Note: http://dx.doi.org/10.1007/s00285-009-0319-y..         Toggle abstract "Reticulation networks are now frequently used to model the history of life for various groups of species whose evolutionary past is likely to include reticulation events such as horizontal gene transfer or hybridization. However, the reconstructed networks are rarely guaranteed to be temporal. If a reticulation network is temporal, then it satisfies the two biologically motivated timing constraints of instantaneously occurring reticulation events and successively occurring speciation events. On the other hand, if a reticulation network is not temporal, it is always possible to make it temporal by adding a number of additional unsampled or extinct taxa. In the first half of the paper, we show that deciding whether a given number of additional taxa is sufficient to transform a non-temporal reticulation network into a temporal one is an NP-complete problem. As one is often given a set of gene trees instead of a network in the context of hybridization, this motivates the second half of the paper which provides an algorithm, called TemporalHybrid, for reconstructing a temporal hybridization network that simultaneously explains the ancestral history of two trees or indicates that no such network exists. We further derive two methods to decide whether or not a temporal hybridization network exists for two given trees and illustrate one of the methods on a grass data set. © 2009 The Author(s)." 23 Leo van Iersel, Charles Semple and Mike Steel. Locating a tree in a phylogenetic network. In IPL, Vol. 110(23), 2010. Keywords: cluster containment, explicit network, from network, level k phylogenetic network, normal network, NP complete, phylogenetic network, polynomial, regular network, time consistent network, tree containment, tree sibling network, tree-child network. Note: http://arxiv.org/abs/1006.3122.         Toggle abstract "Phylogenetic trees and networks are leaf-labelled graphs that are used to describe evolutionary histories of species. The Tree Containment problem asks whether a given phylogenetic tree is embedded in a given phylogenetic network. Given a phylogenetic network and a cluster of species, the Cluster Containment problem asks whether the given cluster is a cluster of some phylogenetic tree embedded in the network. Both problems are known to be NP-complete in general. In this article, we consider the restriction of these problems to several well-studied classes of phylogenetic networks. We show that Tree Containment is polynomial-time solvable for normal networks, for binary tree-child networks, and for level-k networks. On the other hand, we show that, even for tree-sibling, time-consistent, regular networks, both Tree Containment and Cluster Containment remain NP-complete. © 2010 Elsevier B.V. All rights reserved." 24 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/.

2009

25 Leo van Iersel, Steven Kelk and Matthias Mnich. Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks. In JBCB, Vol. 7(4):597-623, 2009. Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, reconstruction, uniqueness. Note: http://arxiv.org/pdf/0712.2932v2.         26 Ran Libeskind-Hadas and Michael A. Charleston. On the Computational Complexity of the Reticulate Cophylogeny Reconstruction Problem. In JCB, Vol. 16(1):105-117, 2009. Keywords: cophylogeny, heuristic, NP complete, parsimony, phylogenetic network, reconstruction. Note: http://dx.doi.org/10.1089/cmb.2008.0084.         Toggle abstract "The cophylogeny reconstruction problem is that of finding minimal cost explanations of differences between evolutionary histories of ecologically linked groups of biological organisms. We present a proof that shows that the general problem of reconciling evolutionary histories is NP-complete and provide a sharp boundary where this intractability begins. We also show that a related problem, that of finding Pareto optimal solutions, is NP-hard. As a byproduct of our results, we give a framework by which meta-heuristics can be applied to find good solutions to this problem. © Mary Ann Liebert, Inc. 2009." 27 Daniel H. Huson, Regula Rupp, Vincent Berry, Philippe Gambette and Christophe Paul. Computing Galled Networks from Real Data. In ISMBECCB09, Vol. 25(12):i85-i93 of BIO, 2009. Keywords: abstract network, cluster containment, explicit network, FPT, from clusters, from rooted trees, galled network, NP complete, phylogenetic network, phylogeny, polynomial, Program Dendroscope, reconstruction. Note: http://hal-lirmm.ccsd.cnrs.fr/lirmm-00368545/en/.         Toggle abstract "Motivation: Developing methods for computing phylogenetic networks from biological data is an important problem posed by molecular evolution and much work is currently being undertaken in this area. Although promising approaches exist, there are no tools available that biologists could easily and routinely use to compute rooted phylogenetic networks on real datasets containing tens or hundreds of taxa. Biologists are interested in clades, i.e. groups of monophyletic taxa, and these are usually represented by clusters in a rooted phylogenetic tree. The problem of computing an optimal rooted phylogenetic network from a set of clusters, is hard, in general. Indeed, even the problem of just determining whether a given network contains a given cluster is hard. Hence, some researchers have focused on topologically restricted classes of networks, such as galled trees and level-k networks, that are more tractable, but have the practical draw-back that a given set of clusters will usually not possess such a representation. Results: In this article, we argue that galled networks (a generalization of galled trees) provide a good trade-off between level of generality and tractability. Any set of clusters can be represented by some galled network and the question whether a cluster is contained in such a network is easy to solve. Although the computation of an optimal galled network involves successively solving instances of two different NP-complete problems, in practice our algorithm solves this problem exactly on large datasets containing hundreds of taxa and many reticulations in seconds, as illustrated by a dataset containing 279 prokaryotes. © 2009 The Author(s)." 28 Ali Tofigh. Using Trees to Capture Reticulate Evolution, Lateral Gene Transfers and Cancer Progression. PhD thesis, KTH Royal Institute of Technology, Sweden, 2009. Keywords: duplication, dynamic programming, from multilabeled tree, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://kth.diva-portal.org/smash/record.jsf?pid=diva2:220830&searchId=1.

2008

29 Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, Ferry Hagen and Teun Boekhout. Constructing level-2 phylogenetic networks from triplets. In RECOMB08, Vol. 4955:450-462 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 level-1 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 level-2 networks. This shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily nontree-like. This further strengthens the case for the use of triplet-based methods in the construction of phylogenetic networks. We also implemented the algorithm and applied it to yeast data. © 2009 IEEE." 30 Iyad A. Kanj, Luay Nakhleh, Cuong Than and Ge Xia. Seeing the Trees and Their Branches in the Network is Hard. In TCS, Vol. 401:153-164, 2008. Keywords: evaluation, from network, from rooted trees, NP complete, phylogenetic network, phylogeny, tree containment. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcs08.pdf.

2007

31 Magnus Bordewich and Charles Semple. Computing the minimum number of hybridization events for a consistent evolutionary history. In DAM, Vol. 155:914-918, 2007. Keywords: agreement forest, approximation, APX hard, explicit network, from rooted trees, hybridization, inapproximability, NP complete, phylogenetic network, phylogeny, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS06a.pdf.         32 Iyad A. Kanj, Luay Nakhleh, Cuong Than and Ge Xia. Seeing the Trees and Their Branches in the Network is Hard. In Proceedings of the Tenth Italian Conference on Theoretical Computer Science (ICTCS'07), 2007. Keywords: evaluation, from network, from rooted trees, NP complete, phylogenetic network, phylogeny, tree containment. Note: http://www.cs.rice.edu/~nakhleh/Papers/ictcs07.pdf.         33 Cam Thach Nguyen, Nguyen Bao Nguyen, Wing-Kin Sung and Louxin Zhang. Reconstructing Recombination Network from Sequence Data: The Small Parsimony Problem. In TCBB, Vol. 4(3):394-402, 2007. Keywords: explicit network, from sequences, labeling, NP complete, parsimony, phylogenetic network, phylogeny. Note: http://www.cs.washington.edu/homes/ncthach/Papers/TCBB2007.pdf.

2006

34 Pawel Górecki. Detection of horizontal gene transfer. PhD thesis, Warsaw University, Poland, 2006. Keywords: explicit network, from rooted trees, from species tree, lateral gene transfer, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction.

2005

35 Magnus Bordewich and Charles Semple. On the computational complexity of the rooted subtree prune and regraft distance. In ACOM, Vol. 8:409-423, 2005. Keywords: agreement forest, from rooted trees, NP complete, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS04.pdf.         Toggle abstract "The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is fixed parameter tractable when parameterised by the distance between the two trees." 36 Charles Choy, Jesper Jansson, Kunihiko Sadakane and Wing-Kin Sung. Computing the maximum agreement of phylogenetic networks. In TCS, Vol. 335(1):93-107, 2005. Keywords: dynamic programming, FPT, level k phylogenetic network, MASN, NP complete, phylogenetic network, phylogeny. Note: http://www.df.lth.se/~jj/Publications/masn8_TCS2005.pdf.         Toggle abstract "We introduce the maximum agreement phylogenetic subnetwork problem (MASN) for finding branching structure shared by a set of phylogenetic networks. We prove that the problem is NP-hard even if restricted to three phylogenetic networks and give an O(n2)-time algorithm for the special case of two level-1 phylogenetic networks, where n is the number of leaves in the input networks and where N is called a level-f phylogenetic network if every biconnected component in the underlying undirected graph induces a subgraph of N containing at most f nodes with indegree 2. We also show how to extend our technique to yield a polynomial-time algorithm for any two level-f phylogenetic networks N1,N2 satisfying f=O(logn); more precisely, its running time is O(|V(N1)|·|V(N2)|·2f1+f2), where V(Ni) and fi denote the set of nodes in Ni and the level of Ni, respectively, for i∈{1,2}. © 2005 Elsevier B.V. All rights reserved." 37 Trinh N. D. Huynh, Jesper Jansson, Nguyen Bao Nguyen and Wing-Kin Sung. Constructing a Smallest Refining Galled Phylogenetic Network. In RECOMB05, Vol. 3500:265-280 of LNCS, springer, 2005. Keywords: from rooted trees, galled tree, NP complete, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction. Note: http://www.df.lth.se/~jj/Publications/refining_gn3_RECOMB2005.pdf.         38 Jesper Jansson and Wing-Kin Sung. The Maximum Agreement of Two Nested Phylogenetic Networks. In ISAAC04, Vol. 3341:581-593 of LNCS, springer, 2005. Keywords: dynamic programming, MASN, nested network, NP complete, phylogenetic network, phylogeny, polynomial. Note: http://www.df.lth.se/~jj/Publications/nested7_ISAAC2004.pdf.

2004

39 Charles Choy, Jesper Jansson, Kunihiko Sadakane and Wing-Kin Sung. Computing the maximum agreement of phylogenetic networks. In Proceedings of Computing: the Tenth Australasian Theory Symposium (CATS'04), Vol. 91:134-147 of Electronic Notes in Theoretical Computer Science, 2004. Keywords: dynamic programming, FPT, level k phylogenetic network, MASN, NP complete, phylogenetic network, phylogeny. Note: http://www.df.lth.se/~jj/Publications/masn6_CATS2004.pdf.         Toggle abstract "We introduce the maximum agreement phylogenetic subnetwork problem (MASN) of finding a branching structure shared by a set of phylogenetic networks. We prove that the problem is NP-hard even if restricted to three phylogenetic networks and give an O(n2)-time algorithm for the special case of two level-1 phylogenetic networks, where n is the number of leaves in the input networks and where N is called a level-f phylogenetic network if every biconnected component in the underlying undirected graph contains at most f nodes having indegree 2 in N. Our algorithm can be extended to yield a polynomial-time algorithm for two level-f phylogenetic networks N 1,N2 for any f which is upper-bounded by a constant; more precisely, its running time is O(|V(N1)|·|V(N 2)|·4f), where V(Ni) denotes the set of nodes of Ni. © 2004 Published by Elsevier B.V." 40 Mike Hallett, Jens Lagergren and Ali Tofigh. Simultaneous Identification of Duplications and Lateral Transfers. In RECOMB04, Pages 347-356, 2004. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.nada.kth.se/~jensl/p164-hallett.pdf.         41 Mike Hallett and Jens Lagergren. Efficient algorithms for lateral gene transfers problems. 2004. Keywords: from rooted trees, lateral gene transfer, NP complete, phylogeny, polynomial, reconstruction. Note: submitted to SIAM Journal on Computing, http://www.mcb.mcgill.ca/~hallett/Lateral.pdf.         42 Pawel Górecki. Reconciliation problems for duplication, loss and horizontal gene transfer. In RECOMB04, Pages 316-325, 2004. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://ai.stanford.edu/~serafim/CS374_2004/Papers/Gorecki_Reconciliation.pdf.

2003

43 Pawel Górecki. Single step reconciliation algorithm for duplication, loss and horizontal gene transfer model. In ECCB03, 2003. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.inra.fr/eccb2003/posters/pdf/short/S_gorecki.ps.

2001

44 Mike Hallett and Jens Lagergren. Efficient algorithms for lateral gene transfers problems. In RECOMB01, Pages 141-148, 2001. Keywords: from rooted trees, lateral gene transfer, NP complete, phylogeny, polynomial, Program McKiTscH, reconstruction. Note: http://dx.doi.org/10.1145/369133.369188.         45 Lusheng Wang, Kaizhong Zhang and Louxin Zhang. Perfect phylogenetic networks with recombination. In SAC01, Pages 46-50, 2001. Keywords: from sequences, galled tree, NP complete, perfect, phylogenetic network, phylogeny, polynomial, recombination, reconstruction. Note: http://dx.doi.org/10.1145/372202.372271.

1998

46 John Kececioglu and Dan Gusfield. Reconstructing a history of recombinations from a set of sequences. In DAM, Pages 239-260, 1998. Keywords: from sequences, NP complete, polynomial, recombination, reconstruction. Note: http://citeseer.ist.psu.edu/76600.html.

1994

47 John Kececioglu and Dan Gusfield. Reconstructing a history of recombinations from a set of sequences. In SODA94, Pages 471-480, 1994. Keywords: from sequences, NP complete, polynomial, recombination, reconstruction. Note: http://portal.acm.org/citation.cfm?id=314626#.

1986

48 Ingo Althöfer. On optimal realizations of finite metric spaces by graphs. In Discrete and Computational Geometry, Vol. 3(1):103-122, 1986. Keywords: NP complete, optimal realization, realization. Note: http://dx.doi.org/10.1007/BF02187901.         Toggle abstract "Graph realizations of finite metric spaces have widespread applications, for example, in biology, economics, and information theory. The main results of this paper are: 1. Finding optimal realizations of integral metrics (which means all distances are integral) is NP-complete. 2. There exist metric spaces with a continuum of optimal realizations. Furthermore, two conditions necessary for a weighted graph to be an optimal realization are given and an extremal problem arising in connection with the realization problem is investigated. © 1988 Springer-Verlag New York Inc."