首页|Graph search and variable neighborhood search for finding constrained longest common subsequences in artificial and real gene sequences
Graph search and variable neighborhood search for finding constrained longest common subsequences in artificial and real gene sequences
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
We consider the constrained longest common subsequence problem with an arbitrary set of input strings as well as an arbitrary set of pattern strings. This problem has applications, for example, in computational biology where it serves as a measure of similarity for sets of molecules with putative structures in common. We contribute in several ways. First, it is formally proven that finding a feasible solution of arbitrary length is, in general, NP-complete. Second, we propose several heuristic approaches: a greedy algorithm, a beam search aiming for feasibility, a variable neighborhood search, and a hybrid of the latter two approaches. An exhaustive experimental study shows the effectivity and differences of the proposed approaches in respect to finding a feasible solution, finding high-quality solutions, and runtime for both, artificial and real-world instance sets. The latter ones are generated from a set of 12681 bacteria 16S rRNA gene sequences and consider 15 primer contigs as pattern strings. (C)& nbsp;2022 Elsevier B.V. All rights reserved.
Longest common subsequenceBeam searchHybrid MethodsVariable neighborhood searchComputational biologyBEAM SEARCHALGORITHM
Djukanovic, Marko、Kartelj, Aleksandar、Matic, Dragan、Grbic, Milana、Blum, Christian、Raidl, Guenther R.
NSTL
Elsevier
