Genomic rearrangements play a critical role in evolution and adaptation, altering genome structure and organization, thereby influencing phenotypic traits. Understanding these rearrangements helps identify the mechanisms underlying many genetic diseases and evolutionary processes.

However, even quantifying rearrangements for most genomes that occur in practice is NP-hard under realistic models. While Integer Linear Programming (ILP) is commonly used to address this challenge, it has been recently observed that SAT formulations of the same problems may offer a faster alternative. The project involves converting an existing ILP solution for genomic rearrangement quantification into a SAT-based solution, leveraging SAT solvers' computational efficiency.

Contact Leonard for details.

Despite advances in long-read sequencing technologies, plasmid assembly remains a significant challenge. Current state-of-the-art assemblers often fail to recover plasmids, especially those smaller than 10‎kb. This limitation is concerning because small plasmids often harbor important virulence and antimicrobial resistance genes. Popular assemblers such as Flye, Miniasm, Raven, and Canu show variable success, with recovery rates dropping dramatically for smaller plasmids. Furthermore, when plasmids are recovered, they often appear as multiple copies or are misassembled into the chromosome, highlighting fundamental limitations of current assembly algorithms. We are developing a novel pangenomic approach that uses gene identification within long reads and k-mers over the gene alphabet to improve the quality of the assembly graph. The main tasks for the students will be to analyze the performance of this method and to potentially improve it. ‎ Contact Andreas for details.

<Project description>