An SIMD algorithm for wraparound tandem alignment

Joshua Loving, John P. Scaduto, Gary Benson

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

DNA tandem repeats (TRs), and in particular, variable number of tandem repeat (VNTR) loci, can have functional effects on gene regulation and disease mechanisms and are useful for forensics studies. The need to quickly analyze high volumes of sequencing data for TRs and VNTRs has motivated the search for a more efficient sequence alignment algorithm for tandem repeats. Alignment of a pattern to a sequence, which may contain zero or more tandem copies of the pattern, can be accomplished using wraparound dynamic programming (WDP). This paper presents the use of Single Instruction, Multiple Data (SIMD) computer instructions as well as a parallel scan to accelerate WDP, extending earlier SIMD algorithms for global alignment. The SIMD data types and intrinsics store data in 128 bit computer words partitioned into 16 1-byte blocks. Operations are performed on the bytes separately and simultaneously. We allow either single values for match and mismatch, or a substitution scoring scheme that assigns a potentially different substitution weight to every pair of alphabet characters. Additionally, for indels, we allow either a simple linear gap penalty or an affine gap penalty. Benchmarking demonstrated that SIMD tandem alignment runs over 3 times faster than standard wraparound dynamic programming.

Original languageEnglish
Title of host publicationBioinformatics Research and Applications - 13th International Symposium, ISBRA 2017, Proceedings
EditorsZhipeng Cai, Ovidiu Daescu, Min Li
PublisherSpringer Verlag
Pages140-149
Number of pages10
ISBN (Print)9783319595740
DOIs
StatePublished - 2017
Externally publishedYes
Event13th International Symposium on Bioinformatics Research and Applications, ISBRA 2017 - Honolulu, United States
Duration: 29 May 20172 Jun 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10330 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Symposium on Bioinformatics Research and Applications, ISBRA 2017
Country/TerritoryUnited States
CityHonolulu
Period29/05/172/06/17

Fingerprint

Dive into the research topics of 'An SIMD algorithm for wraparound tandem alignment'. Together they form a unique fingerprint.

Cite this