High scoring segment selection for pairwise whole genome sequence alignment with the maximum scoring subsequence and GPUs

Abdulrhman Aljouie, Ling Zhong, Usman Roshan

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Whole genome alignment programs use string matching with hash tables to identify high scoring fragments between a query and target sequence around which a full alignment is then built. A recent study comparing alignment programs showed that while evolutionary similar genomes were easy to align, divergent genomes still posed a challenge to existing methods. To fill this gap we explore the use of the maximum scoring subsequence to identify high scoring fragments. We split the query genome into several fragments and align them to the target with a previously published parallel algorithm for short read alignment. We then pass such high scoring fragments on to the LASTZ program to obtain a more complete alignment. On simulated data we obtain an average of at least 20% higher accuracy than the alignment given by LASTZ at the expense of few hours of additional runtime.

Original languageEnglish (US)
Pages (from-to)71-81
Number of pages11
JournalInternational Journal of Computational Biology and Drug Design
Volume13
Issue number1
DOIs
StatePublished - 2020

All Science Journal Classification (ASJC) codes

  • Drug Discovery
  • Computer Science Applications

Keywords

  • Anchor selection
  • GPU
  • Genome alignment
  • Graphics processing unit
  • LASTZ

Fingerprint Dive into the research topics of 'High scoring segment selection for pairwise whole genome sequence alignment with the maximum scoring subsequence and GPUs'. Together they form a unique fingerprint.

Cite this