Abstract. The dramatic decrease in time and cost for generating genetic sequence data has opened up vast opportunities in molecular systematics, one of which is the ability to decipher the evolutionary history of strains of a species. Under this fine systematic resolution, the standard markers are often too crude to provide a reliable phylogenetic signal. Nevertheless, among prokaryotes, genome dynamics (GD) in the form of horizontal gene transfer (HGT), the transfer of genetic material between organisms not through lineal descent, seem to provide far richer information by affecting both gene order and gene content. The synteny index (SI) between a pair of genomes combines these latter two factors, allowing comparison of genomes with unequal gene content, together with order considerations of their common genes. Although this approach is useful for classifying close relatives, no rigorous statistical modelling for it has been suggested. Such modelling is valuable, as it allows observed measures to be transformed into estimates of time periods during evolution, yielding the additivity of the SI measure. To the best of our knowledge, there is no other additivity proof for other gene order/content measures under HGT. 

Here we provide a first statistical, two-level modeling and analysis, for GD under a very simple operation – the Jump operation. Under this framework, at the higher level, genome evolution is modeled as a random walk in the genome permutation state space. At the lower level, gene neighborhood is modeled as a birth–death–immigration process affected by the genes jumping across the genome. Using this modeling we can infer several neutral characteristics for genomes evolving along a tree and analytically relate the HGT rate and time to the expected SI. 

We applied this model to the new version of the orthology DB EggNOG containing over 4.5K taxa. To the best of our knowledge, this is the largest gene-order-based tree constructed and it overcomes shortcomings found in previous approaches. Constructing a GD-based tree allows toconfirm and contrast findings based on other phylogenetic approaches, as we show. 

Related Papers:

1) Katriel G., Mahanaymi U., Koutschan C., Zeilberger D., Steel M. and  Snir S. 2023. Gene Transfer-based Phylogenetics: Analytical Expressions and Additivity via Birth–Death Theory, Accepted at Systematic Biology. A preliminary version is available at bioarxiv

2) Sevillya, G., D. Doerr, Y. Lerner, J. Stoye, M. Steel, and S. Snir. 2019. Horizontal Gene Transfer Phylogenetics: A Random Walk Approach. Molecular Biology and Evolution (MBE)37:1470–1479.

3) Shifman, A., N. Ninyo, U. Gophna, and S. Snir. 2013. Phylo si: a new genome-wide approach for prokaryotic phylogeny. Nucleic acids research (NAR)42:2391–2404.

Bio: Sagi Snir graduated in Computer Science from the Technion Israel, focusing on analytical, algebraic, maximum likelihood solutions to phylogenetics. After a postdoc in Math and Computer Science depts at UC Berkeley, he returned to the University of Haifa in Israel, where he has established the Bioinformatics program for grad students. He is now a professor of computational evolution at the University of Haifa and the President of the Israeli Society for Bioinformatics and Computational Biology. 

His research combines algorithmic and combinatorial/statistical approaches to problems from evolution with focus on phylogenetic trees and networks. He has developed the Quartet MaxCut algorithm to combine conflicting signals between evolutionary trees and other fundamental results on maximum likelihood of trees and networks. 

His papers have been published in both leading pure theoretical computer science venues and pure evolution venues.