OPTIMA: Sensitive and Accurate Whole-Genome Alignment of Error-prone Genomic Maps by Combinatorial Indexing and Technology-Agnostic Statistical Analysis

Background: Resolution of complex repeat structures and rearrangements in the assembly and analysis of largeeukaryotic genomes is often aided by a combination of high-throughput sequencing and genome-mappingtechnologies (for example, optical restriction mapping). In particular, mapping technologies can generate sparsemaps of large DNA fragments (150 kilo base pairs (kbp) to 2Mbp) and thus provide a unique source of information fordisambiguating complex rearrangements in cancer genomes. Despite their utility, combining high-throughputsequencing and mapping technologies has been challenging because of the lack of efficient and sensitivemap-alignment algorithms for robustly aligning error-prone maps to sequences.Results: We introduce a novel seed-and-extend glocal (short for global-local) alignment method, OPTIMA (and asliding-window extension for overlap alignment, OPTIMA-Overlap), which is the first to create indexes forcontinuous-valued mapping data while accounting for mapping errors. We also present a novel statistical model,agnostic with respect to technology-dependent error rates, for conservatively evaluating the significance ofalignments without relying on expensive permutation-based tests.Conclusions: We show that OPTIMA and OPTIMA-Overlap outperform other state-of-the-art approaches (1.6 - 2times more sensitive) and are more efficient (170 - 200 %) and precise in their alignments (nearly 99% precision).These advantages are independent of the quality of the data, suggesting that our indexing approach and statisticalevaluation are robust, provide improved sensitivity and guarantee high precision.