{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T11:43:59Z","timestamp":1782906239063,"version":"3.54.5"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,2,15]]},"abstract":"<jats:p>Motivation: Alignment of similar whole genomes is often performed using anchors given by the maximal exact matches (MEMs) between their sequences. In spite of significant amount of research on this problem, the computation of MEMs for large genomes remains a challenging problem. The leading current algorithms employ full text indexes, the sparse suffix array giving the best results. Still, their memory requirements are high, the parallelization is not very efficient, and they cannot handle very large genomes.<\/jats:p>\n               <jats:p>Results: We present a new algorithm, efficient computation of MEMs (E-MEM) that does not use full text indexes. Our algorithm uses much less space and is highly amenable to parallelization. It can compute all MEMs of minimum length 100 between the whole human and mouse genomes on a 12 core machine in 10 min and 2 GB of memory; the required memory can be as low as 600 MB. It can run efficiently genomes of any size. Extensive testing and comparison with currently best algorithms is provided.<\/jats:p>\n               <jats:p>Availability and implementation: The source code of E-MEM is freely available at: http:\/\/www.csd.uwo.ca\/\u223cilie\/E-MEM\/<\/jats:p>\n               <jats:p>Contact: ilie@csd.uwo.ca<\/jats:p>\n               <jats:p>Supplementary information: Supplementary Data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu687","type":"journal-article","created":{"date-parts":[[2014,10,18]],"date-time":"2014-10-18T02:34:38Z","timestamp":1413599678000},"page":"509-514","source":"Crossref","is-referenced-by-count":29,"title":["E-MEM: efficient computation of maximal exact matches for very large genomes"],"prefix":"10.1093","volume":"31","author":[{"given":"Nilesh","family":"Khiste","sequence":"first","affiliation":[{"name":"1Department of Computer Science, University of Western Ontario, London, Ontario, N6A 5B7, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lucian","family":"Ilie","sequence":"additional","affiliation":[{"name":"1Department of Computer Science, University of Western Ontario, London, Ontario, N6A 5B7, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2014,10,17]]},"reference":[{"key":"2023020108564361300_btu687-B1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","article-title":"Replacing suffix trees with enhanced suffix arrays","volume":"2","author":"Abouelhoda","year":"2004","journal-title":"J. Discrete Algorithms"},{"key":"2023020108564361300_btu687-B2","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1101\/gr.1960404","article-title":"MAVID: constrained ancestral alignment of multiple sequences","volume":"14","author":"Bray","year":"2004","journal-title":"Genome Res."},{"key":"2023020108564361300_btu687-B3","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1186\/1471-2105-4-66","article-title":"Fast and sensitive multiple alignment of large genomic sequences","volume":"4","author":"Brudno","year":"2003","journal-title":"BMC Bioinformatics"},{"key":"2023020108564361300_btu687-B4","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/j.compbiolchem.2005.04.004","article-title":"GAME: a simple and efficient whole genome alignment method using maximal exact match filtering","volume":"29","author":"Choi","year":"2005","journal-title":"Comput. Biol. Chem"},{"key":"2023020108564361300_btu687-B5","doi-asserted-by":"crossref","first-page":"2369","DOI":"10.1093\/nar\/27.11.2369","article-title":"Alignment of whole genomes","volume":"27","author":"Delcher","year":"1999","journal-title":"Nucleic Acids Res"},{"key":"2023020108564361300_btu687-B6","doi-asserted-by":"crossref","first-page":"2478","DOI":"10.1093\/nar\/30.11.2478","article-title":"Fast algorithms for large-scale genome alignment and comparison","volume":"30","author":"Delcher","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023020108564361300_btu687-B7","first-page":"113","article-title":"Emagen: An efficient approach to multiple whole genome alignment","volume-title":"Proceedings of the second conference on Asia-Pacific bioinformatics","author":"Deogun","year":"2004"},{"key":"2023020108564361300_btu687-B8","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1093\/bioinformatics\/btt706","article-title":"slaMEM: efficient retrieval of maximal exact matches using a sampled LCP array","volume":"30","author":"Fernandes","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020108564361300_btu687-B9","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1109\/SFCS.2000.892127","article-title":"Opportunistic data structures with applications","volume-title":"Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on IEEE","author":"Ferragina","year":"2000"},{"key":"2023020108564361300_btu687-B10","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees and sequences: computer science and computational biology","author":"Gusfield","year":"1997"},{"key":"2023020108564361300_btu687-B11","doi-asserted-by":"crossref","first-page":"S312","DOI":"10.1093\/bioinformatics\/18.suppl_1.S312","article-title":"Efficient multiple genome alignment","volume":"18","author":"H\u00f6hl","year":"2002","journal-title":"Bioinformatics"},{"key":"2023020108564361300_btu687-B12","doi-asserted-by":"crossref","first-page":"2969","DOI":"10.1093\/bioinformatics\/btm422","article-title":"Multiple spaced seeds for homology search","volume":"23","author":"Ilie","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020108564361300_btu687-B13","doi-asserted-by":"crossref","first-page":"2433","DOI":"10.1093\/bioinformatics\/btr368","article-title":"SpEED: fast computation of sensitive spaced seeds","volume":"27","author":"Ilie","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020108564361300_btu687-B14","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/3-540-61332-3_155","article-title":"Sparse suffix trees","volume-title":"Computing and Combinatorics","author":"K\u00e4rkk\u00e4inen","year":"1996"},{"key":"2023020108564361300_btu687-B15","first-page":"656","article-title":"Blatthe blast-like alignment tool","volume":"12","author":"Kent","year":"2002","journal-title":"Genome Res."},{"key":"2023020108564361300_btu687-B16","doi-asserted-by":"crossref","first-page":"1609","DOI":"10.1093\/bioinformatics\/btp275","article-title":"A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays","volume":"25","author":"Khan","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020108564361300_btu687-B17","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1002\/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O","article-title":"Reducing the space requirement of suffix trees","volume":"29","author":"Kurtz","year":"1999","journal-title":"Softw. Practice Exp."},{"key":"2023020108564361300_btu687-B18","doi-asserted-by":"crossref","first-page":"R12","DOI":"10.1186\/gb-2004-5-2-r12","article-title":"Versatile and open software for comparing large genomes","volume":"5","author":"Kurtz","year":"2004","journal-title":"Genome Biol."},{"key":"2023020108564361300_btu687-B19","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1142\/S0219720004000661","article-title":"PatternHunter II: Highly sensitive and fast homology search","volume":"2","author":"Li","year":"2004","journal-title":"J. Bioinformatics Comput. Biol."},{"key":"2023020108564361300_btu687-B20","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1093\/bioinformatics\/18.3.440","article-title":"PatternHunter: faster and more sensitive homology search","volume":"18","author":"Ma","year":"2002","journal-title":"Bioinformatics"},{"key":"2023020108564361300_btu687-B21","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix arrays: a new method for on-line string searches","volume":"22","author":"Manber","year":"1993","journal-title":"Siam J. Comput."},{"key":"2023020108564361300_btu687-B22","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1186\/1471-2105-14-102","article-title":"Mobilomics in saccharomyces cerevisiae strains","volume":"14","author":"Menconi","year":"2013","journal-title":"BMC Bioinformatics"},{"key":"2023020108564361300_btu687-B23","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1216370.1216372","article-title":"Compressed full-text indexes","volume":"39","author":"Navarro","year":"2007","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"2023020108564361300_btu687-B24","article-title":"Chaining algorithms and applications in comparative genomics","volume-title":"Handbook of Computational Molecular Biology","author":"Ohlebusch","year":"2006"},{"key":"2023020108564361300_btu687-B25","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/978-3-642-16321-0_36","article-title":"Computing matching statistics and maximal exact matches on compressed full-text indexes","volume-title":"String Processing and Information Retrieval","author":"Ohlebusch","year":"2010"},{"key":"2023020108564361300_btu687-B26","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1101\/gr.10.4.577","article-title":"Pipmakera web server for aligning two genomic dna sequences","volume":"10","author":"Schwartz","year":"2000","journal-title":"Genome Res."},{"key":"2023020108564361300_btu687-B27","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1093\/bioinformatics\/btt042","article-title":"essaMEM: finding maximal exact matches using enhanced sparse suffix arrays","volume":"29","author":"Vyverman","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020108564361300_btu687-B28","first-page":"1","article-title":"Linear pattern matching algorithms","volume-title":"Switching and Automata Theory, 1973. SWAT\u201908. IEEE Conference Record of 14th Annual Symposium on IEEE","author":"Weiner","year":"1973"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/4\/509\/49011087\/bioinformatics_31_4_509.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/4\/509\/49011087\/bioinformatics_31_4_509.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T20:25:10Z","timestamp":1675283110000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/4\/509\/2748225"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,17]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu687","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,17]]}}}