Who is Who in Phylogenetic Networks

Publications of Luay Nakhleh     Order by:   Type | Year
Associated keywords
abstract-network AIC approximation bayesian BIC bootstrap bound branch-length cluster-containment coalescent counting distance-between-networks evaluation explicit-network from-clusters from-distances from-multistate-characters from-network from-rooted-trees from-sequences from-species-tree from-unrooted-trees galled-tree generation heuristic hybridization incomplete-lineage-sorting lateral-gene-transfer likelihood lineage-sorting NP-complete parsimony perfect phylogenetic-network phylogeny polynomial Program-Dendroscope Program-LatTrans Program-Nepal Program-PhyloNet Program-PhyloNet-HMM Program-PhyloNetworks-SNaQ Program-PIRN Program-SplitsTree Program-SPNet reconstruction software split SPR-distance statistical-model survey time-consistent-network tree-containment tree-sibling-network tree-based-network tree-child-network tripartition-distance weakly-displaying
2019
1 R. A. Leo Elworth, Huw A. Ogilvie, Jiafan Zhu and Luay Nakhleh. Advances in Computational Methods for Phylogenetic Networks in the Presence of Hybridization. In Tandy Warnow editor, Bioinformatics and Phylogenetics. Seminal Contributions of Bernard Moret, Vol. 29 of Computational Biology, Springer, 2019. Keywords: explicit network, phylogenetic network, phylogeny, Program Dendroscope, Program PhyloNet, Program PhyloNetworks SNaQ, Program PIRN, Program SplitsTree, reconstruction, survey. Note: https://bioinfocs.rice.edu/sites/g/files/bxs266/f/ElworthZhuOgilvieNakhleh.pdf
2018
2 Dingqiao Wen, Yun Yu, Jiafan Zhu and Luay Nakhleh. Inferring Phylogenetic Networks Using PhyloNet. In SB, Vol. 67(4):735-740, 2018. Keywords: bayesian, likelihood, parsimony, phylogenetic network, phylogeny, Program PhyloNet, reconstruction, software.         3 Jiafan Zhu, Dingqiao Wen, Yun Yu, Heidi M. Meudt and Luay Nakhleh. Bayesian inference of phylogenetic networks from bi-allelic genetic markers. In PLoS Computational Biology, Vol. 14(1):e1005932.1-32, 2018. Keywords: bayesian, explicit network, from multistate characters, phylogenetic network, phylogeny, Program PhyloNet. Note: https://doi.org/10.1371/journal.pcbi.1005932.         4 Dingqiao Wen and Luay Nakhleh. Coestimating Reticulate Phylogenies and Gene Trees from Multilocus Sequence Data. In SB, Vol. 67(3):439-457, 2018. Keywords: bayesian, explicit network, from sequences, incomplete lineage sorting, phylogenetic network, phylogeny, Program PhyloNet, reconstruction. Note: https://doi.org/10.1093/sysbio/syx085.
2017
5 Luay Nakhleh. Phylogenetic Networks: From Displayed Trees to a Distribution of Gene Trees. Phyloseminar #70, 2017. Keywords: bayesian, coalescent, explicit network, phylogenetic network, phylogeny, Program PhyloNet, reconstruction, statistical model. Note: https://www.youtube.com/watch?v=dkQsvLUUDcQ.
2016
6 Dingqiao Wen, Yun Yu and Luay Nakhleh. Bayesian Inference of Reticulate Phylogenies under the Multispecies Network Coalescent. In PLoS Genetics, Vol. 12(5):e1006006, 2016. Keywords: bayesian, coalescent, phylogenetic network, phylogeny, Program PhyloNet, reconstruction, software.         7 Jiafan Zhu, Yun Yu and Luay Nakhleh. In the Light of Deep Coalescence: Revisiting Trees Within Networks. In RECOMB-CG16, Vol. 17(suppl. 14):415.271-282 of BMCB, 2016. Keywords: branch length, evaluation, explicit network, incomplete lineage sorting, phylogenetic network, phylogeny, statistical model, tree-based network, weakly displaying. Note: http://arxiv.org/abs/1606.07350.
2015
8 Yun Yu and Luay Nakhleh. A Distance-Based Method for Inferring Phylogenetic Networks in the Presence of Incomplete Lineage Sorting. In ISBRA15, Vol. 9096:378-389 of LNCS, springer, 2015. Keywords: bootstrap, explicit network, from distances, heuristic, incomplete lineage sorting, phylogenetic network, phylogeny, reconstruction. Note: http://bioinfo.cs.rice.edu/sites/bioinfo.cs.rice.edu/files/YuNakhleh-ISBRA15.pdf.         9 Yun Yu and Luay Nakhleh. A maximum pseudo-likelihood approach for phylogenetic networks. In RECOMB-CG15, Vol. 16(Suppl 10)(S10):1-10 of BMC Genomics, BioMed Central, 2015. Keywords: explicit network, from rooted trees, hybridization, incomplete lineage sorting, likelihood, phylogenetic network, phylogeny, Program PhyloNet, reconstruction, tripartition distance. Note: http://dx.doi.org/10.1186/1471-2164-16-S10-S10.
2014
10 Kevin J. Liu, Jingxuan Dai, Kathy Truong, Ying Song, Michael H. Kohn and Luay Nakhleh. An HMM-Based Comparative Genomic Framework for Detecting Introgression in Eukaryotes. In PLoS ONE, Vol. 10(6):e1003649, 2014. Keywords: explicit network, from network, phylogenetic network, phylogeny, Program PhyloNet-HMM. Note: http://arxiv.org/abs/1310.7989.         Toggle abstract "One outcome of interspecific hybridization and subsequent effects of evolutionary forces is introgression, which is the integration of genetic material from one species into the genome of an individual in another species. The evolution of several groups of eukaryotic species has involved hybridization, and cases of adaptation through introgression have been already established. In this work, we report on PhyloNet-HMM-a new comparative genomic framework for detecting introgression in genomes. PhyloNet-HMM combines phylogenetic networks with hidden Markov models (HMMs) to simultaneously capture the (potentially reticulate) evolutionary history of the genomes and dependencies within genomes. A novel aspect of our work is that it also accounts for incomplete lineage sorting and dependence across loci. Application of our model to variation data from chromosome 7 in the mouse (Mus musculus domesticus) genome detected a recently reported adaptive introgression event involving the rodent poison resistance gene Vkorc1, in addition to other newly detected introgressed genomic regions. Based on our analysis, it is estimated that about 9% of all sites within chromosome 7 are of introgressive origin (these cover about 13 Mbp of chromosome 7, and over 300 genes). Further, our model detected no introgression in a negative control data set. We also found that our model accurately detected introgression and other evolutionary processes from synthetic data sets simulated under the coalescent model with recombination, isolation, and migration. Our work provides a powerful framework for systematic analysis of introgression while simultaneously accounting for dependence across sites, point mutations, recombination, and ancestral polymorphism. © 2014 Liu et al." 11 Yun Yu, Jianrong Dong, Kevin J. Liu and Luay Nakhleh. Maximum likelihood inference of reticulate evolutionary histories. In PNAS, Vol. 111(46):16448-16453, 2014. Keywords: explicit network, likelihood, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1073/pnas.1407950111.
2013
12 Eric Bapteste, Leo van Iersel, Axel Janke, Scott Kelchner, Steven Kelk, James O. McInerney, David A. Morrison, Luay Nakhleh, Mike Steel, Leen Stougie and James B. Whitfield. Networks: expanding evolutionary thinking. In Trends in Genetics, Vol. 29(8):439-441, 2013. Keywords: abstract network, explicit network, phylogenetic network, phylogeny, reconstruction. Note: http://bioinf.nuim.ie/wp-content/uploads/2013/06/Bapteste-TiG-2013.pdf.         Toggle abstract "Networks allow the investigation of evolutionary relationships that do not fit a tree model. They are becoming a leading tool for describing the evolutionary relationships between organisms, given the comparative complexities among genomes. © 2013 Elsevier Ltd." 13 Yun Yu, R. Matthew Barnett and Luay Nakhleh. Parsimonious Inference of Hybridization in the Presence of Incomplete Lineage Sorting. In Systematic Biology, Vol. 62(5):738-751, 2013. Keywords: from network, from rooted trees, hybridization, lineage sorting, parsimony, phylogenetic network, phylogeny, Program PhyloNet, reconstruction.         Toggle abstract "Hybridization plays an important evolutionary role in several groups of organisms. A phylogenetic approach to detect hybridization entails sequencing multiple loci across the genomes of a group of species of interest, reconstructing their gene trees, and taking their differences as indicators of hybridization. However, methods that follow this approach mostly ignore population effects, such as incomplete lineage sorting (ILS). Given that hybridization occurs between closely related organisms, ILS may very well be at play and, hence, must be accounted for in the analysis framework. To address this issue, we present a parsimony criterion for reconciling gene trees within the branches of a phylogenetic network, and a local search heuristic for inferring phylogenetic networks from collections of gene-tree topologies under this criterion. This framework enables phylogenetic analyses while accounting for both hybridization and ILS. Further, we propose two techniques for incorporating information about uncertainty in gene-tree estimates. Our simulation studies demonstrate the good performance of our framework in terms of identifying the location of hybridization events, as well as estimating the proportions of genes that underwent hybridization. Also, our framework shows good performance in terms of efficiency on handling large data sets in our experiments. Further, in analysing a yeast data set, we demonstrate issues that arise when analysing real data sets. Although a probabilistic approach was recently introduced for this problem, and although parsimonious reconciliations have accuracy issues under certain settings, our parsimony framework provides a much more computationally efficient technique for this type of analysis. Our framework now allows for genome-wide scans for hybridization, while also accounting for ILS. [Phylogenetic networks; hybridization; incomplete lineage sorting; coalescent; multi-labeled trees.] © 2013 The Author(s). All rights reserved." 14 Luay Nakhleh. Computational approaches to species phylogeny inference and gene tree reconciliation. In Trends in Ecology and Evolution, Vol. 28(12):719-728, 2013. Keywords: from rooted trees, from species tree, phylogenetic network, phylogeny, reconstruction, survey. Note: http://bioinfo.cs.rice.edu/sites/bioinfo.cs.rice.edu/files/TREE-Nakhleh13.pdf.         Toggle abstract "An intricate relation exists between gene trees and species phylogenies, due to evolutionary processes that act on the genes within and across the branches of the species phylogeny. From an analytical perspective, gene trees serve as character states for inferring accurate species phylogenies, and species phylogenies serve as a backdrop against which gene trees are contrasted for elucidating evolutionary processes and parameters. In a 1997 paper, Maddison discussed this relation, reviewed the signatures left by three major evolutionary processes on the gene trees, and surveyed parsimony and likelihood criteria for utilizing these signatures to elucidate computationally this relation. Here, I review progress that has been made in developing computational methods for analyses under these two criteria, and survey remaining challenges. © 2013 Elsevier Ltd." 15 Yun Yu, Nikola Ristic and Luay Nakhleh. Fast algorithms and heuristics for phylogenomics under ILS and hybridization. In RECOMB-CG'13, Vol. 14(Suppl 15):S6 of BMCB, 2013. Keywords: from network, from rooted trees, heuristic, phylogenetic network, phylogeny, Program PhyloNet, reconstruction.
2012
16 Yun Yu and Luay Nakhleh. Fast Algorithms for Reconciliation under Hybridization and Incomplete Lineage Sorting. 2012. Keywords: hybridization, lineage sorting, phylogenetic network, phylogeny, Program PhyloNet, reconstruction, software. Note: http://arxiv.org/abs/1212.1909.         17 Yun Yu, James H. Degnan and Luay Nakhleh. The probability of a gene tree topology within a phylogenetic network with applications to hybridization detection. In PLoS Genetics, Vol. 8(4):e1002660, 2012. Keywords: AIC, BIC, explicit network, hybridization, phylogenetic network, phylogeny, statistical model. Note: http://dx.doi.org/10.1371/journal.pgen.1002660.         Toggle abstract "Gene tree topologies have proven a powerful data source for various tasks, including species tree inference and species delimitation. Consequently, methods for computing probabilities of gene trees within species trees have been developed and widely used in probabilistic inference frameworks. All these methods assume an underlying multispecies coalescent model. However, when reticulate evolutionary events such as hybridization occur, these methods are inadequate, as they do not account for such events. Methods that account for both hybridization and deep coalescence in computing the probability of a gene tree topology currently exist for very limited cases. However, no such methods exist for general cases, owing primarily to the fact that it is currently unknown how to compute the probability of a gene tree topology within the branches of a phylogenetic network. Here we present a novel method for computing the probability of gene tree topologies on phylogenetic networks and demonstrate its application to the inference of hybridization in the presence of incomplete lineage sorting. We reanalyze a Saccharomyces species data set for which multiple analyses had converged on a species tree candidate. Using our method, though, we show that an evolutionary hypothesis involving hybridization in this group has better support than one of strict divergence. A similar reanalysis on a group of three Drosophila species shows that the data is consistent with hybridization. Further, using extensive simulation studies, we demonstrate the power of gene tree topologies at obtaining accurate estimates of branch lengths and hybridization probabilities of a given phylogenetic network. Finally, we discuss identifiability issues with detecting hybridization, particularly in cases that involve extinction or incomplete sampling of taxa. © 2012 Yu et al." 18 Hyun Jung Park and Luay Nakhleh. MURPAR: A fast heuristic for inferring parsimonious phylogenetic networks from multiple gene trees. In ISBRA12, Vol. 7292:213-224 of LNCS, springer, 2012. Keywords: explicit network, from unrooted trees, heuristic, phylogenetic network, phylogeny, reconstruction, software. Note: https://www.researchgate.net/profile/Hyun_Jung_Park2/publication/262318595_MURPAR_A_Fast_Heuristic_for_Inferring_Parsimonious_Phylogenetic_Networks_from_Multiple_Gene_Trees/links/54b7e7b50cf269d8cbf58cc4.pdf.         Toggle abstract "Phylogenetic networks provide a graphical representation of evolutionary histories that involve non-treelike evolutionary events, such as horizontal gene transfer (HGT). One approach for inferring phylogenetic networks is based on reconciling gene trees, assuming all incongruence among the gene trees is due to HGT. Several mathematical results and algorithms, both exact and heuristic, have been introduced to construct and analyze phylogenetic networks. Here, we address the computational problem of inferring phylogenetic networks with minimum reticulations from a collection of gene trees. As this problem is known to be NP-hard even for a pair of gene trees, the problem at hand is very hard. In this paper, we present an efficient heuristic, MURPAR, for inferring a phylogenetic network from a collection of gene trees by using pairwise reconciliations of trees in the collection. Given the development of efficient and accurate methods for pairwise gene tree reconciliations, MURPAR inherits this efficiency and accuracy. Further, the method includes a formulation for combining pairwise reconciliations that is naturally amenable to an efficient integer linear programming (ILP) solution. We show that MURPAR produces more accurate results than other methods and is at least as fast, when run on synthetic and biological data. We believe that our method is especially important for rapidly obtaining estimates of genome-scale evolutionary histories that can be further refined by more detailed and compute-intensive methods. © 2012 Springer-Verlag." 19 Hyun Jung Park and Luay Nakhleh. Inference of reticulate evolutionary histories by maximum likelihood: The performance of information criteria. In RECOMB-CG'12, Vol. 13(suppl 19):S12 of BMCB, 2012. Keywords: AIC, BIC, explicit network, heuristic, likelihood, phylogenetic network, phylogeny, reconstruction, statistical model. Note: http://www.biomedcentral.com/1471-2105/13/S19/S12.
2011
20 Yun Yu, Cuong Than, James H. Degnan and Luay Nakhleh. Coalescent Histories on Phylogenetic Networks and Detection of Hybridization Despite Incomplete Lineage Sorting. In Systematic Biology, Vol. 60(2):138-149, 2011. Keywords: coalescent, hybridization, lineage sorting, reconstruction, statistical model. Note: http://www.cs.rice.edu/~nakhleh/Papers/YuEtAl-SB11.pdf.         Toggle abstract "Analyses of the increasingly available genomic data continue to reveal the extent of hybridization and its role in the evolutionary diversification of various groups of species. We show, through extensive coalescent-based simulations of multilocus data sets on phylogenetic networks, how divergence times before and after hybridization events can result in incomplete lineage sorting with gene tree incongruence signatures identical to those exhibited by hybridization. Evolutionary analysis of such data under the assumption of a species tree model can miss all hybridization events, whereas analysis under the assumption of a species network model would grossly overestimate hybridization events. These issues necessitate a paradigm shift in evolutionary analysis under these scenarios, from a model that assumes a priori a single source of gene tree incongruence to one that integrates multiple sources in a unifying framework. We propose a framework of coalescence within the branches of a phylogenetic network and show how this framework can be used to detect hybridization despite incomplete lineage sorting. We apply the model to simulated data and show that the signature of hybridization can be revealed as long as the interval between the divergence times of the species involved in hybridization is not too small. We reanalyze a data set of 106 loci from 7 in-group Saccharomyces species for which a species tree with no hybridization has been reported in the literature. Our analysis supports the hypothesis that hybridization occurred during the evolution of this group, explaining a large amount of the incongruence in the data. Our findings show that an integrative approach to gene tree incongruence and its reconciliation is needed. Our framework will help in systematically analyzing genomic data for the occurrence of hybridization and elucidating its evolutionary role. [Coalescent history; incomplete lineage sorting; hybridization; phylogenetic network.]. © 2011 The Author(s)."
2010
21 Luay Nakhleh. A Metric on the Space of Reduced Phylogenetic Networks. In TCBB, Vol. 7(2), 2010. Keywords: distance between networks, phylogenetic network, phylogeny. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcbb-Metric.pdf.         Toggle abstract "Phylogenetic networks are leaf-labeled, rooted, acyclic, and directed graphs that are used to model reticulate evolutionary histories. Several measures for quantifying the topological dissimilarity between two phylogenetic networks have been devised, each of which was proven to be a metric on certain restricted classes of phylogenetic networks. A biologically motivated class of phylogenetic networks, namely, reduced phylogenetic networks, was recently introduced. None of the existing measures is a metric on the space of reduced phylogenetic networks. In this paper, we provide a metric on the space of reduced phylogenetic networks that is computable in time polynomial in the size of the networks. © 2006 IEEE." 22 Luay Nakhleh. Evolutionary phylogenetic networks: models and issues. In L. Heath and N. Ramakrishnan editors, The Problem Solving Handbook for Computational Biology and Bioinformatics, Springer, 2010. Keywords: phylogenetic network, phylogeny, survey. Note: http://www.cs.rice.edu/~nakhleh/Papers/HeathRamakrishnanBookChapter.pdf.         23 Hyun Jung Park, Guohua Jin and Luay Nakhleh. Bootstrap-based Support of HGT Inferred by Maximum Parsimony. In BMCEB, Vol. 10:131, 2010. Keywords: bootstrap, explicit network, from sequences, lateral gene transfer, parsimony, phylogenetic network, phylogeny, Program Nepal, reconstruction. Note: http://dx.doi.org/10.1186/1471-2148-10-131.         Toggle abstract "Background. Maximum parsimony is one of the most commonly used criteria for reconstructing phylogenetic trees. Recently, Nakhleh and co-workers extended this criterion to enable reconstruction of phylogenetic networks, and demonstrated its application to detecting reticulate evolutionary relationships. However, one of the major problems with this extension has been that it favors more complex evolutionary relationships over simpler ones, thus having the potential for overestimating the amount of reticulation in the data. An ad hoc solution to this problem that has been used entails inspecting the improvement in the parsimony length as more reticulation events are added to the model, and stopping when the improvement is below a certain threshold. Results. In this paper, we address this problem in a more systematic way, by proposing a nonparametric bootstrap-based measure of support of inferred reticulation events, and using it to determine the number of those events, as well as their placements. A number of samples is generated from the given sequence alignment, and reticulation events are inferred based on each sample. Finally, the support of each reticulation event is quantified based on the inferences made over all samples. Conclusions. We have implemented our method in the NEPAL software tool (available publicly at http://bioinfo.cs.rice.edu/), and studied its performance on both biological and simulated data sets. While our studies show very promising results, they also highlight issues that are inherently challenging when applying the maximum parsimony criterion to detect reticulate evolution. © 2010 Park et al; licensee BioMed Central Ltd." 24 Hyun Jung Park, Guohua Jin and Luay Nakhleh. Algorithmic strategies for estimating the amount of reticulation from a collection of gene trees. In CSB10, 2010. Keywords: bound, from rooted trees, heuristic, phylogenetic network, phylogeny, reconstruction, SPR distance. Note: http://www.cs.rice.edu/~nakhleh/Papers/ParkEtAl-CSB2010.pdf.
2009
25 Guohua Jin, Luay Nakhleh, Sagi Snir and Tamir Tuller. Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-time Heuristic. In TCBB, Vol. 6(3):495-505, 2009. Keywords: explicit network, heuristic, parsimony, phylogenetic network, phylogeny, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcbb-MP.pdf.         26 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.
2008
27 Iyad A. Kanj, Luay Nakhleh and Ge Xia. The Compatibility of Binary Characters on Phylogenetic Networks: Complexity and Parameterized Algorithms. In ALG, Vol. 51(2):99-128, 2008. Keywords: perfect, phylogenetic network, phylogeny. Note: http://www.cs.rice.edu/~nakhleh/Papers/algorithmica.pdf.         28 Cuong Than and Luay Nakhleh. SPR-based Tree Reconciliation: Non-binary Trees and Multiple Solutions. In APBC08, Pages 251-260, 2008. Keywords: evaluation, from rooted trees, lateral gene transfer, phylogenetic network, phylogeny, Program LatTrans, Program PhyloNet, reconstruction, SPR distance. Note: http://www.cs.rice.edu/~nakhleh/Papers/apbc08.pdf.         29 Cuong Than, Derek Ruths and Luay Nakhleh. PhyloNet: A Software Package for Analyzing and Reconstructing Reticulate Evolutionary Relationships. In BMCB, Vol. 9(322), 2008. Keywords: Program PhyloNet, software. Note: http://dx.doi.org/10.1186/1471-2105-9-322.         Toggle abstract "Background: Phylogenies, i.e., the evolutionary histories of groups of taxa, play a major role in representing the interrelationships among biological entities. Many software tools for reconstructing and evaluating such phylogenies have been proposed, almost all of which assume the underlying evolutionary history to be a tree. While trees give a satisfactory first-order approximation for many families of organisms, other families exhibit evolutionary mechanisms that cannot be represented by trees. Processes such as horizontal gene transfer (HGT), hybrid speciation, and interspecific recombination, collectively referred to as reticulate evolutionary events, result in networks, rather than trees, of relationships. Various software tools have been recently developed to analyze reticulate evolutionary relationships, which include SplitsTree4, LatTrans, EEEP, HorizStory, and T-REX. Results: In this paper, we report on the PhyloNet software package, which is a suite of tools for analyzing reticulate evolutionary relationships, or evolutionary networks, which are rooted, directed, acyclic graphs, leaf-labeled by a set of taxa. These tools can be classified into four categories: (1) evolutionary network representation: reading/writing evolutionary networks in a newly devised compact form; (2) evolutionary network characterization: analyzing evolutionary networks in terms of three basic building blocks - trees, clusters, and tripartitions; (3) evolutionary network comparison: comparing two evolutionary networks in terms of topological dissimilarities, as well as fitness to sequence evolution under a maximum parsimony criterion; and (4) evolutionary network reconstruction: reconstructing an evolutionary network from a species tree and a set of gene trees. Conclusion: The software package, PhyloNet, offers an array of utilities to allow for efficient and accurate analysis of evolutionary networks. The software package will help significantly in analyzing large data sets, as well as in studying the performance of evolutionary network reconstruction methods. Further, the software package supports the proposed eNewick format for compact representation of evolutionary networks, a feature that allows for efficient interoperability of evolutionary network software tools. Currently, all utilities in PhyloNet are invoked on the command line. © 2008 Than et al; licensee BioMed Central Ltd." 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.         31 Cuong Than, Guohua Jin and Luay Nakhleh. Integrating Sequence and Topology for Efficient and Accurate Detection of Horizontal Gene Transfer. In Proceedings of the Sixth RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG'08), Vol. 5267:113-127 of LNCS, springer, 2008. Keywords: bootstrap, explicit network, from rooted trees, from sequences, lateral gene transfer, phylogenetic network, phylogeny, Program Nepal, Program PhyloNet, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/recombcg-08.pdf, slides available at http://igm.univ-mlv.fr/RCG08/RCG08slides/Cuong_Than_RCG08.pdf.
2007
32 Guohua Jin, Luay Nakhleh, Sagi Snir and Tamir Tuller. Efficient Parsimony-based Methods for Phylogenetic Network Reconstruction. In ECCB06, Vol. 23(2):e123-e128 of BIO, 2007. Keywords: parsimony, phylogenetic network, phylogeny, Program Nepal, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/eccb06.pdf.         33 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.         34 Guohua Jin, Luay Nakhleh, Sagi Snir and Tamir Tuller. Inferring Phylogenetic Networks by the Maximum Parsimony Criterion: A Case Study. In MBE, Vol. 24(1):324-337, 2007. Keywords: explicit network, parsimony, phylogenetic network, phylogeny, Program Nepal, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/MBE06.pdf.         35 Guohua Jin, Luay Nakhleh, Sagi Snir and Tamir Tuller. A New Linear-time Heuristic Algorithm for Computing the Parsimony Score of Phylogenetic Networks: Theoretical Bounds and Empirical Performance. In ISBRA07, Vol. 4463:61-72 of LNCS, springer, 2007. Keywords: approximation, heuristic, parsimony, phylogenetic network, phylogeny, Program Nepal. Note: http://www.cs.rice.edu/~nakhleh/Papers/isbra07.pdf.         36 Cuong Than, Derek Ruths, Hideki Innan and Luay Nakhleh. Confounding Factors in HGT Detection: Statistical Error, Coalescent Effects, and Multiple Solutions. In JCB, Vol. 14(4):517-535, 2007. Keywords: counting, explicit network, from rooted trees, from species tree, lateral gene transfer, phylogenetic network, phylogeny, Program LatTrans, Program PhyloNet. Note: http://www.cs.rice.edu/~nakhleh/Papers/recombcg06-jcb.pdf.
2006
37 Iyad A. Kanj, Luay Nakhleh and Ge Xia. Reconstructing Evolution of Natural Languages: Complexity and Parameterized Algorithms. In COCOON06, Vol. 4112:299-308 of LNCS, springer, 2006. Note: http://www.cs.rice.edu/~nakhleh/Papers/cocoon06.pdf.         38 Guohua Jin, Luay Nakhleh, Sagi Snir and Tamir Tuller. Maximum Likelihood of Phylogenetic Networks. In BIO, Vol. 22(21):2604-2611, 2006. Keywords: explicit network, likelihood, phylogenetic network, phylogeny, Program Nepal, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/NetworksML06.pdf, supplementary material: http://www.cs.rice.edu/~nakhleh/Papers/Supp-ML.pdf.         39 Cuong Than, Derek Ruths, Hideki Innan and Luay Nakhleh. Identifiability Issues in Phylogeny-Based Detection of Horizontal Gene Transfer. In Proceedings of the Fourth RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG'06), Vol. 4205:215-229 of LNCS, springer, 2006. Keywords: explicit network, from rooted trees, from species tree, lateral gene transfer, phylogenetic network, phylogeny, Program LatTrans, Program PhyloNet. Note: http://www.cs.rice.edu/~nakhleh/Papers/recombcg06-final.pdf.
2005
40 Luay Nakhleh, Guohua Jin, Fengmei Zhao and John Mellor-Crummey. Reconstructing Phylogenetic Networks Using Maximum Parsimony. In CSB05, Pages 93-102, 2005. Keywords: parsimony, phylogenetic network, phylogeny, Program Nepal, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/CSB05.pdf.         41 Luay Nakhleh and Li-San Wang. Phylogenetic Networks: Properties and Relationship to Trees and Clusters. In TCSB2, Vol. 3680:82-99 of LNCS, springer, 2005. Keywords: cluster containment, evaluation, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment, tree-child network. Note: http://www.cs.rice.edu/~nakhleh/Papers/LNCS_TCSB05.pdf.         42 Luay Nakhleh and Li-San Wang. Phylogenetic Networks, Trees, and Clusters. In IWBRA05, Vol. 3515:919-926 of LNCS, springer, 2005. Keywords: cluster containment, evaluation, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment, tree-child network. Note: http://www.cs.rice.edu/~nakhleh/Papers/NakhlehWang.pdf.         43 Derek Ruths and Luay Nakhleh. Recombination and phylogeny: effects and detection. In IJBRA, Pages 202-212, 2005. Note: http://www.cs.rice.edu/~nakhleh/Papers/IJBRA05.pdf.         44 Luay Nakhleh, Tandy Warnow, C. Randal Linder and Katherine St. John. Reconstructing reticulate evolution in species - theory and practice. In JCB, Vol. 12(6):796-811, 2005. Keywords: from rooted trees, galled tree, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction, software. Note: http://www.cs.rice.edu/~nakhleh/Papers/NWLSjcb.pdf.         45 Luay Nakhleh, Derek Ruths and Li-San Wang. RIATA-HGT: A Fast and Accurate Heuristic for Reconstructing Horizontal Gene Transfer. In COCOON05, Vol. 3595:84-93 of LNCS, springer, 2005. Keywords: from rooted trees, heuristic, lateral gene transfer, phylogenetic network, phylogeny, Program PhyloNet. Note: http://www.cs.rice.edu/~nakhleh/Papers/COCOON05.pdf.
2004
46 Luay Nakhleh. Phylogenetic Networks. PhD thesis, University of Texas at Austin, U.S.A., 2004. Keywords: distance between networks, evaluation, generation, phylogenetic network, phylogeny, Program SPNet, reconstruction, split, statistical model, tree sibling network. Note: http://www.library.utexas.edu/etd/d/2004/nakhlehl042/nakhlehl042.pdf.         47 Bernard M. E. Moret, Luay Nakhleh, Tandy Warnow, C. Randal Linder, Anna Tholse, Anneke Padolina, Jerry Sun and Ruth Timme. Phylogenetic Networks: Modeling, Reconstructibility, and Accuracy. In TCBB, Vol. 1(1):13-23, 2004. Keywords: distance between networks, evaluation, phylogenetic network, phylogeny, time consistent network, tripartition distance. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcbb04.pdf.         48 Luay Nakhleh, Tandy Warnow and C. Randal Linder. Reconstructing reticulate evolution in species - theory and practice. In RECOMB04, Pages 337-346, 2004. Keywords: from rooted trees, galled tree, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction, software. Note: http://www.cs.rice.edu/~nakhleh/Papers/144-nakhleh.pdf.         49 C. Randal Linder, Bernard M. E. Moret, Luay Nakhleh and Tandy Warnow. Network (Reticulate) Evolution: Biology, Models, and Algorithms. In PSB04, 2004. Note: http://www.cs.rice.edu/~nakhleh/Papers/psb04.pdf.
2003
50 Luay Nakhleh, Jerry Sun, Tandy Warnow, C. Randal Linder, Bernard M. E. Moret and Anna Tholse. Towards the Development of Computational Tools for Evaluating Phylogenetic Network Reconstruction Methods. In PSB03, 2003. Keywords: distance between networks, evaluation, phylogenetic network, phylogeny, polynomial, tripartition distance. Note: http://www.cs.rice.edu/~nakhleh/Papers/psb03.pdf.         51 Esra Erdem, Vladimir Lifschitz, Luay Nakhleh and Don Ringe. Reconstructing the evolutionary history of Indo-European languages using answer set programming. In PADL03, Vol. 2562:160-176 of LNCS, springer, 2003. Note: http://people.sabanciuniv.edu/~esraerdem/papers/padl03.ps.
2002
52 Bernard M. E. Moret, Luay Nakhleh and Tandy Warnow. An error metric for phylogenetic networks. 2002. Keywords: distance between networks, evaluation, phylogenetic network, phylogeny, tripartition distance. Note: Technical report TR-02-09, http://www.cs.unm.edu/~treport/tr/03-05/nakhleh.ps.gz.         53 Luay Nakhleh, Don Ringe and Tandy Warnow. Perfect Phylogenetic Networks: A New Methodology for Reconstructing the Evolutionary History of Natural Languages. In Language, Journal of the Linguistic Society of America, Vol. 81(2):382-420, 2002. Keywords: perfect, phylogenetic network, phylogeny. Note: http://www.cs.rice.edu/~nakhleh/Papers/81.2nakhleh.pdf.