Who is Who in Phylogenetic Networks

Publications of Sagi Snir     Order by:   Type | Year
Associated keywords
approximation evaluation explicit-network from-sequences galled-tree heuristic HMM lateral-gene-transfer likelihood parsimony phylogenetic-network phylogeny Program-Nepal reconstruction statistical-model
2011
1 Shlomo Moran, Sagi Snir and Wing-Kin Sung. Partial Convex Recolorings of Trees and Galled Networks: Tight Upper and Lower bounds. In ACM Transactions on Algorithms, Vol. 7(4), 2011. Keywords: evaluation, galled tree, phylogenetic network. Note: http://www.cs.technion.ac.il/~moran/r/PS/gnets-TOA-7Feb2007.pdf.         Toggle abstract "A coloring of a graph is convex if the vertices that pertain to any color induce a connected subgraph; a partial coloring (which assigns colors to a subset of the vertices) is convex if it can be completed to a convex (total) coloring. Convex coloring has applications in fields such as phylogenetics, communication or transportation networks, etc. When a coloring of a graph is not convex, a natural question is how far it is from a convex one. This problem is denoted as convex recoloring (CR).While the initial works on CR defined and studied the problem on trees, recent efforts aim at either generalizing the underlying graphs or specializing the input colorings. In this work, we extend the underlying graph and the input coloring to partially colored galled networks. We show that although determining whether a coloring is convex on an arbitrary network is hard, it can be found efficiently on galled networks. We present a fixed parameter tractable algorithm that finds the recoloring distance of such a network whose running time is quadratic in the network size and exponential in that distance. This complexity is achieved by amortized analysis that uses a novel technique for contracting colored graphs that seems to be of independent interest. © 2011 ACM."
2010
2 Sagi Snir and Edward Trifonov. A Novel Technique for Detecting Putative Horizontal Gene Transfer in the Sequence Space. In JCB, Vol. 17(11):1535-1548, 2010. Keywords: from sequences, phylogenetic network, phylogeny, reconstruction. Note: http://research.haifa.ac.il/~ssagi/published%20papers/JCB-HGT.pdf.         Toggle abstract "Horizontal transfer (HT) is the event of a DNA sequence being transferred between species not by inheritance. This phenomenon violates the tree-like evolution of the species under study turning the trees into networks. At the sequence level, HT offers basic characteristics that enable not only clear identification and distinguishing from other sequence similarity cases but also the possibility of dating the events. We developed a novel, self-contained technique to identify relatively recent horizontal transfer elements (HTEs) in the sequences. Appropriate formalism allows one to obtain confidence values for the events detected. The technique does not rely on such problematic prerequisites as reliable phylogeny and/or statistically justified pairwise sequence alignment. In conjunction with the unique properties of HT, it gives rise to a two-level sequence similarity algorithm that, to the best of our knowledge, has not been explored. From evolutionary perspective, the novelty of the work is in the combination of small scale and large scale mutational events. The technique is employed on both simulated and real biological data. The simulation results show high capability of discriminating between HT and conserved regions. On the biological data, the method detected documented HTEs along with their exact locations in the recipient genomes. Supplementary Material is available online at www.libertonline.com/cmb. Copyright 2010, Mary Ann Liebert, Inc."
2009
3 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." 4 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.
2008
5 Sagi Snir and Tamir Tuller. Novel Phylogenetic Network Inference by Combining Maximum Likelihood and Hidden Markov Models. In WABI08, Vol. 5251:354-368 of LNCS, springer, 2008. Keywords: explicit network, from sequences, HMM, lateral gene transfer, likelihood, phylogenetic network, phylogeny, statistical model. Note: http://dx.doi.org/10.1007/978-3-540-87361-7_30.         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 for analyzing and modeling phylogenetic networks, the NET-HMM. 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 data set. 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 two different biological inputs. © 2008 Springer-Verlag Berlin Heidelberg."
2007
6 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.         7 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.         8 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.         9 Tamir Tuller and Sagi Snir. The NET-HMM: a HMM Based Likelihood Model for Evolutionary Networks. 2007. Keywords: lateral gene transfer, likelihood, phylogenetic network, phylogeny, reconstruction, statistical model. Note: Poster presented at the eleventh Annual International Conference on Research in Computational Molecular Biology (RECOMB'07), http://www.qb3.org/recomb07/posters/Tuller013043013RECOMB_HMM1.pdf.
2006
10 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.