Fast detection of maximal exact matches via fixed sampling of query k-mers and Bloom filtering of index k-mers

Liu, Yuansheng, Zhang, Leo Yu and Li, Jinyan 2019, Fast detection of maximal exact matches via fixed sampling of query k-mers and Bloom filtering of index k-mers, Bioinformatics, doi: 10.1093/bioinformatics/btz273.

Attached Files
Name Description MIMEType Size Downloads

Title Fast detection of maximal exact matches via fixed sampling of query k-mers and Bloom filtering of index k-mers
Author(s) Liu, Yuansheng
Zhang, Leo YuORCID iD for Zhang, Leo Yu orcid.org/0000-0001-9330-2662
Li, Jinyan
Journal name Bioinformatics
Total pages 7
Publisher Oxford University Press
Place of publication Oxford, Eng.
Publication date 2019
ISSN 1367-4811
Summary MotivationDetection of maximal exact matches (MEMs) between two long sequences is a fundamental problem in pairwise reference-query genome comparisons. To efficiently compare larger and larger genomes, reducing the number of indexed k-mers as well as the number of query k-mers has been adopted as a mainstream approach which saves the computational resources by avoiding a significant number of unnecessary matches.ResultsUnder this framework, we proposed a new method to detect all MEMs from a pair of genomes. The method first performs a fixed sampling of k-mers on the query sequence, and add these selected k-mers to a Bloom filter. Then all the k-mers of the reference sequence are tested by the Bloom filter. If a k-mer passes the test, it is inserted into a hash table for indexing. Compared with the existing methods, much less number of query k-mers are generated and much less k-mers are inserted into the index to avoid unnecessary matches, leading to an efficient matching process and memory usage savings. Experiments on large genomes demonstrate that our method is at least 1.8 times faster than the best of the existing algorithms. This performance is mainly attributed to the key novelty of our method that the fixed k-mer sampling must be conducted on the query sequence and the index k-mers are filtered from the reference sequence via a Bloom filter.
Notes In Press
Language eng
DOI 10.1093/bioinformatics/btz273
Indigenous content off
Field of Research 01 Mathematical Sciences
06 Biological Sciences
08 Information and Computing Sciences
HERDC Research category C1 Refereed article in a scholarly journal
Copyright notice ©2019, The Authors
Persistent URL http://hdl.handle.net/10536/DRO/DU:30121170

Connect to link resolver
 
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in TR Web of Science
Scopus Citation Count Cited 0 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 56 Abstract Views, 0 File Downloads  -  Detailed Statistics
Created: Tue, 30 Apr 2019, 15:39:14 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.