2015/03/31 by Nikita Alexeev, Anna Pologova, Max A. Alekseyev · 1 citation
Biochemistry, Genetics and Molecular Biology · Mathematics · #Advanced Combinatorial Mathematics #Breakpoint #Enumeration #Event (particle physics) #Genome #Genome Rearrangement Algorithms #Genomics #Graph #Limits and Structures in Graph Theory #math.CO #q-bio.GN
paper · pdf · doi:10.1089/cmb.2016.0190
published as Journal of Computational Biology 24:2 (2017), 93-105
openalex created_date 2016/06/24 · openalex publication_date 2017/01/03 · arxiv created 2017/02/11 · arxiv updated 2017/02/21 · openalex updated_date 2026/08/05
Genome rearrangements can be modeled as k-breaks, which break a genome at k positions and glue the resulting fragments in a new order. In particular, reversals, translocations, fusions, and fissions are modeled as 2-breaks, and transpositions are modeled as 3-breaks. While k-break rearrangements for k>3 have not been observed in evolution, they are used in cancer genomics to model chromothripsis, a catastrophic event of multiple breakages happening simultaneously in a genome. It is known that the k-break distance between two genomes (i.e., the minimum number of k-breaks required to transform one genome into the other) can be computed in terms of cycle lengths in the breakpoint graph of these genomes. In the current work, we address the combinatorial problem of enumerating genomes at a given k-break distance from a fixed unichromosomal genome. More generally, we enumerate genome pairs, whose breakpoint graph has a given distribution of cycle lengths. We further show how our enumeration can be used for uniform sampling of random genomes at a given k-break distance, and describe its connection to various combinatorial objects such as Bell polynomials.