Research On Re-sequencing Of Next-Generation-Sequencing Data Based On GPU And Compressed Index

GPU(GraphicProcessingUnit)isahighlyefficientcomputingdeviceofmassivelyparallelcapabilitywhichisonlyemergedrecentyears.Itcanformaheterogeneousarchitecture with CPU and have greate potential in wide fields.BWT(Burrows‐Wheeler Transform) is a lossless and reversible data transformationmethod.ThecompressedindexbasedonBWThasadvantageofhighsearchingspeedand less RAM occupation, which makes it outperform other method in mass dataprocessing.Next generation sequencing is a new high‐throughput DNA/RNA sequencingtechnologywhichgainsgreatfocusinrecentyears.Ithasbecomethemajormethodofobtainingnucleotidesequencesandhasbeenappliedingenotypemutation,geneannotation, analysis of mRNA and miRNA, DNA methylation and personalizationmedicine.Comparedtotraditionalsequencingtechnologies,thesequencesproducedbynextgenerationsequencingtechnologyareshorterandingreaterquantity.ThequantityisintheorderoftensevenhundredsofGB.Usuallythesesequencesrequireaprocessofpositioningthemselvestogenome.Thisprocessiscalledre‐sequencing.The re‐sequencing of mass data requires high‐cost computing system or longcomputing time. This research implements high efficient re‐sequencing based oncompressedindexofBWTandGPU.Inthisdissertation,wefirstanalyzedthebackgroundoftherelativefieldsandthefeasibilityofthecombinationofBWTandGPU.Thenwediscussedthecharacterof next generation sequencing, the programming and optimizing methods of GPUcomputing, and the theory and implementation of compressed index. We thenproposed the implementation scheme of re‐sequencing of next generationsequencing data based on GPU and BWT compressed index. We described thethreads assigning, memory copy, key architecture design and dynamic memoryallocationindetail.Finally,wetestourGPU‐BWAschemeandanalyzedthetestresult.Indiscussion,wealsoproposedthefurtherworkandimprovementplan.This research demonstrated that the re‐sequencing based on GPU and BWTcompressedindexisfeasibleandefficient.Meanwhile,thisresearchisalsoagoodexampleoftheapplicationofGPUandcompressedindex.