漸進式序列比對:演算技術及應用

Incremental Sequence Comparison: Algorithmic Techniques and Applications

許秉慧(Ping-Hui Hsu)

指導教授 ： 趙坤茂

國立臺灣大學/電機資訊學院/資訊工程學研究所/博士(2011年)

https://doi.org/10.6342/NTU.2011.00594

摘要

無資料

關鍵字

漸進式計算 ； 序列比對 ； 編輯距離全域排比 ； 區域排比

並列摘要

In this dissertation, we present two kinds of techniques for incremental sequence comparison whose objective is to save the time for comparing sequences that change over time.
The first technique is used when the input sequences are changed incrementally and/or decrementally. More specifically, we may append characters to the head of one sequence and/or remove characters from that of the other sequence. Our goal is to obtain the comparison result of updated sequences by utilizing the outdated comparison result. Some applications are introduced to show how to apply this incremental technique for efficiency gains.
The second technique is used when two instances (two pairs of sequences) share high similarities with each other. This technique consists of two stages: (1) partitioning the sequences into smaller segments and performing pairwise segment comparison; and (2) using these comparison results to construct the solution of the original sequence comparison. In the first stage, one instance takes advantage of those common segment comparison results of the other instance. In the second stage, the segment comparison results are combined to produce the solution of each instance. We introduce how to apply this technique for incrementally computing both global and local alignments.

並列關鍵字

incremental computing ； sequence comparison ； edit distance ； global alignment ； local alignment

參考文獻

[1] A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber. Geometric applications of a matrix searching algorithm, Algorithmica, 2, pp. 195-208 (1987).

[2] A. Aggarwal and J. Park, Notes on searching in multidimensional monotone arrays, Proceedings of the 29th Symposium on Foundations of Computer Science, pp. 497-512 (1988).

[3] E. Akgun, J. Zahn, S. Baumes, G. Brown, F. Liang, P. J. Romanienko, S. Lewis, and M. Jasin. Palindrome resolution and recombination in the mammalian germ line, Molecular

and Cellular Biology, 17, pp. 5559-5570 (1997).

[6] A. Apostolico, M. J. Atallah, L. L. Larmore, and S. McFaddin. E±cient parallel algorithms for string editing and related problems, SIAM Journal on Computing, 19, pp. 968-988 (1990).