A large neighborhood search heuristic for the longest common subsequence problem

被引：0
作者：
Todd Easton
Abhilash Singireddy
机构：
[1] Kansas State University,School of Industrial and Manufacturing Systems Engineering
来源：
Journal of Heuristics | 2008年 / 14卷
关键词：
Longest common subsequence; Dynamic programming; Large neighborhood search; Heuristic;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Given a set S={S1,…,Sk} of finite strings, the k-Longest Common Subsequence Problem (k-LCSP) seeks a string L* of maximum length such that L* is a subsequence of each Si for i=1,…,k. This paper presents a large neighborhood search technique that provides quality solutions to large k-LCSP instances. This heuristic runs in linear time in both the length of the sequences and the number of sequences. Some computational results are provided.
引用
收藏
页码：271 / 283
页数：12
相关论文
共 47 条
[1]  
Ahuja R.(2002)A survey of very large-scale neighborhood search techniques Discret. Appl. Math. 123 75-102
[2]  
Ergun O.(1998)Experimenting an approximation algorithm for the LCS Discret. Appl. Math. 110 13-24
[3]  
Orlin J.(1994)Performance analysis of some simple heuristics for computing longest common subsequences Algorithmica 12 293-311
[4]  
Punen A.(1969)Computer analysis of protein evolution Sci. Am. 221 86-95
[5]  
Bonizzoni P.(1978)A model of evolutionary change in proteins Atlas Protein Seq. Struct. 5 345-352
[6]  
Vedova G.D.(1992)Italiano, Sparse dynamic programming. II. convex and concave cost functions J. Assoc. Comput. Mach. 39 546-567
[7]  
Mauri G.(1980)On finding minimal length superstrings J. Comput. Syst. Sci. 20 50-58
[8]  
Chin F.(1995)Longest common subsequence to multiple strings. Exact and approximate algorithms Tech. Sci. Inform. 14 897-915
[9]  
Poon C.(2004)Supersequence of masks for oligo-chips J. Bioinform. Comput. Biol. 2 459-469
[10]  
Dayhoff M.O.(1975)A linear space algorithm for computing maximal common subsequences Commun. Assoc. Comput. Mach. 18 341-343
12345