title: Empirical Transition Probability Indexing Sparse-Coding Belief Propagation (ETPI-SCoBeP) Genome Sequence Alignment.
abstract: The advance in human genome sequencing technology has significantly reduced the cost of data generation and overwhelms the computing capability of sequence analysis. Efficiency, efficacy, and scalability remain challenging in sequence alignment, which is an important and foundational operation for genome data analysis. In this paper, we propose a two-stage approach to tackle this problem. In the preprocessing step, we match blocks of reference and target sequences based on the similarities between their empirical transition probability distributions using belief propagation. We then conduct a refined match using our recently published sparse-coding belief propagation (SCoBeP) technique. Our experimental results demonstrated robustness in nucleotide sequence alignment, and our results are competitive to those of the SOAP aligner and the BWA algorithm. Moreover, compared to SCoBeP alignment, the proposed technique can handle sequences of much longer lengths.
authors.affiliation: School of Electrical and Computer Engineering, University of Oklahoma, Tulsa, OK, USA.
authors.forename: Aminmohammad
authors.initials: A
authors.lastname: Roozgard
authors.affiliation: School of Electrical and Computer Engineering, University of Oklahoma, Tulsa, OK, USA.
authors.forename: Nafise
authors.initials: N
authors.lastname: Barzigar
authors.affiliation: Division of Biomedical Informatics, University of California, San Diego, CA, USA.
authors.forename: Shuang
authors.initials: S
authors.lastname: Wang
authors.affiliation: Division of Biomedical Informatics, University of California, San Diego, CA, USA.
authors.forename: Xiaoqian
authors.initials: X
authors.lastname: Jiang
authors.affiliation: School of Electrical and Computer Engineering, University of Oklahoma, Tulsa, OK, USA.
authors.forename: Samuel
authors.initials: S
authors.lastname: Cheng
keywords: belief propagation; empirical transition probability; genome sequence alignment; indexing; sparse-coding