A Sequence Alignment Algorithm With Combining Variants Data

The sequence alignment is of great significance for bioinformatics. With therapid development of next-generation sequencing technology, there are vast amountsof data that could be gained for researchers in a short time. To deal with this mass ofinformation, many alignment tools based on next-generation sequencing, whichprovides a great convenience to the researchers, has begun to appear. The commonalignment tools operate just between single reference genome and read data, whichwill appeared to be inadequate in some applications. When studying the relationshipof the disease and some genes,we should align the reads from one genome tomultiple genomes. Based on this consideration, the algorithm of sequence alignmentwhich is based on HapMap database, was proposed in this paper.In this project, the topic of how to find the best match position of the read inthe reference genome and the HapMap database, was divided into the followingthree cases：The best alignment position locates in common region, variation regionor union region. The BWT method was employed to align reads in common region,the equal_range algorithm was employed to align reads in variation region, and theunion alignment algorithm was employed in union region.In the beginning, the background and current situation of this subject wasintroduced, the development process and application background of alignmentalgorithm was presented. Then the current mainstream alignment algorithm(BWT andHash table) was compared and analyzed, at the meantime, the advantages anddisadvantages were concluded respectively, which paved the way of our furtherresearch. Afterwards, the analysis the commonalities and differences of differentgenomes was completed. On this basis, the research of the HapMap sequencealignment was proposed, and the basic idea of the algorithm, technologies routes andthe process were described. At last, comparing with two current popular NGSalignment tools, Bowtie and BWA, our tool has lower speed but higher accuracy.