On Deriving Synteny Blocks by Compacting Elements

Genomic rearrangements are major drivers of evolution and genetic disease. Studying rearrangements requires segmenting genomes of interest into conserved regions, called synteny blocks, that highlight structural differences between genomes. Synteny blocks are typically defined from annotated genes or derived as a by-product of whole-genome alignment. However, as these procedures are heuristic and do not explicitly model rearrangements, they can obscure real variation, create false similarities, and affect phylogenetic inference. We present a formal framework for deriving synteny blocks by partitioning genomic elements into blocks that do not contain breakpoints. A breakpoint is defined between a pair of genomes as an adjacency of shared elements that occurs in one genome but not in the other. Synteny blocks are therefore not allowed to span such boundaries, ensuring that rearrangements are not obscured. The framework is fully agnostic to the type of genomic element and applies to any genome representation expressed as sequences of elements, such as nonoverlapping alignments, exact matches (MUMs/MEMs), k-mers, unitigs, or minimizers. We formalize two optimization problems: minimizing the total genome length after replacement by synteny blocks (the Minimum-Length Synteny Block Problem) and minimizing the number of distinct blocks (the Minimum-Size Synteny Block Problem). We show that both problems are NP-hard in general. However, when blocks are required to be collinear and to contain a shared element, we provide a linear-time algorithm with respect to the number of input elements that simultaneously minimizes both objectives. The resulting method is simple, efficient, and produces large synteny blocks without obscuring rearrangements.