Empirical Transition Probability Indexing Sparse-Coding Belief Propagation (ETPI-SCoBeP) Genome Sequence Alignment

Aminmohammad Roozgard ； Nafise Barzigar ； Shuang Wang ； Xiao-Qian Jiang ； Samuel Cheng

《Cancer Informatics》 2014-S1期 (2014/12) Pp. 159-165

https://doi.org/10.4137/CIN.S13887

並列摘要

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.

並列關鍵字

empirical transition probability ； indexing ； sparse-coding ； belief propagation ； genome sequence alignment