کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6904195 1446998 2018 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hybrid techniques based on solving reduced problem instances for a longest common subsequence problem
ترجمه فارسی عنوان
تکنیک های ترکیبی بر اساس حل نمونه های کمبود مشکل برای طولانی ترین مشکل متعاقب متعارف است
کلمات کلیدی
بهینه سازی ترکیبی، طولانی ترین متعاقبا عادی، برنامه ریزی خطی عدد صحیح، ابتکاری، الگوریتم ترکیبی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نرم افزارهای علوم کامپیوتر
چکیده انگلیسی
Finding the longest common subsequence of a given set of input strings is a relevant problem arising in various practical settings. One of these problems is the so-called longest arc-preserving common subsequence problem. This NP-hard combinatorial optimization problem was introduced for the comparison of arc-annotated ribonucleic acid (RNA) sequences. In this work we present an integer linear programming (ILP) formulation of the problem. As even in the context of rather small problem instances the application of a general purpose ILP solver is not viable due to the size of the model, we study alternative ways based on model reduction in order to take profit from this ILP model. First, we present a heuristic way for reducing the model, with the subsequent application of an ILP solver. Second, we propose the application of an iterative hybrid algorithm that makes use of an ILP solver for generating high quality solutions at each iteration. Experimental results concerning artificial and real problem instances show that the proposed techniques outperform an available technique from the literature.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Soft Computing - Volume 62, January 2018, Pages 15-28
نویسندگان
, ,