{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T01:22:43Z","timestamp":1775611363726,"version":"3.50.1"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,5,23]],"date-time":"2020-05-23T00:00:00Z","timestamp":1590192000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,5,23]],"date-time":"2020-05-23T00:00:00Z","timestamp":1590192000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000936","name":"Gordon and Betty Moore Foundation","doi-asserted-by":"publisher","award":["GBMF4554"],"award-info":[{"award-number":["GBMF4554"]}],"id":[{"id":"10.13039\/100000936","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"crossref","award":["R01GM122935"],"award-info":[{"award-number":["R01GM122935"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1319998"],"award-info":[{"award-number":["CCF-1319998"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010319","name":"Shurl and Kay Curci Foundation","doi-asserted-by":"publisher","award":["4100070287"],"award-info":[{"award-number":["4100070287"]}],"id":[{"id":"10.13039\/100010319","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>\n                      Most modern seed-and-extend NGS read mappers employ a seeding scheme that requires extracting\n                      <jats:italic>t<\/jats:italic>\n                      non-overlapping seeds in each read in order to find all valid mappings under an edit distance threshold of\n                      <jats:italic>t<\/jats:italic>\n                      . As\n                      <jats:italic>t<\/jats:italic>\n                      grows, this seeding scheme forces mappers to use more and shorter seeds, which increases the seed hits\u00a0(seed frequencies) and therefore reduces the efficiency of mappers.\n                    <\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>\n                      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\n                      <jats:italic>t<\/jats:italic>\n                      . 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\n                      <jats:italic>E.\u00a0coli<\/jats:italic>\n                      genome and show that CAS significantly reduces seed frequencies when compared with the state-of-the-art pigeonhole-principle-based seeding algorithm, the Optimal Seed Solver.\n                    <\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability<\/jats:title>\n                    <jats:p>\n                      <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/Kingsford-Group\/CAS_code\">https:\/\/github.com\/Kingsford-Group\/CAS_code<\/jats:ext-link>\n                    <\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s13015-020-00172-3","type":"journal-article","created":{"date-parts":[[2020,5,23]],"date-time":"2020-05-23T03:02:53Z","timestamp":1590202973000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Context-aware seeds for read mapping"],"prefix":"10.1186","volume":"15","author":[{"given":"Hongyi","family":"Xin","sequence":"first","affiliation":[]},{"given":"Mingfu","family":"Shao","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0118-5516","authenticated-orcid":false,"given":"Carl","family":"Kingsford","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,5,23]]},"reference":[{"issue":"4","key":"172_CR1","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/nmeth.1923","volume":"9","author":"B Langmead","year":"2012","unstructured":"Langmead B, Salzberg SL. Fast gapped-read alignment with Bowtie 2. Nature Methods. 2012;9(4):357.","journal-title":"Nature Methods"},{"key":"172_CR2","unstructured":"Li H. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. 2013. arXiv:1303.3997."},{"issue":"1","key":"172_CR3","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1093\/bioinformatics\/bts635","volume":"29","author":"A Dobin","year":"2013","unstructured":"Dobin A, Davis CA, Schlesinger F, Drenkow J, Zaleski C, Jha S, Batut P, Chaisson M, Gingeras TR. STAR: ultrafast universal RNA-seq aligner. Bioinformatics. 2013;29(1):15\u201321.","journal-title":"Bioinformatics"},{"key":"172_CR4","first-page":"13","volume-title":"Accelerating read mapping with FastHASH","author":"H Xin","year":"2013","unstructured":"Xin H, Lee D, Hormozdiari F, Yedkar S, Mutlu O, Alkan C. Accelerating read mapping with FastHASH, vol. 14. London: BioMed Central; 2013. p. 13."},{"issue":"3","key":"172_CR5","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1101\/gr.113985.110","volume":"21","author":"SM Kie\u0142basa","year":"2011","unstructured":"Kie\u0142basa SM, Wan R, Sato K, Horton P, Frith MC. Adaptive seeds tame genomic sequence comparison. Genome Res. 2011;21(3):487\u201393.","journal-title":"Genome Res"},{"issue":"4","key":"172_CR6","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1109\/TCBB.2015.2465900","volume":"13","author":"NH Tran","year":"2016","unstructured":"Tran NH, Chen X. AMAS: optimizing the partition and filtration of adaptive seeds to speed up read mapping. IEEE\/ACM Transact Comput Biol Bioinf. 2016;13(4):623\u201333.","journal-title":"IEEE\/ACM Transact Comput Biol Bioinf"},{"issue":"2","key":"172_CR7","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"GM Landau","year":"1989","unstructured":"Landau GM, Vishkin U. Fast parallel and serial approximate string matching. J Algorith. 1989;10(2):157\u201369.","journal-title":"J Algorith"},{"issue":"11","key":"172_CR8","doi-asserted-by":"crossref","first-page":"1632","DOI":"10.1093\/bioinformatics\/btv670","volume":"32","author":"H Xin","year":"2015","unstructured":"Xin H, Nahar S, Zhu R, Emmons J, Pekhimenko G, Kingsford C, Alkan C, Mutlu O. Optimal seed solver: optimizing seed selection in read mapping. Bioinformatics. 2015;32(11):1632\u201342.","journal-title":"Bioinformatics"},{"key":"172_CR9","doi-asserted-by":"crossref","first-page":"100","DOI":"10.12688\/f1000research.10571.2","volume":"6","author":"JL Weirather","year":"2017","unstructured":"Weirather JL, de Cesare M, Wang Y, Piazza P, Sebastiano V, Wang X-J, Buck D, Au KF. Comprehensive comparison of pacific biosciences and oxford nanopore technologies and their applications to transcriptome analysis. F1000 Research. 2017;6:100.","journal-title":"F1000 Research"},{"issue":"17","key":"172_CR10","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1093\/bioinformatics\/btw463","volume":"32","author":"E Haghshenas","year":"2016","unstructured":"Haghshenas E, Hach F, Sahinalp SC, Chauve C. Colormap: correcting long reads by mapping short reads. Bioinformatics. 2016;32(17):545\u201351.","journal-title":"Bioinformatics"},{"issue":"1","key":"172_CR11","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1093\/bioinformatics\/bty544","volume":"35","author":"E Haghshenas","year":"2018","unstructured":"Haghshenas E, Sahinalp SC, Hach F. lordFAST: sensitive and fast alignment search tool for long noisy read sequencing data. Bioinformatics. 2018;35(1):20\u20137.","journal-title":"Bioinformatics"},{"key":"172_CR12","doi-asserted-by":"crossref","unstructured":"Jain C, Dilthey A, Koren S, Aluru S, Phillippy AM. A fast approximate algorithm for mapping long reads to large reference databases. In: International Conference on Research in Computational Molecular Biology, pp. 66\u201381; 2017. Springer.","DOI":"10.1007\/978-3-319-56970-3_5"},{"issue":"7","key":"172_CR13","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1038\/nchem.2266","volume":"7","author":"JS Wang","year":"2015","unstructured":"Wang JS, Zhang DY. Simulation-guided DNA probe design for consistently ultraspecific hybridization. Nat Chem. 2015;7(7):545.","journal-title":"Nat Chem"},{"issue":"2","key":"172_CR14","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1111\/j.1462-2920.2011.02559.x","volume":"14","author":"E Dugat-Bony","year":"2012","unstructured":"Dugat-Bony E, Peyretaillade E, Parisot N, Biderre-Petit C, Jaziri F, Hill D, Rimour S, Peyret P. Detecting unknown sequences with DNA microarrays: explorative probe design strategies. Environ Microbiol. 2012;14(2):356\u201371.","journal-title":"Environ Microbiol"},{"issue":"2","key":"172_CR15","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1093\/nar\/30.2.e5","volume":"30","author":"Q Li","year":"2002","unstructured":"Li Q, Luan G, Guo Q, Liang J. A new class of homogeneous nucleic acid probes based on specific displacement hybridization. Nucleic Acids Res. 2002;30(2):5.","journal-title":"Nucleic Acids Res"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-00172-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-020-00172-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-00172-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,22]],"date-time":"2021-05-22T19:06:12Z","timestamp":1621710372000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-020-00172-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,23]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["172"],"URL":"https:\/\/doi.org\/10.1186\/s13015-020-00172-3","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.2.19241\/v1","asserted-by":"object"},{"id-type":"doi","id":"10.1101\/643072","asserted-by":"object"}]},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,23]]},"assertion":[{"value":"13 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"C.K. is co-founder of Ocean Genomics, Inc.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"10"}}