| With the development of computer technology, more and more data is preserved in computers in the form of electronic files. Among them, there exists considerable quantities of text data. Analyzing the text data is significant for the fields of information retrieval and bioinformatics. Local alignment, as the technique for measuring the similarity between different strings, is well suitable for the analysis on text data and has received much concern from the academic community. The widely spread of text data makes it remarkably important to develop an efficient algorithm for searching and analyzing on long strings.There have existed several algorithms for finding the local alignments on the text data. The Smith-Waterman algorithm in 1981 is a classic algorithm to solve the local alignment problem. However, the algorithm is impractical for its low inefficiency on long strings. The later on OASIS algorithm, BWT-SW algorithm and ALAE algorithm make improvements on the efficiency, among which the ALAE algorithm stands out. The ALAE algorithm proposes several filtering strategies to avoid redundant calculations, greatly increasing the efficiency of computing local alignments. All these algorithms need a threshold score, which is used to decide whether one local alignment should be returned as one of the results. Different from this, the top-k local alignment problem requires the solution to return k optimum alignment results with the absence of the score threshold. So far there has been no algorithm for the top-k local alignment problem, thus making it a challenge. On the other hand, current algorithms for the local alignment problem require the text data being held in memory entirely, otherwise the performance of them would be degraded greatly. How can conduct the local alignment computations with inadequate memory space in high efficiency also proposes a challenge.For the top-k local alignment problem, we propose a heuristic strategy that the local alignments beginning with long prefixes are more likely to achieve higher scores. Based on it, we present the techniques to efficiently locate long common prefixes. Through analyzing and comparing the differences between the top-k local alignment problem and the conventional one, we formally define the domination relation and give the solution to efficiently locating and updating the dominated local alignments. When computing local alignments, we propose the variable prefixes trie-based filtering technique and the BWT backward search based filtering technique, further reducing the redundant calculations and improving the efficiency. As for the local alignment problem on large scale text data, we propose an external-memory algorithm, with the external-memory suffix tree as the index. On the access property of the external-memory suffix tree, the algorithm optimizes the I/O costs and solves the inadequate memory space problem. The results of the experiments on the real genetic data, demonstrate the effectiveness of our algorithms. |
