检索结果-内蒙古大学图书馆

Bit-Parallel Algorithm for the constrained longest common subsequence Problem

FUNDAMENTA INFORMATICAE 2010年第4期99卷 409-433页

作者： Deorowicz, Sebastian Silesian Tech Univ Inst Informat PL-44100 Gliwice Poland

The problem of finding a constrained longest common subsequence (CLCS) for the sequences A and B with respect to the sequence P was introduced recently. Its goal is to find a longest subsequence C of A and B such that P is a subsequence of C. Most of the algorithms solving the CLCS problem are based on dynamic programming. Bit-parallelism is a technique of using single bits in a machine word for concurrent computation. We propose the first bit-parallel algorithm computing a CLCS and/or its length which outperforms the other known algorithms in terms of speed.

关键词： constrained longest common subsequence longest common subsequence dynamic programming bit-parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Variants of constrained longest common subsequence

引用

INFORMATION PROCESSING LETTERS 2010年第20期110卷 877-881页

作者： Bonizzoni, Paola Della Vedova, Gianluca Dondi, Riccardo Pirola, Yuri Univ Bergamo Dipartimento Sci Linguaggi Comunicaz & Studi Cult Bergamo Italy Univ Milano Bicocca Dipartimento Stat Milan Italy Univ Milano Bicocca DISCo Milan Italy

We consider a variant of the classical longest common subsequence problem called Doubly-constrained longest common subsequence (DC-LCS). Given two strings s(1) and s(2) over an alphabet Sigma, a set C-s of strings, and a function C-0 : Sigma -> N, the DC-LCS problem consists of finding the longest subsequence s of s(1) and s(2) such that s is a supersequence of all the strings in C-s and such that the number of occurrences in s of each symbol sigma is an element of Sigma is upper bounded by C-0(sigma). The DC-LCS problem provides a clear mathematical formulation of a sequence comparison problem in Computational Biology and generalizes two other constrained variants of the LCS problem that have been introduced previously in the literature: the constrained LCS and the Repetition-Free LCS. We present two results for the DC-LCS problem. First, we illustrate a fixed-parameter algorithm where the parameter is the length of the solution which is also applicable to the more specialized problems. Second, we prove a parameterized hardness result for the constrained LCS problem when the parameter is the number of the constraint strings (vertical bar C-s vertical bar) and the size of the alphabet Sigma E. This hardness result also implies the parameterized hardness of the DC-LCS problem (with the same parameters) and its NP-hardness when the size of the alphabet is constant. 2010 Elsevier B.V. All rights reserved.

关键词： Algorithms longest common subsequence constrained longest common subsequence Fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

The constrained longest common subsequence: Theory and Experiments 39

The Constrained Longest Common Subsequence: Theory and Exper...

引用

39th IEEE Central America and Panama Convention (IEEE CONCAPAN)

作者： Soto, Daniel Soto, Wilson Univ Antioquia Medellin Colombia Univ Catolica Pereira Pereira Colombia

ISBN: (纸本)9781728108834

A common operation on strings is to calculate a value of similarity. The longest common subsequence (LCS) is a measure of similarity between two sequences. An extension of LCS measure is the constrained longest common subsequence (CLCS). The CLCS consists of calculating the LCS of two sequences, and it is a supersequence of a constrained sequence. This paper is an experimental evaluation of the most important CLCS algorithms. The implemented algorithms have a similar performance and were tested with different kinds of random strings belonging to the alphabets: generated uniformly at random (4, 10, 20, 32, 48 and 64 characters) and English text (239 characters). This study could help in selecting optimal algorithms for a given problem.

关键词： Algorithms Approximate String Matching Sequence Comparison longest common subsequence constrained longest common subsequence

来源：评论

学校读者我要写书评

暂无评论

constrained longest common subsequences with Run-Length-Encoded Strings

引用

COMPUTER JOURNAL 2015年第5期58卷 1074-1084页

作者： Liu, Jia-Jie Wang, Yue-Li Chiu, Yu-Shan Shih Hsin Univ Dept Informat Management Taipei 10607 Taiwan Natl Taiwan Univ Sci & Technol Dept Informat Management Taipei Taiwan

