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