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