Given two strings X and Y and a constraining string P, a string Z is called a constrained longest common subsequence of X and Y with respect to P if Z is the longest common subsequence of X and Y such that P is a subsequence of Z. In this paper, we propose an O(r x min{mN, nM})-time algorithm for solving this problem, where m, n and r are the lengths of X, Y and P, respectively, and M and N are the number of runs of the run-length-encoded strings of X and Y, respectively.

关键词： longest common subsequence constrained longest common subsequence run-length-encoding string compression

来源：评论

学校读者我要写书评

暂无评论

Quadratic-time algorithm for a string constrained LCS problem

引用

INFORMATION PROCESSING LETTERS 2012年第11期112卷 423-426页

作者： Deorowicz, Sebastian Silesian Tech Univ Inst Informat Gliwice Poland

The problem of finding a longest common subsequence of two main sequences with some constraint that must be a substring of the result (STR-IC-LCS) was formulated recently. It is a variant of the constrained longest common subsequence problem. As the known algorithms for the STR-IC-LCS problem are cubic-time, the presented quadratic-time algorithm is significantly faster. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Algorithms Sequence similarity longest common subsequence constrained longest common subsequence

来源：评论

学校读者我要写书评

暂无评论

A simple algorithm for the constrained sequence problems

引用

INFORMATION PROCESSING LETTERS 2004年第4期90卷 175-179页

作者： Chin, FYL De Santis, A Ferrara, AL Ho, NL Kim, SK Univ Hong Kong Dept Comp Sci & Informat Syst Hong Kong Peoples R China Univ Salerno Dipartimento Informat & Applicaz I-84081 Baronissi SA Italy Chung Ang Univ Dept Comp Sci & Engn Dongjak Ku Seoul 156756 South Korea

In this paper we address the constrained longest common subsequence problem. Given two sequences X, Y and a constrained sequence P, a sequence Z is a constrained longest common subsequence for X and Y with respect to P if Z is the longest subsequence of X and Y such that P is a subsequence of Z. Recently, Tsai [Inform. Process. Lett. 88 (2003) 173-176] proposed an O(n(2 .) m(2 .) r) time algorithm to solve this problem using dynamic programming technique, where n, m and r are the lengths of X, Y and P, respectively. In this paper, we present a simple algorithm to solve the constrained longest common subsequence problem in O(n (.) m (.) r) time and show that the constrained longest common subsequence problem is equivalent to a special case of the constrained multiple sequence alignment problem which can also be solved with the same time complexity. (C) 2004 Published by Elsevier B.V.

关键词： constrained longest common subsequence algorithms dynamic programming sequence alignment

来源：评论

学校读者我要写书评

暂无评论

Dominant Point-Based Sequential and Parallel Algorithms for the Multiple Sequential Substring constrained-LCS Problem

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2024年第4期11卷 1-31页

作者： Tepiele, Hermann bogning Tchendji, Vianney kengne Onabid, Mathias akong Myoupo, J. E. A. N. FReDeRIC Ngomade, Armel nkonjoh Univ Dschang Math & Comp Sci Dschang Cameroon Univ Bamenda Dept Comp Sci Bambili Cameroon Univ Picardie Jules Verne Comp Sci Lab MIS Amiens France Univ Ebolowa Comp Engn Ebolowa Cameroon

The longest common subsequence (LCS) problem is a well-known and studied problem in computer science and bioinformatics. It consists in finding the longest subsequence that is common to two or more given sequences. In this article, we address the problem of finding all LCS for the Sequential Substring constrainedLCS (SSCLCS) problem, called the Multiple SSCLCS problem. To solve this problem, we first propose a dominant point-based sequential algorithm, designed on a new Leveled Direct Acyclic Graph (DAG) that gives the correct evaluation order of subproblems to avoid redundancy due to overlap. Depending on whether the constraints may overlap or not, it requires O ( S |Sigma| K + 1 + r + n |Sigma|) and O ( S |Sigma| K + 1 + n |Sigma|) time with O(Max_level+n|Sigma|) space. S is the number of partial SSCLCS in a node, K is the number of DAG levels, n is the length of sequences, r is the total length of constraints, Max_level is the number of nodes in the largest level of the DAG, and |Sigma| is the length of the alphabet. Then, we derive a coarse-grained multicomputer parallel solution requiring O ( S | Sigma| K +1 + r + n |Sigma | ) and O ( S | Sigma|K+1+n |Sigma | pp ) execution time, O(Max_level + n |Sigma |) memory space and O ( K ) communication rounds. p is the number of processors. Experimental results showed that the parallel algorithm is, respectively, 14.43x and 19.19x faster than the sequential algorithm on 32 and 64 processors.

