copMEM2: robust and scalable maximum exact match finding.
basic_science · Level V
Where this comes from
- Record sourced from PubMed, PMID 37171886.
- Also identified by DOI 10.1093/bioinformatics/btad313 and PMC identifier 10209524.
- Licence recorded as CC BY.
- The licence permits redistribution, so the abstract is shown in full and the full text is available from the publisher.
Abstract
Finding Maximum Exact Matches, i.e. matches between two strings that cannot be further extended to the left or right, is a classic string problem with applications in genome-to-genome comparisons. The existing tools rarely explicitly address the problem of MEM finding for a pair of very similar genomes, which may be computationally challenging. We present copMEM2, a multithreaded implementation of its predecessor. Together with a few optimizations, including a carefully built predecessor query data structure and sort procedure selection, and taking care for highly similar data, copMEM2 allows to compute all MEMs of minimum length 50 between the human and mouse genomes in 59 s, using 10.40 GB of RAM and 12 threads, being at least a few times faster than its main contenders. On a pair of human genomes, hg18 and hg19, the results are 324 s and 16.57 GB, respectively. copMEM2 is available at https://github.com/wbieniec/copmem2.
Medical subject headings
- Algorithms
- Software