Researches On Long Read Alignment Algorithms Oriented To The Third Generation Sequencing Technology

With the continuous development and improvement of sequencing technology,the genome sequencing reads are also changing.Currently,in order to adapt to the third generation sequencing technology,we need to study and improve the read alignment algorithm further to make that the algorithms can deal with the long reads.This thesis analyses the read alignment algorithms based on hash table and windows hash table indexing method,including SSAHA(Sequence search and alignment by hashing algorithm)the traditional method of read alignment based on hash table indexing and rHAT(Regional hashing-based alignment tool)based on windows hash table indexing.This thesis makes further improvements,and proposes a new method,a long read alignment based on double window hash tables and dynamic location(WHDL).WHDL constructs double windows hash tables including global and local hash tables to reduce repetitive processing.WHDL uses dynamic location method in the hitting and positioning stage.In WHDL,two different methods(WHDL-1 and WHDL-2)and SSAHA+ are proposed in the comparison and processing stage.In this thesis,the algorithms with their experimental results are compared and analyzed.Compared with rHAT,WHDL-1 needs less running time,increases the speed of sequenceing and improves the processing efficiency.In addition,the feasibility and granularity of parallel processing are discussed.In addition,This thesis discusses the location of read alignment from the perspective of sequence similarity comparison,and explores how to understand genomic rules and genetic variation from the perspective of signal and noise.