关键词： constrained longest common subsequence dominant point coarse- grained multicomputer multi-level directed acyclic graph

来源：评论

学校读者我要写书评

暂无评论

Finite automata based algorithms on subsequences and supersequences of degenerate strings

引用

JOURNAL OF DISCRETE ALGORITHMS 2010年第2期8卷 117-130页

作者： Iliopoulos, Costas Rahman, M. Sohel Voracek, Michal Vagner, Ladislav Kings Coll London Dept Comp Sci Algorithm Design Grp London WC2R 2LS England Czech Tech Univ Dept Comp Sci & Engn Prague Czech Republic

In this paper, we present linear-time algorithms for the construction two novel types of finite automata and show how they can be used to efficiently solve the longest common subsequence (LCS), Shortest common Supersequence (SCS) and constrained longest common subsequence (CLCS) problems for degenerate strings. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Finite automata Degenerate strings longest common subsequence Shortest common supersequence constrained longest common subsequence

来源：评论

学校读者我要写书评

暂无评论

Coarse-Grained Multicomputer Based-Parallel Algorithms for the longest common subsequence Problem with a String-Exclusion Constraint 16

Coarse-Grained Multicomputer Based-Parallel Algorithms for t...

引用

International Conference on High Performance Computing & Simulation (HPCS)

作者： Myoupo, Jean Frederic Ngomade, Armel Nkonjoh Tchendji, Vianney Kengne Univ Picardie Jules Verne Comp Sci Lab MIS Amiens France Univ Dschang Dept Math & Comp Sci Dschang Cameroon

ISBN: (纸本)9781538678794

In this paper, new parallel algorithms based on the Coarse-Grained Multicomputer (CGM) model for solving the longest common subsequence (LCS) problem with a string exclusion constraint (STR-EC-LCS) is presented. Based on a previous sequential algorithm, we propose two CGM parallel algorithms for STR-EC-LCS problem. We perform an experimental study of our two solutions to validate our theoretical predictions, and conclude that our first algorithm that minimizes idleness of the processors is better than the second. To the best of our knowledge, these algorithms are the first CGMbased parallel algorithms for the generalized-constrained-LCS problem.

关键词： Parallel Algorithms constrained longest common subsequence Dynamic Programming Coarse-Grained Multicomputer

来源：评论

学校读者我要写书评

暂无评论

Space-Efficient STR-IC-LCS Computation 48th

Space-Efficient STR-IC-LCS Computation

引用

48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Yonemoto, Yuuki Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo Kyushu Univ Dept Informat Sci & Technol Fukuoka Japan Kyushu Univ Dept Informat Fukuoka Japan Japan Sci & Technol Agcy PRESTO Kawaguchi Saitama Japan Tokyo Med & Dent Univ M&D Data Sci Ctr Tokyo Japan

ISBN: (纸本)9783031231001;9783031231018

One of the most fundamental methods for comparing two given strings A and B is the longest common subsequence (LCS), where the task is to find (the length) of the longest common subsequence. In this paper, we address the STR-IC-LCS problem which is one of the constrained LCS problems proposed by Chen and Chao [J. Comb. Optim, 2011]. A string Z is said to be an STR-IC-LCS of three given strings A, B, and P, if Z is one of the longest common subsequences of A and B that contains P as a substring. We present a space efficient solution for the STR-IC-LCS problem. Our algorithm computes the length of an STR-IC-LCS in O(n(2)) time and O((l + 1)(n - l + 1)) space where l is the length of a longest common subsequence of A and B of length n. When l = O(1) or n - l = O(1), then our algorithm uses only linear O(n) space.

关键词： String algorithm constrained longest common subsequence Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：