Who is Who in Phylogenetic Networks

Publications list	Showing 421 - 450 (752 total)

421 Poornima Venugopal. Improving layout of phylogenetic network produced by PADRE. Master's thesis, University of Texas at Dallas, U.S.A., 2009. Keywords: explicit network, phylogenetic network, Program PADRE, visualization. Note: http://proquest.umi.com/pqdlink?did=2026498501&sid=1&Fmt=2&clientId=176295&RQT=309&VName=PQD.         422 Lichen Bao. Phylogenetic network construction and the application. PhD thesis, University of Texas at Dallas, U.S.A., 2009. Keywords: from distances, phylogenetic network, phylogeny, reconstruction, split, split network. Note: http://proquest.umi.com/pqdlink?did=1952801881&sid=1&Fmt=6&clientId=176295&RQT=309&VName=PQD.         423 Chris Whidden. A Unifying View on Approximation and FPT of Agreement Forests. Master's thesis, Dalhousie University, Canada, 2009. Keywords: agreement forest, approximation, explicit network, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, reconstruction, SPR distance. Note: http://web.cs.dal.ca/~whidden/MCSThesis09.pdf.         424 Poornima Venugopal and Sergey Bereg. Layout of Phylogenetic Networks and Multi-Labeled Trees. In BIOT'09, Pages 91, 2009. Keywords: explicit network, phylogenetic network, phylogeny, Program PADRE, visualization. Note: http://www.biotconf.org/PDFs/1456.pdf.         425 Thu-Hien To and Michel Habib. Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time. In CPM09, (5577):275-288, springer, 2009. Keywords: explicit network, from triplets, level k phylogenetic network, minimum number, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/0901.1657.         Toggle abstract "For a given dense triplet set Τ there exist two natural questions [7]: Does there exist any phylogenetic network consistent with Τ? In case such networks exist, can we find an effective algorithm to construct one? For cases of networks of levels k = 0, 1 or 2, these questions were answered in [1,6,7,8,10] with effective polynomial algorithms. For higher levels k, partial answers were recently obtained in [11] with an O(/Τ/k+1)time algorithm for simple networks. In this paper, we give a complete answer to the general case, solving a problem proposed in [7]. The main idea of our proof is to use a special property of SN-sets in a level-k network. As a consequence, for any fixed k, we can also find a level-k network with the minimum number of reticulations, if one exists, in polynomial time. © 2009 Springer Berlin Heidelberg." 426 Philippe Gambette, Vincent Berry and Christophe Paul. The structure of level-k phylogenetic networks. In CPM09, Vol. 5577:289-300 of LNCS, springer, 2009. Keywords: coalescent, explicit network, galled tree, level k phylogenetic network, phylogenetic network, Program Recodon. Note: http://hal-lirmm.ccsd.cnrs.fr/lirmm-00371485/en/.         Toggle abstract "Evolution is usually described as a phylogenetic tree, but due to some exchange of genetic material, it can be represented as a phylogenetic network which has an underlying tree structure. The notion of level was recently introduced as a parameter on realistic kinds of phylogenetic networks to express their complexity and tree-likeness. We study the structure of level-k networks, and how they can be decomposed into level-k generators. We also provide a polynomial time algorithm which takes as input the set of level-k generators and builds the set of level-(k + 1) generators. Finally, with a simulation study, we evaluate the proportion of level-k phylogenetic networks among networks generated according to the coalescent model with recombination. © 2009 Springer Berlin Heidelberg." 427 Robert G. Beiko and Mark A. Ragan. Untangling Hybrid Phylogenetic Signals: Horizontal Gene Transfer and Artifacts of Phylogenetic Reconstruction. In Horizontal Gene Transfer, Vol. 532:241-256 of Methods in Molecular Biology, 2009. Note: http://dx.doi.org/10.1007/978-1-60327-853-9_14.         Toggle abstract "Phylogenomic methods can be used to investigate the tangled evolutionary relationships among genomes. Building 'all the trees of all the genes' can potentially identify common pathways of horizontal gene transfer (HGT) among taxa at varying levels of phylogenetic depth. Phylogenetic affinities can be aggregated and merged with the information about genetic linkage and biochemical function to examine hypotheses of adaptive evolution via HGT. Additionally, the use of many genetic data sets increases the power of statistical tests for phylogenetic artifacts. However, large-scale phylogenetic analyses pose several challenges, including the necessary abandonment of manual validation techniques, the need to translate inferred phylogenetic discordance into inferred HGT events, and the challenges involved in aggregating results from search-based inference methods. In this chapter we describe a tree search procedure to recover the most parsimonious pathways of HGT, and examine some of the assumptions that are made by this method." 428 Maria S. Poptsova. Testing Phylogenetic Methods to Identify Horizontal Gene Transfer. In Horizontal Gene Transfer, Pages 227-240, 2009. Note: http://dx.doi.org/10.1007/978-1-60327-853-9_13.         Toggle abstract "The subject of this chapter is to describe the methodology for assessing the power of phylogenetic HGT detection methods. Detection power is defined in the framework of hypothesis testing. Rates of false positives and false negatives can be estimated by testing HGT detection methods on HGT-free orthologous sets, and on the same sets with in silico simulated HGT events. The whole process can be divided into three steps: obtaining HGT-free orthologous sets, in silico simulation of HGT events in the same set, and submitting both sets for evaluation by any of the tested methods.Phylogenetic methods of HGT detection can be roughly divided into three types: likelihood-based tests of topologies (Kishino-Hasegawa (KH), Shimodaira-Hasegawa (SH), and Approximately Unbiased (AU) tests), tree distance methods (symmetrical difference of Robinson and Foulds (RF), and Subtree Pruning and Regrafting (SPR) distances), and genome spectral approaches (bipartition and quartet decomposition analysis). Restrictions that are inherent to phylogenetic methods of HGT detection in general and the power and precision of each method are discussed and comparative analyses of different approaches are provided, as well as some examples of assessing the power of phylogenetic HGT detection methods from a case study of orthologous sets from gamma-proteobacteria (Poptsova and Gogarten, BMC Evol Biol 7, 45, 2007) and cyanobacteria (Zhaxybayeva et al., Genome Res 16, 1099-108, 2006)." 429 Lichen Bao and Sergey Bereg. Counting Faces in Split Networks. In ISBRA09, Vol. 5251:284-295 of LNCS, 2009. Note: http://dx.doi.org/10.1007/978-3-642-01551-9_12.         Toggle abstract SplitsTree is a popular program for inferring and visualizing various phylogenetic networks including split networks. Split networks are useful for realizing metrics that are linear combinations of split metrics. We show that the realization is not unique in some cases and design an algorithm for computing split networks with minimum number of faces. We also prove that the minimum number of faces in a split network is equal to the number of pairs of incompatible splits. 430 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)." 431 Luay Nakhleh, Derek Ruths and Hideki Innan. Gene Trees, Species Trees, and Species Networks. In R. Guerra, D. B. Allison and D. Goldstein editors, Meta-analysis and Combining Information in Genetics and Genomics, 2009. Keywords: coalescent, explicit network, from rooted trees, from species tree, phylogenetic network, phylogeny, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/GuerraGoldsteinBookChapter.pdf.         432 Vincent Moulton and Katharina Huber. Split Networks. A tool for exploring complex evolutionary relationships in molecular data. In Philippe Lemey, Marco Salemi and Anne-Mieke Vandamme editors, The Phylogenetic Handbook, Cambridge University Press, 2009. Keywords: abstract network, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split network.         433 Chris Whidden and Norbert Zeh. A Unifying View on Approximation and FPT of Agreement Forests. In WABI09, Vol. 5724:390-402 of LNCS, Springer, 2009. Keywords: agreement forest, approximation, explicit network, FPT, minimum number, phylogenetic network, phylogeny, reconstruction. Note: https://www.cs.dal.ca/sites/default/files/technical_reports/CS-2009-02.pdf.         Toggle abstract "We provide a unifying view on the structure of maximum (acyclic) agreement forests of rooted and unrooted phylogenies. This enables us to obtain linear- or O(n log n)-time 3-approximation and improved fixed-parameter algorithms for the subtree prune and regraft distance between two rooted phylogenies, the tree bisection and reconnection distance between two unrooted phylogenies, and the hybridization number of two rooted phylogenies. © 2009 Springer Berlin Heidelberg." 434 Stefan Grünewald, Katharina Huber, Vincent Moulton, Charles Semple and Andreas Spillner. Characterizing weak compatibility in terms of weighted quartets. In Advances in Applied Mathematics, Vol. 42(3):329-341, 2009. Keywords: abstract network, characterization, from quartets, split network, weak hierarchy. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/GHMSS08.pdf, slides at http://www.lirmm.fr/miep08/slides/12_02_huber.pdf.         435 Peter J. Humphries and Charles Semple. Note on the hybridization number and subtree distance in phylogenetics. In Applied Mathematics Letters, Vol. 22(4):611-615, 2009. Keywords: explicit network, minimum number, phylogenetic network, phylogeny, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/HS08.pdf.         436 Stefan Grünewald, Jacobus Koolen and Woo-Sun Lee. Quartets in maximal weakly compatible split systems. In Applied Mathematics Letters, Vol. 22(6):1604-1608, 2009. Note: http://dx.doi.org/10.1016/j.aml.2009.05.006.         Toggle abstract "Weakly compatible split systems are a generalization of unrooted evolutionary trees and are commonly used to display reticulate evolution or ambiguity in biological data. They are collections of bipartitions of a finite set X of taxa (e.g. species) with the property that, for every four taxa, at least one of the three bipartitions into two pairs (quartets) is not induced by any of the X-splits. We characterize all split systems where exactly two quartets from every quadruple are induced by some split. On the other hand, we construct maximal weakly compatible split systems where the number of induced quartets per quadruple tends to 0 with the number of taxa going to infinity. © 2009." 437 Martin Lott, Andreas Spillner, Katharina Huber and Vincent Moulton. PADRE: A Package for Analyzing and Displaying Reticulate Evolution. In BIO, Vol. 25(9):1199-1200, 2009. Keywords: duplication, explicit network, from multilabeled tree, phylogenetic network, phylogeny, Program PADRE, reconstruction, software. Note: http://dx.doi.org/10.1093/bioinformatics/btp133.         Toggle abstract "Recent advances in gene sequencing for polyploid species, coupled with standard phylogenetic tree reconstruction, leads to gene trees in which the same species can label several leaves. Such multi-labeled trees are then used to reconstruct the evolutionary history of the polyploid species in question. However, this reconstruction process requires new techniques that are not available in current phylogenetic software packages. Here, we describe the software package PADRE (Package for Analyzing and Displaying Reticulate Evolution) that implements such techniques, allowing the reconstruction of complex evolutionary histories for polyploids in the form of phylogenetic networks. © The Author 2009. Published by Oxford University Press. All rights reserved." 438 Mark A. Ragan. Trees and networks before and after Darwin. In Biology Direct, Vol. 4(43), 2009. Keywords: abstract network, explicit network, phylogenetic network, phylogeny, survey, visualization. Note: http://dx.doi.org/10.1186/1745-6150-4-43.         Toggle abstract "It is well-known that Charles Darwin sketched abstract trees of relationship in his 1837 notebook, and depicted a tree in the Origin of Species (1859). Here I attempt to place Darwin's trees in historical context. By the mid-Eighteenth century the Great Chain of Being was increasingly seen to be an inadequate description of order in nature, and by about 1780 it had been largely abandoned without a satisfactory alternative having been agreed upon. In 1750 Donati described aquatic and terrestrial organisms as forming a network, and a few years later Buffon depicted a network of genealogical relationships among breeds of dogs. In 1764 Bonnet asked whether the Chain might actually branch at certain points, and in 1766 Pallas proposed that the gradations among organisms resemble a tree with a compound trunk, perhaps not unlike the tree of animal life later depicted by Eichwald. Other trees were presented by Augier in 1801 and by Lamarck in 1809 and 1815, the latter two assuming a transmutation of species over time. Elaborate networks of affinities among plants and among animals were depicted in the late Eighteenth and very early Nineteenth centuries. In the two decades immediately prior to 1837, so-called affinities and/or analogies among organisms were represented by diverse geometric figures. Series of plant and animal fossils in successive geological strata were represented as trees in a popular textbook from 1840, while in 1858 Bronn presented a system of animals, as evidenced by the fossil record, in a form of a tree. Darwin's 1859 tree and its subsequent elaborations by Haeckel came to be accepted in many but not all areas of biological sciences, while network diagrams were used in others. Beginning in the early 1960s trees were inferred from protein and nucleic acid sequences, but networks were re-introduced in the mid-1990s to represent lateral genetic transfer, increasingly regarded as a fundamental mode of evolution at least for bacteria and archaea. In historical context, then, the Network of Life preceded the Tree of Life and might again supersede it. Reviewers: This article was reviewed by Eric Bapteste, Patrick Forterre and Dan Graur. © 2009 Ragan; licensee BioMed Central Ltd." 439 Laxmi Parida, Asif Javed, Marta Melé, Francesc Calafell, Jaume Bertranpetit and Genographic Consortium. Minimizing recombinations in consensus networks for phylogeographic studies. In BMCB, Vol. 10(Suppl 1):S72, 2009. Note: Selected papers from the Seventh Asia-Pacific Bioinformatics Conference (APBC 2009), http://dx.doi.org/10.1186/1471-2105-10-S1-S72.         Toggle abstract "Background: We address the problem of studying recombinational variations in (human) populations. In this paper, our focus is on one computational aspect of the general task: Given two networks G1 and G2, with both mutation and recombination events, defined on overlapping sets of extant units the objective is to compute a consensus network G3 with minimum number of additional recombinations. We describe a polynomial time algorithm with a guarantee that the number of computed new recombination events is within = sz(G1, G2) (function sz is a well-behaved function of the sizes and topologies of G1 and G2) of the optimal number of recombinations. To date, this is the best known result for a network consensus problem. Results: Although the network consensus problem can be applied to a variety of domains, here we focus on structure of human populations. With our preliminary analysis on a segment of the human Chromosome X data we are able to infer ancient recombinations, population-specific recombinations and more, which also support the widely accepted 'Out of Africa' model. These results have been verified independently using traditional manual procedures. To the best of our knowledge, this is the first recombinations-based characterization of human populations. Conclusion: We show that our mathematical model identifies recombination spots in the individual haplotypes; the aggregate of these spots over a set of haplotypes defines a recombinational landscape that has enough signal to detect continental as well as population divide based on a short segment of Chromosome X. In particular, we are able to infer ancient recombinations, population-specific recombinations and more, which also support the widely accepted 'Out of Africa' model. The agreement with mutation-based analysis can be viewed as an indirect validation of our results and the model. Since the model in principle gives us more information embedded in the networks, in our future work, we plan to investigate more non-traditional questions via these structures computed by our methodology. © 2009 Parida et al; licensee BioMed Central Ltd." 440 Sarah C. Ayling and Terence A. Brown. Novel methodology for construction and pruning of quasi-median networks. In BMCB, Vol. 9:115, 2009. Keywords: abstract network, from sequences, median network, phylogenetic network, phylogeny, quasi-median network, reconstruction. Note: http://dx.doi.org/10.1186/1471-2105-9-115.         Toggle abstract "BACKGROUND: Visualising the evolutionary history of a set of sequences is a challenge for molecular phylogenetics. One approach is to use undirected graphs, such as median networks, to visualise phylogenies where reticulate relationships such as recombination or homoplasy are displayed as cycles. Median networks contain binary representations of sequences as nodes, with edges connecting those sequences differing at one character; hypothetical ancestral nodes are invoked to generate a connected network which contains all most parsimonious trees. Quasi-median networks are a generalisation of median networks which are not restricted to binary data, although phylogenetic information contained within the multistate positions can be lost during the preprocessing of data. Where the history of a set of samples contain frequent homoplasies or recombination events quasi-median networks will have a complex topology. Graph reduction or pruning methods have been used to reduce network complexity but some of these methods are inapplicable to datasets in which recombination has occurred and others are procedurally complex and/or result in disconnected networks. RESULTS: We address the problems inherent in construction and reduction of quasi-median networks. We describe a novel method of generating quasi-median networks that uses all characters, both binary and multistate, without imposing an arbitrary ordering of the multistate partitions. We also describe a pruning mechanism which maintains at least one shortest path between observed sequences, displaying the underlying relations between all pairs of sequences while maintaining a connected graph. CONCLUSION: Application of this approach to 5S rDNA sequence data from sea beet produced a pruned network within which genetic isolation between populations by distance was evident, demonstrating the value of this approach for exploration of evolutionary relationships." 441 Martin Lott, Andreas Spillner, Katharina Huber, Anna Petri, Bengt Oxelman and Vincent Moulton. Inferring polyploid phylogenies from multiply-labeled gene trees. In BMCEB, Vol. 9:216, 2009. Keywords: duplication, explicit network, from multilabeled tree, phylogenetic network, phylogeny, Program PADRE, reconstruction. Note: http://dx.doi.org/10.1186/1471-2148-9-216.         Toggle abstract "Background : Gene trees that arise in the context of reconstructing the evolutionary history of polyploid species are often multiply-labeled, that is, the same leaf label can occur several times in a single tree. This property considerably complicates the task of forming a consensus of a collection of such trees compared to usual phylogenetic trees. Results. We present a method for computing a consensus tree of multiply-labeled trees. As with the well-known greedy consensus tree approach for phylogenetic trees, our method first breaks the given collection of gene trees into a set of clusters. It then aims to insert these clusters one at a time into a tree, starting with the clusters that are supported by most of the gene trees. As the problem to decide whether a cluster can be inserted into a multiply-labeled tree is computationally hard, we have developed a heuristic method for solving this problem. Conclusion. We illustrate the applicability of our method using two collections of trees for plants of the genus Silene, that involve several allopolyploids at different levels. © 2009 Lott et al; licensee BioMed Central Ltd." 442 Stefan Grünewald, Vincent Moulton and Andreas Spillner. Consistency of the QNet algorithm for generating planar split networks from weighted quartets. In DAM, Vol. 157(10):2325-2334, 2009. Keywords: abstract network, consistency, from quartets, phylogenetic network, phylogeny, Program QNet, reconstruction, software. Note: http://dx.doi.org/10.1016/j.dam.2008.06.038.         Toggle abstract "Phylogenetic networks are a generalization of evolutionary or phylogenetic trees that allow the representation of conflicting signals or alternative evolutionary histories in a single diagram. Recently the Quartet-Net or "QNet" method was introduced, a method for computing a special kind of phylogenetic network called a split network from a collection of weighted quartet trees (i.e. phylogenetic trees with 4 leaves). This can be viewed as a quartet analogue of the distance-based Neighbor-Net (NNet) method for constructing outer-labeled planar split networks. In this paper, we prove that QNet is a consistent method, that is, we prove that if QNet is applied to a collection of weighted quartets arising from a circular split weight function, then it will return precisely this function. This key property of QNet not only ensures that it is guaranteed to produce a tree if the input corresponds to a tree, and an outer-labeled planar split network if the input corresponds to such a network, but also provides the main guiding principle for the design of the method. © 2008 Elsevier B.V. All rights reserved." 443 Ulrik Brandes and Sabine Cornelsen. Phylogenetic Graph Models Beyond Trees. In DAM, Vol. 157(10):2361-2369, 2009. Keywords: abstract network, cactus graph, from splits, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.inf.uni-konstanz.de/~cornelse/Papers/bc-pgmbt-07.pdf.         Toggle abstract "A graph model for a set S of splits of a set X consists of a graph and a map from X to the vertices of the graph such that the inclusion-minimal cuts of the graph represent S. Phylogenetic trees are graph models in which the graph is a tree. We show that the model can be generalized to a cactus (i.e. a tree of edges and cycles) without losing computational efficiency. A cactus can represent a quadratic rather than linear number of splits in linear space. We show how to decide in linear time in the size of a succinct representation of S whether a set of splits has a cactus model, and if so construct it within the same time bounds. As a byproduct, we show how to construct the subset of all compatible splits and a maximal compatible set of splits in linear time. Note that it is N P-complete to find a compatible subset of maximum size. Finally, we briefly discuss further generalizations of tree models. © 2008 Elsevier B.V. All rights reserved." 444 Marc Thuillard and Didier Fraix-Burnet. Phylogenetic Applications of the Minimum Contradiction Approach on Continuous Characters. In Evolutionary Bioinformatics, Vol. 5:53-46, 2009. Keywords: from continuous characters, minimum contradiction, phylogenetic network, phylogeny, split, split network. Note: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2747132/.         445 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.         446 Sagi Snir and Tamir Tuller. The NET-HMM approach: Phylogenetic Network Inference by Combining Maximum Likelihood and Hidden Markov Models. In JBCB, Vol. 7(4):625-644, 2009. Keywords: explicit network, from sequences, HMM, lateral gene transfer, likelihood, phylogenetic network, phylogeny, statistical model. Note: http://research.haifa.ac.il/~ssagi/published%20papers/Snir-NET-HMM-JBCB-2009.pdf.         Toggle abstract "Horizontal gene transfer (HGT) is the event of transferring genetic material from one lineage in the evolutionary tree to a different lineage. HGT plays a major role in bacterial genome diversification and is a significant mechanism by which bacteria develop resistance to antibiotics. Although the prevailing assumption is of complete HGT, cases of partial HGT (which are also named chimeric HGT) where only part of a gene is horizontally transferred, have also been reported, albeit less frequently. In this work we suggest a new probabilistic model, the NET-HMM, for analyzing and modeling phylogenetic networks. This new model captures the biologically realistic assumption that neighboring sites of DNA or amino acid sequences are not independent, which increases the accuracy of the inference. The model describes the phylogenetic network as a Hidden Markov Model (HMM), where each hidden state is related to one of the network's trees. One of the advantages of the NET-HMM is its ability to infer partial HGT as well as complete HGT. We describe the properties of the NET-HMM, devise efficient algorithms for solving a set of problems related to it, and implement them in software. We also provide a novel complementary significance test for evaluating the fitness of a model (NET-HMM) to a given dataset. Using NET-HMM, we are able to answer interesting biological questions, such as inferring the length of partial HGT's and the affected nucleotides in the genomic sequences, as well as inferring the exact location of HGT events along the tree branches. These advantages are demonstrated through the analysis of synthetical inputs and three different biological inputs. © 2009 Imperial College Press." 447 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." 448 Francesc Rosselló and Gabriel Valiente. All that Glisters is not Galled. In MBIO, Vol. 221(1):54-59, 2009. Keywords: galled tree, phylogenetic network, phylogeny. Note: http://arxiv.org/abs/0904.2448.         Toggle abstract "Galled trees, evolutionary networks with isolated reticulation cycles, have appeared under several slightly different definitions in the literature. In this paper, we establish the actual relationships between the main four such alternative definitions: namely, the original galled trees, level-1 networks, nested networks with nesting depth 1, and evolutionary networks with arc-disjoint reticulation cycles. © 2009 Elsevier Inc. All rights reserved." 449 Laura S. Kubatko. Identifying Hybridization Events in the Presence of Coalescence via Model Selection. In Systematic Biology, Vol. 58(5):478-488, 2009. Keywords: AIC, BIC, branch length, coalescent, explicit network, from rooted trees, from species tree, hybridization, lineage sorting, model selection, phylogenetic network, phylogeny, statistical model. Note: http://dx.doi.org/10.1093/sysbio/syp055.         450 Bui Quang Minh, Steffen Klaere and Arndt von Haeseler. Taxon Selection under Split Diversity. In Systematic Biology, Vol. 58(6):586-594, 2009. Keywords: abstract network, circular split system, diversity, from network, phylogenetic network, split network. Note: http://dx.doi.org/10.1093/sysbio/syp058.         Toggle abstract "The phylogenetic diversity (PD) measure of biodiversity is evaluated using a phylogenetic tree, usually inferred from morphological or molecular data. Consequently, it is vulnerable to errors in that tree, including those resulting from sampling error, model misspecification, or conflicting signals. To improve the robustness of PD, we can evaluate the measure using either a collection (or distribution) of trees or a phylogenetic network. Recently, it has been shown that these 2 approaches are equivalent but that the problem of maximizing PD in the general concept is NP-hard. In this study, we provide an efficient dynamic programming algorithm for maximizing PD when splits in the trees or network form a circular split system. We illustrate our method using a case study of game birds (Galliformes) and discuss the different choices of taxa based on our approach and PD."