Sequence Alignment Algorithms for Run-Length-Encoded Strings

摘要：

A unified framework is applied to solving various sequence comparison problems for run-length encoded strings. All of these algorithms take O(minmn,mn)time and O(maxm, n) space, for two strings of lengths m and n, with m and n runs, respectively. We assume the linear-gap model and make no assumption on the scoring matrices, which maximizes the applicability of these algorithms. The trace (i.e., the way to align two strings) of an optimal solution can also be recovered within the same time and space bounds.

作者: Guan Shieng Huang Jia Jie Liu Yue Li Wang

作者单位: Department of Computer Science and Information Engineering,National Chi Nan University, Taiwan Department of Information Management, Shih Hsin University, Taiwan Department of Computer Science and Information Engineering, National Chi Nan University,Taiwan

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 319-330

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）