MEM-based pangenome indexing for k-mer queries

MEM-based pangenome indexing for k-mer queries | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article MEM-based pangenome indexing for k-mer queries Stephen Hwang, Nathaniel K. Brown, Omar Y. Ahmed, Katharine M. Jenike, and 3 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-5363291/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 01 Mar, 2025 Read the published version in Algorithms for Molecular Biology → Version 1 posted 3 You are reading this latest preprint version Abstract Pangenomes are growing in number and size, thanks to the prevalence of high-quality long-read assemblies. However, current methods for studying sequence composition and conservation within pangenomes have limitations. Methods based on graph pangenomes require a computationally expensive multiple-alignment step, which can leave out some variation. Indexes based on k-mers and de Bruijn graphs are limited to answering questions at a specific substring length k. We present Maximal Exact Match Ordered (MEMO), a pangenome indexing method based on maximal exact matches (MEMs) between sequences. A single MEMO index can handle arbitrary-length queries over pangenomic windows. MEMO enables both queries that test k-mer presence/absence (membership queries) and that count the number of genomes containing k-mers in a window (conservation queries). MEMO's index for a pangenome of 89 human autosomal haplotypes fits in 2.04 GB, 8.8X smaller than a comparable KMC3 index and 11.4X smaller than a PanKmer index. MEMO indexes can be made smaller by sacrificing some counting resolution, with our decile-resolution HPRC index reaching 0.67 GB. MEMO can conduct a conservation query for 31-mers over the human leukocyte antigen locus in 13.89 seconds, 2.5X faster than other approaches. MEMO's small index size, lack of k-mer length dependence, and efficient queries make it a flexible tool for studying and visualizing substring conservation in pangenomes. Pangenomics Comparative genomics Compressed indexing Full Text Additional Declarations Competing interest reported. B.L. is founder of InOrder Labs LLC. Cite Share Download PDF Status: Published Journal Publication published 01 Mar, 2025 Read the published version in Algorithms for Molecular Biology → Version 1 posted Editor assigned by journal 02 Nov, 2024 Submission checks completed at journal 01 Nov, 2024 First submitted to journal 30 Oct, 2024 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-5363291","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":373225536,"identity":"a88aea13-db65-4819-a74c-b7afcc95f61d","order_by":0,"name":"Stephen Hwang","email":"","orcid":"","institution":"XDBio Program, Johns Hopkins University","correspondingAuthor":false,"prefix":"","firstName":"Stephen","middleName":"","lastName":"Hwang","suffix":""},{"id":373225537,"identity":"5b3adf2a-6962-4ee6-8612-7142d7eae784","order_by":1,"name":"Nathaniel K. Brown","email":"","orcid":"","institution":"Department of Computer Science, Johns Hopkins University","correspondingAuthor":false,"prefix":"","firstName":"Nathaniel","middleName":"K.","lastName":"Brown","suffix":""},{"id":373225538,"identity":"c6e849c1-153b-44de-b690-6159a570501a","order_by":2,"name":"Omar Y. Ahmed","email":"","orcid":"","institution":"Department of Computer Science, Johns Hopkins University","correspondingAuthor":false,"prefix":"","firstName":"Omar","middleName":"Y.","lastName":"Ahmed","suffix":""},{"id":373225539,"identity":"22ea1b4c-2332-459b-9e26-8ba2fce31552","order_by":3,"name":"Katharine M. Jenike","email":"","orcid":"","institution":"Department of Computer Science, Johns Hopkins University","correspondingAuthor":false,"prefix":"","firstName":"Katharine","middleName":"M.","lastName":"Jenike","suffix":""},{"id":373225540,"identity":"c4865d41-82fc-4154-83e7-a063382ce745","order_by":4,"name":"Sam Kovaka","email":"","orcid":"","institution":"Department of Computer Science, Johns Hopkins University","correspondingAuthor":false,"prefix":"","firstName":"Sam","middleName":"","lastName":"Kovaka","suffix":""},{"id":373225541,"identity":"5d2e41f0-f046-45a1-9076-d0ce95aa083b","order_by":5,"name":"Michael C. Schatz","email":"","orcid":"","institution":"Department of Computer Science, Johns Hopkins University","correspondingAuthor":false,"prefix":"","firstName":"Michael","middleName":"C.","lastName":"Schatz","suffix":""},{"id":373225542,"identity":"c26b2117-1412-4d31-8d94-1f78a445695f","order_by":6,"name":"Ben Langmead","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA0UlEQVRIiWNgGAWjYBACPigtByKMwcwDBLSwQWlj0rUkNgAJZuK0sJ89/OpGhV16f/8BhuLCNgY5vhsJBLTw5KVZ55xJzp0BVGk8s43BWJKgFoYcM+PcNubcDRJAv/C2MSRuIKiF/w1Qy7/6dAP+A2At9YS1SOQYP85tOJxgwJAA1pJgQFjLGzPmnGPHDWfcSGww5jknYTjzzAP8Wvj5c4w/59RUy/P3Hz5mzFNmI893nIAtYIsgNGObAQODBEHlIMD8AcYg4KJRMApGwSgYqQAA74k9cYXwn9sAAAAASUVORK5CYII=","orcid":"","institution":"Department of Computer Science, Johns Hopkins University","correspondingAuthor":true,"prefix":"","firstName":"Ben","middleName":"","lastName":"Langmead","suffix":""}],"badges":[],"createdAt":"2024-10-30 19:53:21","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-5363291/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-5363291/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1186/s13015-025-00272-y","type":"published","date":"2025-03-01T15:57:38+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":77622850,"identity":"fe0ce884-d6e7-4f3c-a1eb-85c974a8482f","added_by":"auto","created_at":"2025-03-03 16:10:34","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":2768515,"visible":true,"origin":"","legend":"","description":"","filename":"memoamb.pdf","url":"https://assets-eu.researchsquare.com/files/rs-5363291/v1_covered_f6d327e8-5c32-4eb7-97d2-15ee6e65217c.pdf"}],"financialInterests":"Competing interest reported. B.L. is founder of InOrder Labs LLC.","formattedTitle":"MEM-based pangenome indexing for k-mer queries","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"algorithms-for-molecular-biology","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"amob","sideBox":"Learn more about [Algorithms for Molecular Biology](http://almob.biomedcentral.com/)","snPcode":"13015","submissionUrl":"https://submission.nature.com/new-submission/13015/3","title":"Algorithms for Molecular Biology","twitterHandle":"@BioMedCentral","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"BMC/SO AJ","inReviewEnabled":true,"inReviewRevisionsEnabled":true},"keywords":"Pangenomics, Comparative genomics, Compressed indexing","lastPublishedDoi":"10.21203/rs.3.rs-5363291/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-5363291/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Pangenomes are growing in number and size, thanks to the prevalence of high-quality long-read assemblies. However, current methods for studying sequence composition and conservation within pangenomes have limitations. Methods based on graph pangenomes require a computationally expensive multiple-alignment step, which can leave out some variation. Indexes based on k-mers and de Bruijn graphs are limited to answering questions at a specific substring length k. We present Maximal Exact Match Ordered (MEMO), a pangenome indexing method based on maximal exact matches (MEMs) between sequences. A single MEMO index can handle arbitrary-length queries over pangenomic windows. MEMO enables both queries that test k-mer presence/absence (membership queries) and that count the number of genomes containing k-mers in a window (conservation queries). MEMO's index for a pangenome of 89 human autosomal haplotypes fits in 2.04 GB, 8.8X smaller than a comparable KMC3 index and 11.4X smaller than a PanKmer index. MEMO indexes can be made smaller by sacrificing some counting resolution, with our decile-resolution HPRC index reaching 0.67 GB. MEMO can conduct a conservation query for 31-mers over the human leukocyte antigen locus in 13.89 seconds, 2.5X faster than other approaches. MEMO's small index size, lack of k-mer length dependence, and efficient queries make it a flexible tool for studying and visualizing substring conservation in pangenomes.","manuscriptTitle":"MEM-based pangenome indexing for k-mer queries","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-11-13 05:24:38","doi":"10.21203/rs.3.rs-5363291/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"editorAssigned","content":"","date":"2024-11-02T09:02:24+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-11-01T09:22:46+00:00","index":"","fulltext":""},{"type":"submitted","content":"Algorithms for Molecular Biology","date":"2024-10-30T19:44:48+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"algorithms-for-molecular-biology","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"amob","sideBox":"Learn more about [Algorithms for Molecular Biology](http://almob.biomedcentral.com/)","snPcode":"13015","submissionUrl":"https://submission.nature.com/new-submission/13015/3","title":"Algorithms for Molecular Biology","twitterHandle":"@BioMedCentral","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"BMC/SO AJ","inReviewEnabled":true,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"63e4c65e-7b56-44df-b662-0c0cfa5dd4d3","owner":[],"postedDate":"November 13th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2025-03-03T16:07:14+00:00","versionOfRecord":{"articleIdentity":"rs-5363291","link":"https://doi.org/10.1186/s13015-025-00272-y","journal":{"identity":"algorithms-for-molecular-biology","isVorOnly":false,"title":"Algorithms for Molecular Biology"},"publishedOn":"2025-03-01 15:57:38","publishedOnDateReadable":"March 1st, 2025"},"versionCreatedAt":"2024-11-13 05:24:38","video":"","vorDoi":"10.1186/s13015-025-00272-y","vorDoiUrl":"https://doi.org/10.1186/s13015-025-00272-y","workflowStages":[]},"version":"v1","identity":"rs-5363291","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-5363291","identity":"rs-5363291","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}