




Sagi Snir and
Tamir Tuller. The NETHMM approach: Phylogenetic Network Inference by Combining Maximum Likelihood and Hidden Markov Models. In JBCB, Vol. 7(4):625644, 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/SnirNETHMMJBCB2009.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 NETHMM, 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 NETHMM is its ability to infer partial HGT as well as complete HGT. We describe the properties of the NETHMM, 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 (NETHMM) to a given dataset. Using NETHMM, 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."








Sagi Snir and
Tamir Tuller. Novel Phylogenetic Network Inference by Combining Maximum Likelihood and Hidden Markov Models. In WABI08, Vol. 5251:354368 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/9783540873617_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 NETHMM. 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 NETHMM is its ability to infer partial HGT as well as complete HGT. We describe the properties of the NETHMM, 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 (NETHMM) to a given data set. Using NETHMM 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 SpringerVerlag Berlin Heidelberg."



Hadas Birin,
Zohar GalOr,
Isaac Elias and
Tamir Tuller. Inferring horizontal transfers in the presence of rearrangements by the minimum evolution criterion. In BIO, Vol. 24(6):826832, 2008. Note: http://dx.doi.org/10.1093/bioinformatics/btn024.
Toggle abstract
"Motivation: The evolution of viruses is very rapid and in addition to local point mutations (insertion, deletion, substitution) it also includes frequent recombinations, genome rearrangements and horizontal transfer of genetic materials (HGTS). Evolutionary analysis of viral sequences is therefore a complicated matter for two main reasons: First, due to HGTs and recombinations, the right model of evolution is a network and not a tree. Second, due to genome rearrangements, an alignment of the input sequences is not guaranteed. These facts encourage developing methods for inferring phylogenetic networks that do not require aligned sequences as input. Results: In this work, we present the first computational approach which deals with both genome rearrangements and horizontal gene transfers and does not require a multiple alignment as input. We formalize a new set of computational problems which involve analyzing such complex models of evolution. We investigate their computational complexity, and devise algorithms for solving them. Moreover, we demonstrate the viability of our methods on several synthetic datasets as well as four biological datasets. © The Author 2008. Published by Oxford University Press. All rights reserved."










Guohua Jin,
Luay Nakhleh,
Sagi Snir and
Tamir Tuller. A New Lineartime Heuristic Algorithm for Computing the Parsimony Score of Phylogenetic Networks: Theoretical Bounds and Empirical Performance. In ISBRA07, Vol. 4463:6172 of LNCS, springer, 2007. Keywords: approximation, heuristic, parsimony, phylogenetic network, phylogeny, Program Nepal. Note: http://www.cs.rice.edu/~nakhleh/Papers/isbra07.pdf.





Hadas Birin,
Zohar GalOr,
Isaac Elias and
Tamir Tuller. Inferring Models of Rearrangements, Recombinations, and Horizontal Transfers by the Minimum Evolution Criterion. In WABI07, Vol. 4645:111123 of LNCS, springer, 2007. Keywords: explicit network, from sequences, phylogenetic network, phylogeny, reconstruction. Note: http://safrabio.cs.tau.ac.il/download/Papers/Birin_et_al.pdf.






Guohua Jin,
Luay Nakhleh,
Sagi Snir and
Tamir Tuller. Maximum Likelihood of Phylogenetic Networks. In BIO, Vol. 22(21):26042611, 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/SuppML.pdf.



