title: OPTIMA: sensitive and accurate whole-genome alignment of error-prone genomic maps by combinatorial indexing and technology-agnostic statistical analysis.
abstract: BACKGROUND
  Resolution of complex repeat structures and rearrangements in the assembly and analysis of large eukaryotic genomes is often aided by a combination of high-throughput sequencing and genome-mapping technologies (for example, optical restriction mapping). In particular, mapping technologies can generate sparse maps of large DNA fragments (150 kilo base pairs (kbp) to 2 Mbp) and thus provide a unique source of information for disambiguating complex rearrangements in cancer genomes. Despite their utility, combining high-throughput sequencing and mapping technologies has been challenging because of the lack of efficient and sensitive map-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 a sliding-window extension for overlap alignment, OPTIMA-Overlap), which is the first to create indexes for continuous-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 of alignments without relying on expensive permutation-based tests.
  
  
  CONCLUSIONS
  We show that OPTIMA and OPTIMA-Overlap outperform other state-of-the-art approaches (1.6-2 times 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 statistical evaluation are robust, provide improved sensitivity and guarantee high precision.
authors.affiliation: Computational and Systems Biology, Genome Institute of Singapore, 60 Biopolis Street, Singapore, 138672 Singapore.
authors.forename: Davide
authors.initials: D
authors.lastname: Verzotto
authors.affiliation: Cancer Therapeutics and Stratified Oncology, Genome Institute of Singapore, 60 Biopolis Street, Singapore, 138672 Singapore.
authors.forename: Audrey S
authors.initials: AS
authors.lastname: M Teo
authors.affiliation: Cancer Therapeutics and Stratified Oncology, Genome Institute of Singapore, 60 Biopolis Street, Singapore, 138672 Singapore.
authors.forename: Axel M
authors.initials: AM
authors.lastname: Hillmer
authors.affiliation: Computational and Systems Biology, Genome Institute of Singapore, 60 Biopolis Street, Singapore, 138672 Singapore.
authors.forename: Niranjan
authors.initials: N
authors.lastname: Nagarajan
mesh_terms: D000465:Algorithms; D000818:Animals; D002874:Chromosome Mapping / Q000379:methods*; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D004331:Drosophila melanogaster / Q000235:genetics; D023281:Genomics / Q000379:methods*; D059014:High-Throughput Nucleotide Sequencing; D006801:Humans; D015203:Reproducibility of Results; D016415:Sequence Alignment / Q000379:methods*
keywords: Genomic mapping; Glocal alignment; Map-to-sequence alignment; Optical mapping; Overlap alignment