Bilkent University
Department of Computer Engineering
CS 590/690 SEMINAR
Characterization of structural variation through assembly-to-assembly comparison
Muhammet Rafi Çoktalaş
Master Student
(Supervisor:Assoc.Prof.Can Alkan)
Computer Engineering Department
Bilkent University
Abstract: Motivation: Structural variations (SVs) are genomic differences spanning more than 50 nucleotides that drive evolution and significantly influence human health, underlying conditions such as autism, schizophrenia, and cancer. With the recent availability of high-quality de novo assemblies, SV discovery is shifting from short-read alignment to assembly-to-assembly comparison. However, existing assembly-based tools typically rely on Whole Genome Alignment (WGA), a computationally resource-intensive process that scales poorly to large datasets. Consequently, there is an urgent need forefficient algorithms that can characterize SVs without the overhead of full alignment. Results: We introduce STRiVE, a linearithmic-time algorithm that utilizes genome assembly sketches—rather than whole-genome alignments—to identify insertions, deletions, and inversions. Inspired by optical mapping, STRiVE treats sketches as sparse genomic landmarks to rapidly detect structural discrepancies. We evaluated STRiVE on simulated data based on the human reference (GRCh38) and real data from the Telomere-to-Telomere CHM13 assembly. STRiVE characterizes SVs in less than one minute per chromosome, including preprocessing steps. Our algorithm achieved a precision and recall of over 90%. While performance for insertions and deletions decreased in regions containing segmental duplications, STRiVE maintained robust performance for inversion discovery, with recall remaining above 90% even in complex scenarios in simulated data sets. We also tested STRiVE to characterize large SVs in the CHM13 data set, and STRiVE achieved the strongest overall recovery on the validated benchmark, detecting 12 of 15 insertions, 4 of 5 deletions, and 5 of 6 inversions. Availability: STRiVE is available at https://github.com/BilkentCompGen/strive
DATE: April 13, Monday @ 16:30 Place: EA 502