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

Authors: Abdulrhman Aljouie; Ling Zhong; Usman Roshan

Addresses: Department of Computer Science, New Jersey Institute of Technology, Newark, 07102, NJ, USA ' Department of Computer Science, New Jersey Institute of Technology, Newark, 07102, NJ, USA ' Department of Computer Science, New Jersey Institute of Technology, Newark, 07102, NJ, USA

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. Our source code is freely available at http://web.njit.edu/usman/MSGA

Keywords: genome alignment; anchor selection; LASTZ; GPU; graphics processing unit.

DOI: 10.1504/IJCBDD.2020.105097

International Journal of Computational Biology and Drug Design, 2020 Vol.13 No.1, pp.71 - 81

Received: 11 Jul 2018
Accepted: 15 Aug 2018
Published online: 13 Feb 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article