This preprint is under consideration at Algorithms for Molecular Biology. A preprint is a preliminary version of a manuscript that has not completed peer review at a journal. Research Square does not conduct peer review prior to posting preprints. The posting of a preprint on this server should not be interpreted as an endorsement of its validity or suitability for dissemination as established information or for guiding clinical practice.
Learn more about In Review
Research
Context-Aware Seeds for Read Mapping
Carl Kingsford
Carnegie Mellon University
Corresponding Author
ORCiD: https://orcid.org/0000-0002-0118-5516
License:
This work is licensed under a CC BY 4.0 License. Read Full License
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 mappings 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 in the reference. 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 20.3% when compared with the state-of-the-art pigeonhole-principle-based seeding algorithm, the Optimal Seed Solver.
Keywords
Read mapping, Seeds, Error tolerance, Seed and extend
Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
Figure 11
Figure 12
Figure 13
Figure 14
Figure 15
Due to technical limitations, full-text HTML conversion of this manuscript could not be completed. However, the manuscript can be downloaded and accessed as a PDF.
Badges
Prescreen
This manuscript passed our Prescreen assessment
Complete author information
Appropriate declaration statements
Potential risks to human health
Prescreen
Peer Review Timeline
CURRENT STATUS: Under Review
Version 1
Posted 18 Dec, 2019
No community comments so far
Editorial decision: Major revision
On 24 Jan, 2020
Review #2 received
Received 23 Jan, 2020
Review #1 received
Received 12 Jan, 2020
Reviewer #2 agreed
On 23 Dec, 2019
Reviewer #1 agreed
On 20 Dec, 2019
Reviewers invited
Invitations sent on 18 Dec, 2019
Submission checks complete
On 14 Dec, 2019
Editor invited
On 14 Dec, 2019
Editor assigned
On 14 Dec, 2019
First submitted
On 13 Dec, 2019
Metrics
Comments: 0
PDF Downloads: ...
HTML Views: ...
Learn more about our company.
This preprint is under consideration at Algorithms for Molecular Biology. A preprint is a preliminary version of a manuscript that has not completed peer review at a journal. Research Square does not conduct peer review prior to posting preprints. The posting of a preprint on this server should not be interpreted as an endorsement of its validity or suitability for dissemination as established information or for guiding clinical practice.
Learn more about In Review
Research
Context-Aware Seeds for Read Mapping
Carl Kingsford
Carnegie Mellon University
Corresponding Author
ORCiD: https://orcid.org/0000-0002-0118-5516
Badges
Prescreen
This manuscript passed our Prescreen assessment
Complete author information
Appropriate declaration statements
Potential risks to human health
Prescreen
Peer Review Timeline
CURRENT STATUS: Under Review
Version 1
Posted 18 Dec, 2019
No community comments so far
Editorial decision: Major revision
On 24 Jan, 2020
Review #2 received
Received 23 Jan, 2020
Review #1 received
Received 12 Jan, 2020
Reviewer #2 agreed
On 23 Dec, 2019
Reviewer #1 agreed
On 20 Dec, 2019
Reviewers invited
Invitations sent on 18 Dec, 2019
Submission checks complete
On 14 Dec, 2019
Editor invited
On 14 Dec, 2019
Editor assigned
On 14 Dec, 2019
First submitted
On 13 Dec, 2019
Metrics
Comments: 0
PDF Downloads: ...
HTML Views: ...
License:
This work is licensed under a CC BY 4.0 License. Read Full License
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 mappings 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 in the reference. 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 20.3% when compared with the state-of-the-art pigeonhole-principle-based seeding algorithm, the Optimal Seed Solver.
Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
Figure 11
Figure 12
Figure 13
Figure 14
Figure 15
Due to technical limitations, full-text HTML conversion of this manuscript could not be completed. However, the manuscript can be downloaded and accessed as a PDF.