• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Computer Applications in Industry and Engineering >An Efficient Sequential Algorithm for the k-LCS Problem
【24h】

An Efficient Sequential Algorithm for the k-LCS Problem

机译：k-LCS问题的有效顺序算法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The problem of finding a Longest Common Subsequence (LCS) frequently arises in a number of areas such a genetic engineering, data compression and syntactic pattern recognition. It has therefore been extensively studied in sequential but the inherent O(n x m) time complexity of the LCS problem can only be improved under restrictive assumptions. The problem of the longest common subsequence of more than two sequences was poorly studying although this problem is very important to solve the sequence alignment problem. Sequential algorithms are proposed to find an LCS of three sequences but the complexity in time is close to a cubic time. The generalization to k sequences yields to a complexity in time of O(n~k) (n and k represent respectively the length of the longest input sequence and the number of sequences). In this paper, we propose an algorithm with a complexity of 0(k x n~4).
机译：寻找最长公共子序列（LCS）的问题经常出现在许多领域，例如基因工程，数据压缩和句法模式识别。因此，已经在顺序上进行了广泛研究，但是LCS问题的固有O（n x m）时间复杂度只能在限制性假设下得到改善。尽管这个问题对于解决序列比对问题非常重要，但对两个以上序列的最长公共子序列问题的研究却很少。提出了顺序算法来找到三个序列的LCS，但是时间复杂度接近三次时间。对k个序列的泛化导致时间复杂度为O（n〜k）（n和k分别代表最长输入序列的长度和序列数）。在本文中，我们提出了一种算法，其复杂度为0（k x n〜4）。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号