75 15

A performant bridge between fixed-size and variable-size seeding

Title
A performant bridge between fixed-size and variable-size seeding
Author
KUTZNER, ARNE HOLGER
Keywords
High-throughput sequence alignment; Minimizer; MEM; SMEM; FMD-index
Issue Date
2020-07
Publisher
BMC
Citation
BMC BIOINFORMATICS, v. 21, no. 1, article no. 328
Abstract
Background Seeding is usually the initial step of high-throughput sequence aligners. Two popular seeding strategies are fixed-size seeding (k-mers, minimizers) and variable-size seeding (MEMs, SMEMs, maximal spanning seeds). The former strategy supports fast seed computation, while the latter one benefits from a high seed uniqueness. Algorithmic bridges between instances of both seeding strategies are of interest for combining their respective advantages.Results We introduce an efficient strategy for computing MEMs out of fixed-size seeds (k-mers or minimizers). In contrast to previously proposed extend-purge strategies, our merge-extend strategy prevents the creation and filtering of duplicate MEMs. Further, we describe techniques for extracting SMEMs or maximal spanning seeds out of MEMs. A comprehensive benchmarking shows the applicability, strengths, shortcomings and computational requirements of all discussed seeding techniques. Additionally, we report the effects of seed occurrence filters in the context of these techniques.Aside from our novel algorithmic approaches, we analyze hierarchies within fixed-size and variable-size seeding along with a mapping between instances of both seeding strategies.Conclusion Benchmarking shows that our proposed merge-extend strategy for MEM computation outperforms previous extend-purge strategies in the context of PacBio reads. The observed superiority grows with increasing read size and read quality. Further, the presented filters for extracting SMEMs or maximal spanning seeds out of MEMs outperform FMD-index based extension techniques. All code used for benchmarking is available via GitHub at https://github.com/ITBE-Lab/seed-evaluation.
URI
https://bmcbioinformatics.biomedcentral.com/articles/10.1186/s12859-020-03642-yhttps://repository.hanyang.ac.kr/handle/20.500.11754/169269
ISSN
1471-2105
DOI
10.1186/s12859-020-03642-y
Appears in Collections:
COLLEGE OF ENGINEERING[S](공과대학) > INFORMATION SYSTEMS(정보시스템학과) > Articles
Files in This Item:
A performant bridge between fixed-size and variable-size seeding.pdfDownload
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE