Computer Science ›› 2017, Vol. 44 ›› Issue (2): 270-274.doi: 10.11896/j.issn.1002-137X.2017.02.045

Previous Articles     Next Articles

Computing Longest Common Subsequences Approximately Based on Lattice

SUN Tao and ZHU Xiao-ming   

  • Online:2018-11-13 Published:2018-11-13

Abstract: The longest common subsequences can represent the common information of a sequence set,and it has many important applications in many fields,such as computational genomics,information retrieval and so on.Computing longest common subsequences is a famous NP-hard problem with multiple solutions.Some approximate algorithms have a low time complexity,but the result set only has one subsequence.For the sequence set with many longest common subsequences,the information loss is overmuch.In this paper,we presented a new approximate algorithm for this problem.Our algorithm employs a specific mathematical structure called lattice.Firstly,the common lattice of two sequences is computed through dynamic programming and then the common lattice of the current lattice and the current sequence recursively combined with the greedy algorithm are also computed.As the paths in a common lattice contain many common subsequences,the result set contains many longest common subsequences of the original sequence set.And the validity of our algorithm is proved through theory and experiment.

Key words: Longest common subsequences (LCS),Lattice,Approximate algorithm,Greedy algorithm

[1] MAIER D.The complexity of some problem on subsequencesand superseuqences[J].Journal of the ACM (JACM), 1978,25 (2):322-366.
[2] BERGROTH L,HAKONEN H,RAITA T.A survey of longest common subsequence algorithms[C]∥Processings.Seventh International Symposium on String Processing and Information Retrieval,2000(SPIRE 2000).IEEE,2000:39-48.
[3] ATTWOOD T,FINDLAY J.Fingerprinting g-protein-coupledreceptors[J].Protein engineering,1994,7(2):195-203.
[4] SANKOFF D,BLANCHETTE M.Phylogenetic invariants forgenome rearrangements[J].Journal of Computational Biology,1999,6(3/4):431-445.
[5] SHUKLA A,AGARWAL S.A relative position based algorithm to find out the longest common subsequence from multiple biological sequences[C]∥Proceedings of the 2010 International Conference on Computer and Communication Technology (ICCCT).2010:496-502.
[6] RIZVI S,AGARWAL P.A new index-based parallel algorithm for finding longest common subsequence in multiple dna sequences[C]∥International Conference in Cognitive Systems.Citeseer,2005.
[7] HAKATA K,IMAI H.Algorithms for the longest commonsubsequence problem for multiple strings based on geometric maxima[J].Optimization Methods and Software,1998,10(2):233-260.
[8] BOURQUE G,PEVZNER P A.Genome-scale evolution:reconstructing gene orders in the ancestral species[J].Genome research,2002,12(1):26-36.
[9] SHERIDAN R P,VENKATARAGHAVAN R.A systematicsearch for protein signature sequences[J].Proteins-Structure Function and Bioinformatics,1992,14(1):16-28.

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .