Our research is focused on mathematical and algorithmic solutions to problems in bioinformatics, in particular in the field ofevolution.The tools we use are from fields such as combinatorial optimization, statistics and probability, mathematics, and information theory. Our research is characterized by ample collaborations with researchers from broad disciplines under the general framework of a systematic analysis of evolutionary processes aiming at finding biologically significant patterns. Below are the main field we focus at:
Phylogenetics, the reconstruction of the evolutionary history of a group of species, is increasingly integrated into modern biological areas such as preventive medicine and epidemiology. Understanding the biological mechanisms underlying the observed evolution of pathogen species is crucial for devising effective control strategies for important human, animal and plant diseases. Moreover, in light of the high mutational and speciation rates among RNA viruses, extremely accurate modeling and reconstruction is called for. Maximum Likelihood (ML) is currently considered as the most accurate phylogenetic method. In past works I developed analytical solutions to ML reconstruction. The novelty of that approach was application of algebraic geometry tools for obtaining the solution. These works have since sparked a wave of interest in the field, in particular at UC Berkeley where I later took on a position as a postdoctoral research fellow.
Another field I am pursuing is supertree reconstruction that is used for large scale phylogenetic reconstruction. Here, we developed an extremely fast method that is inspired by ideas of finding a maximum cut in a weighted graph by means of semidefinite programming (SDP). The method is used by leading labs in the world and has yielded several publications, both practical and theoretical.
Horizontal gene transfer (HGT), the passage of genetic material between genetically distant organisms, is a significant factor in microbial evolution, driving the diversification and speciation of microorganisms, especially pathogens. HGT plays a role in the emergence of novel human diseases, as well as promoting the spread of antibiotic resistance in bacteria species. The unexpectedly high frequency of HGT among prokaryotes made it a topical area in microbiology and medical research. Our research of HGT proceeds along seemingly unrelated tracks. In the first, the phylogenetic track, we have formulated several rigorous frameworks to detect and analyze HGT. These works were the first to model realistically HGT. We formulated both combinatorial and statistical models for the HGT phenomenon.
On a second, the sequence based track, we seek for intrinsic clues for HGT in the organism genomes. The advantage here is the speed of the methods and the alleviation of tasks such as sequence alignment or phylogenetic reconstruction. The method is able to trace HGT events in a community of organisms.
Sequence alignment - the grouping of homologous bases into one column - is fundamental to almost any task in comparative genomics. This translates to positing gaps in the genomic sequences to account for events of insertions and deletions (indels). The interrelationship between sequence alignment and phylogenetic reconstruction has drawn substantial attention recently. We have developed a combinatorial (as opposed to statistical) approach based on indel history. The novelty of this approach is the distinguishing between insertions and deletions and augmenting the analysis a dimension of "depth" extending it from the sequence space to the phylogenetic space.
S. Snir and R. Yuster. Reconstructing approximate phylogenetic trees from quartet samples.ACMSIAM Symposium on Discrete Algorithms (SODA), 2010. (Link)
B. Chor, M. Hendy and S. Snir. Maximum Likelihood Jukes-Cantor Triplets: Analytic Solutions. Molecular Biology and Evolution (MBE), 23(3): 626-632, 2006. (Link)
B. Chor, A. Khetan and S. Snir. Maximum Likelihood on Four Taxa Phylogenetic Trees: Analytic Solutions. Proceedings of the Seventh annual International Conference on Computational Molecular Biology (RECOMB), pages 76-83, 2003. (Link)
S. Snir and L. Pachter. Phylogenetic Profiling of Insertions and Deletions in Vertebrate Genomes. Proceedings of the tenth annual International Conference on Computational Molecular Biology (RECOMB). Lecture Notes in Computer Science 3909: 265-280. 2006. (Link)
G. Jin, L. Nakhleh, S. Snir, and T. Tuller. Inferring Phylogenetic Networks by the Maximum Parsimony Criterion: A Case Study. Molecular Biology and Evolution (MBE), 24(1): 324-337, 2007. All authors contributed equally. (Link)
S. Snir and S. Rao. QuartetsMaxCut: A Divide and Conquer Quartets Algorithm. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB). (Link)
M. Hendy and S. Snir. Hadamard Conjugation for the Kimura 3ST Model: Combinatorial Proof using Path-Sets. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), 5(3): 461-471, 2008. (Link)
S. Moran and S. Snir. Convex Recolorings of Phylogenetic Trees: Definitions, Hardness Results and Algorithms. Journal of Computer and System Sciences (JCSS), 74(5): 850-869, 2008. (Link)
Gronau, S. Moran and S. Snir. Fast and Reliable Reconstruction of Phylogenetic Trees with Very Short Branches. ACM-SIAM Symposium on Discrete Algorithms (SODA), 379-388, 2008. (Link)
B. Chor and S. Snir. Molecular Clock Forks: Symbolic Mathematical Analysis. Mathematical Biosciences, 208(2): 347-58, 2007.