The longest common subsequence problem for arc-annotated sequences

被引：0
作者：
Jiang, T [1 ]
Lin, GH
Ma, B
Zhang, KZ
机构：
[1] Univ Calif Riverside, Dept Comp Sci, Riverside, CA 92521 USA
[2] Univ Waterloo, Dept Comp Sci, Waterloo, ON N2L 3G1, Canada
[3] Univ Western Ontario, Dept Comp Sci, London, ON N6A 5B7, Canada
[4] McMaster Univ, Dept Comp & Software, Hamilton, ON L8S 4L7, Canada
来源：
COMBINATORIAL PATTERN MATCHING | 2000年 / 1848卷
关键词：
sequence annotation; longest common subsequence; approximation algorithm; maximum independent set; MAX SNP-hard; dynamic programming;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Are-annotated sequences are useful in representing the structural information of RNA and protein sequences. Recently, the longest are-preserving common subsequence problem has been introduced in [6, 7] as a framework for studying the similarity of arc-annotated sequences. In this paper, we consider are-annotated sequences with various are structures and present some new algorithmic and complexity results on the longest are-preserving common subsequence problem. Some of our results answer an open question in [6, 7] and some others improve the hardness results in [6,7].
引用
收藏
页码：154 / 165
页数：12
相关论文
共 14 条
[1]  
BAFNA V, 1996, 9630 DIMACS
[2]   Free bits, PCPs, and nonapproximability - Towards tight results [J].
Bellare, M ;
Goldreich, O ;
Sudan, M .
SIAM JOURNAL ON COMPUTING, 1998, 27 (03) :804-915
[3]  
BERMAN P, LNCS, V955, P449
[4]  
CORPET F, 1994, COMPUT APPL BIOSCI, V10, P389
[5]   A special case for subset interconnection designs [J].
Du, DZ ;
Gao, B ;
Wu, WL .
DISCRETE APPLIED MATHEMATICS, 1997, 78 (1-3) :51-60
[6]  
Evans P., 1999, THESIS U VICTORIA
[7]  
EVANS PA, LNCS, V1645, P270
[8]  
GOLDMAN D, 1999, P IEEE 40 ANN C FDN
[9]  
HIRSCHBERG DS, 1975, THESIS PRINCETON U
[10]  
LENHOF H, P 2 ANN INT C COMP M, P153
12