Design And Implementation Of Long Sequence Alignment Algorithms Based On Xeon Phi

A gene is a genetic information that controls a biological trait,usually carried by a DNA sequence,and can be considered as a basic genetic unit.The products of the genes can be proteins and RNA,thereby controlling the differential performance of the traits of the individual.The similarity between the two genes is high,and it is possible to have homology in evolution.It comes down to calculations,which is how to find the optimal or nearly optimal alignment of two sequences.With the completion of the sequencing of the Human Genome Project,the research of bioinformatics focuses on the function of gene sequences.With the rapid development of high throughput sequencing technology,biological data show exponential growth.Therefore,there is a need for efficient and accurate analysis of a large number of biological information data.Gene sequence determines the nature of organisms.Finding out genetic differences is of far-reaching significance for human beings to overcome diseases.In this paper,we propose a new super-long sequence alignment algorithm SLPal which is designed and implemented on Xeon Phi multi-core architecture.The core of the algorithm is BitPAI algorithm based on bit parallel.At the coarse-grained level,in order to achieve multi-threaded parallelism,we divided the super-large scale matrix into multiple tiles in the vertical and horizontal directions.Then a directed acyclic graph model is constructed by Intel TBB parallel programming library to realize the parallelism between matrix blocks in the grid.At fine granularity,we write the Intrinsic instruction with the instruction set on Xeon Phi.Some operations in SLPal have no corresponding vectorization implementation,and we use manual writing functions to achieve the related functions.Experiments show that SLPal algorithm is more efficient than the existing super-long sequence alignment algorithm.The computational performances of 172 and 482GCUPS are obtained on the KNC and KNL platforms.Compared with the parallel super-long sequence alignment algorithm of swaphi-ls,SLPal achieved an acceleration ratio of 5.8 times and 16 times on KNC and KNL,respectively.