title: Canonical, stable, general mapping using context schemes.
abstract: BACKGROUND
  Sequence mapping is the cornerstone of modern genomics. However, most existing sequence mapping algorithms are insufficiently general.
  
  
  RESULTS
  We introduce context schemes: a method that allows the unambiguous recognition of a reference base in a query sequence by testing the query for substrings from an algorithmically defined set. Context schemes only map when there is a unique best mapping, and define this criterion uniformly for all reference bases. Mappings under context schemes can also be made stable, so that extension of the query string (e.g. by increasing read length) will not alter the mapping of previously mapped positions. Context schemes are general in several senses. They natively support the detection of arbitrary complex, novel rearrangements relative to the reference. They can scale over orders of magnitude in query sequence length. Finally, they are trivially extensible to more complex reference structures, such as graphs, that incorporate additional variation. We demonstrate empirically the existence of high-performance context schemes, and present efficient context scheme mapping algorithms.
  
  
  METHODS
  The software test framework created for this study is available from https://registry.hub.docker.com/u/adamnovak/sequence-graphs/.
  
  
  BACKGROUND
  anovak@soe.ucsc.edu
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: UC Santa Cruz Genomics Institute, 1156 High Street, Santa Cruz, CA 95064 and.
authors.forename: Adam M
authors.initials: AM
authors.lastname: Novak
authors.affiliation: NYU School of Medicine, 550 First Avenue, New York, NY 10016, USA.
authors.forename: Yohei
authors.initials: Y
authors.lastname: Rosen
authors.affiliation: UC Santa Cruz Genomics Institute, 1156 High Street, Santa Cruz, CA 95064 and.
authors.forename: David
authors.initials: D
authors.lastname: Haussler
authors.affiliation: UC Santa Cruz Genomics Institute, 1156 High Street, Santa Cruz, CA 95064 and.
authors.forename: Benedict
authors.initials: B
authors.lastname: Paten
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D056426:Genetic Loci; D023281:Genomics / Q000379:methods*; D006801:Humans; D008285:Major Histocompatibility Complex / Q000235:genetics; D016415:Sequence Alignment; D012984:Software