Rxivist logo

Context-Aware Seeds for Read Mapping

By Hongyi Xin, Mingfu Shao, Carl Kingsford

Posted 20 May 2019
bioRxiv DOI: 10.1101/643072 (published DOI: 10.1186/s13015-020-00172-3)

Motivation: Most modern seed-and-extend NGS read mappers employ a seeding scheme that requires extracting t non-overlapping seeds in each read in order to find all valid mappings under an edit distance threshold of t. As t grows (such as in long reads with high error rate), this seeding scheme forces mappers to use more and shorter seeds, which increases the seed hits (seed frequencies) and therefore reduces the efficiency of mappers. Results: We propose a novel seeding framework, context-aware seeds (CAS). CAS guarantees finding all valid mapping but uses fewer (and longer) seeds, which reduces seed frequencies and increases efficiency of mappers. CAS achieves this improvement by attaching a confidence radius to each seed. We prove that all valid mappings can be found if the sum of confidence radii of seeds are greater than t. CAS generalizes the existing pigeonhole-principle-based seeding scheme in which this confidence radius is implicitly always 1. Moreover, we design an efficient algorithm that constructs the confidence radius database in linear time. We experiment CAS with E. coli genome and show that CAS reduces seed frequencies by up to 25.4% when compared with the state-of-the-art pigeonhole-principle-based seeding algorithm, the Optimal Seed Solver.

Download data

  • Downloaded 311 times
  • Download rankings, all-time:
    • Site-wide: 53,604 out of 92,758
    • In bioinformatics: 5,984 out of 8,685
  • Year to date:
    • Site-wide: 76,670 out of 92,758
  • Since beginning of last month:
    • Site-wide: 79,468 out of 92,758

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide


Sign up for the Rxivist weekly newsletter! (Click here for more details.)