The ability to estimate the evolutionary distance between extant genomes plays a crucial role in many phylogenomic studies. Often such estimation is based on the parsimony assumption, implying that the distance between two genomes can be estimated as the minimal number of genome rearrangements required to transform one genome into the other. However, in reality the parsimony assumption may not always hold, emphasizing the need for estimation that does not rely on the minimal number of genome rearrangements. While there exists a method for such estimation, it however assumes that genomes can be broken by rearrangements equally likely at any position in the course of evolution. This assumption, known as the random breakage model, has recently been refuted in favor of the more rigorous fragile breakage model postulating that only certain “fragile” genomic regions are prone to rearrangements. We propose a new method for estimating the evolutionary distance between two genomes with high accuracy under the fragile breakage mode.

---

Combinatorial Scoring of Phylogenetic Networks

Project lead: Nikita Alexeev

Construction of phylogenetic trees and networks for extant species from their characters represents one of the key problems in phylogenomics. While solution to this problem is not always uniquely defined and there exist multiple methods for tree/network construction, it becomes important to measure how well constructed networks capture the given character relationship across the species.
In the current study, we propose a novel method for measuring the specificity of a given phylogenetic network in terms of the total number of distributions of character states at the leaves that the network may impose. While for binary phylogenetic trees, this number has an exact formula and depends only on the number of leaves and character states but not on the tree topology, the situation is much more complicated for non-binary trees or networks. Nevertheless, we develop an algorithm for combinatorial enumeration of such distributions, which is applicable for arbitrary trees and networks under some reasonable assumptions.

Sage Code: cactus_network
Publications:

• N. Alexeev and M. A. Alekseyev. “Combinatorial Scoring of Phylogenetic Networks”. Lecture Notes in Computer Science 9797 (2016), 560–572. doi:10.1007/978-3-319-42634-1_45 arXiv:1602.02841