Developing Algorithms for Sequence Alignment to Genomic Interval Maps

Interval maps provide large-scale scale information about genome sequences and allow to resolve long repeats. Interval maps have found many applications in genome assembly including scaffolding. The core problem for applying interval map data is the problem of sequence alignment to interval maps. Nabsys has developed HD-Mapping™, a new technology for producing low-cost high-resolution interval maps. SPAdes, a short read assembler, supports Nabsys restriction maps for scaffolding. Paths from SPAdes scaffolding steps can contain a few large insertions and deletions. But, the existing alignment algorithm is sensitive to large insertions and deletions, which limits the uses of the alignment algorithm. I developed a new algorithm for interval map alignment that supports few large insertions or deletions. Keywords: optical maps, electronic maps, interval maps, restriction maps, sequence alignment