Accurate high throughput alignment via line sweep-based seed processing

Markus Schmidt, Klaus Heese, Arne Kutzner

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Accurate and fast aligners are required to handle the steadily increasing volume of sequencing data. Here we present an approach allowing performant alignments of short reads (Illumina) as well as long reads (Pacific Bioscience, Ultralong Oxford Nanopore), while achieving high accuracy, based on a universal three-stage scheme. It is also suitable for the discovery of insertions and deletions that originate from structural variants. We comprehensively compare our approach to other state-of-the-art aligners in order to confirm its performance with respect to accuracy and runtime. As part of our algorithmic scheme, we introduce two line sweep-based techniques called “strip of consideration” and “seed harmonization”. These techniques represent a replacement for chaining and do not rely on any specially tailored data structures. Additionally, we propose a refined form of seeding on the foundation of the FMD-index.

Original languageEnglish
Article number1939
JournalNature Communications
Volume10
Issue number1
DOIs
StatePublished - 2019 Dec 1

Fingerprint

Nanopores
Seed
Data structures
seeds
Seeds
alignment
Throughput
deletion
sequencing
data structures
inoculation
Processing
insertion
strip

Cite this

@article{2eb3961d3567418cb16135f0870b3099,
title = "Accurate high throughput alignment via line sweep-based seed processing",
abstract = "Accurate and fast aligners are required to handle the steadily increasing volume of sequencing data. Here we present an approach allowing performant alignments of short reads (Illumina) as well as long reads (Pacific Bioscience, Ultralong Oxford Nanopore), while achieving high accuracy, based on a universal three-stage scheme. It is also suitable for the discovery of insertions and deletions that originate from structural variants. We comprehensively compare our approach to other state-of-the-art aligners in order to confirm its performance with respect to accuracy and runtime. As part of our algorithmic scheme, we introduce two line sweep-based techniques called “strip of consideration” and “seed harmonization”. These techniques represent a replacement for chaining and do not rely on any specially tailored data structures. Additionally, we propose a refined form of seeding on the foundation of the FMD-index.",
author = "Markus Schmidt and Klaus Heese and Arne Kutzner",
year = "2019",
month = "12",
day = "1",
doi = "10.1038/s41467-019-09977-2",
language = "English",
volume = "10",
journal = "Nature communications",
issn = "2041-1723",
number = "1",

}

Accurate high throughput alignment via line sweep-based seed processing. / Schmidt, Markus; Heese, Klaus; Kutzner, Arne.

In: Nature Communications, Vol. 10, No. 1, 1939, 01.12.2019.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Accurate high throughput alignment via line sweep-based seed processing

AU - Schmidt, Markus

AU - Heese, Klaus

AU - Kutzner, Arne

PY - 2019/12/1

Y1 - 2019/12/1

N2 - Accurate and fast aligners are required to handle the steadily increasing volume of sequencing data. Here we present an approach allowing performant alignments of short reads (Illumina) as well as long reads (Pacific Bioscience, Ultralong Oxford Nanopore), while achieving high accuracy, based on a universal three-stage scheme. It is also suitable for the discovery of insertions and deletions that originate from structural variants. We comprehensively compare our approach to other state-of-the-art aligners in order to confirm its performance with respect to accuracy and runtime. As part of our algorithmic scheme, we introduce two line sweep-based techniques called “strip of consideration” and “seed harmonization”. These techniques represent a replacement for chaining and do not rely on any specially tailored data structures. Additionally, we propose a refined form of seeding on the foundation of the FMD-index.

AB - Accurate and fast aligners are required to handle the steadily increasing volume of sequencing data. Here we present an approach allowing performant alignments of short reads (Illumina) as well as long reads (Pacific Bioscience, Ultralong Oxford Nanopore), while achieving high accuracy, based on a universal three-stage scheme. It is also suitable for the discovery of insertions and deletions that originate from structural variants. We comprehensively compare our approach to other state-of-the-art aligners in order to confirm its performance with respect to accuracy and runtime. As part of our algorithmic scheme, we introduce two line sweep-based techniques called “strip of consideration” and “seed harmonization”. These techniques represent a replacement for chaining and do not rely on any specially tailored data structures. Additionally, we propose a refined form of seeding on the foundation of the FMD-index.

UR - http://www.scopus.com/inward/record.url?scp=85064956284&partnerID=8YFLogxK

U2 - 10.1038/s41467-019-09977-2

DO - 10.1038/s41467-019-09977-2

M3 - Article

VL - 10

JO - Nature communications

JF - Nature communications

SN - 2041-1723

IS - 1

M1 - 1939

ER -