Approximate string matching in DNA sequences

Approximate string matching on large DNA sequences data is very important in bioinformatics.Some studies have shown that suffix tree is an efficient data structure for approximate string matching.It performs better than suffix array if the data structure can be stored entirely in the memory.However, our study find that suffix array is much better than suffix tree for indexing the DNA sequences since the data structure has to be created and stored on the disk due to its size.We propose a novel auxiliary data structure which greatly improves the efficiency of suffix array in the approximate string matching problem in the external memory model.The second problem we have tackled is the parallel approximate matching in DNA sequence.We propose 2 novel parallel algorithms for this problem and implement them on a PC cluster.The result shows that when the error allowed is small, a direct partitioning of the array over the machines in the cluster is a more efficient approach.On the other hand, when the error allowed is large, partitioning the data over the machines is a better approach.1. We show that suffix array is much more efficient than suffix tree in external memory model (i.e. that the main memory is not large enough to store the whole indexing structure)2. We propose a novel auxillary indexing structure named quick lookup table which can improve the searching efficiency of suffix array.3. We propose two novel approaches of parallel computing for indexing and searching DNA sequences in PC clusters which can reduce the index construction time and querying time.