استكشاف مشكلة تسلسل العناصر المشترك الأطول: ثغرات متعددة ومتغيرات معقدة

يتناول هذا المقال البحثي موضوعاً مثيراً في مجال علوم الحوسبة، وهو مشكلة تسلسل العناصر المشترك الأطول مع الثغرات المتعددة (Variable Gapped Longest Common Subsequence - VGLCS). تُعَد هذه المشكلة تعميماً لمشكلة التسلسل المشترك الأشهر، حيث يظهر دور الفجوة بين عناصر الحلول المتتابعة بشكل مرن. تبرز أهمية هذه المشكلة في عدة مجالات، مثل مقارنة التسلسل الجزيئي، حيث يتطلب احترام قيود المسافة الهيكلية بين عناصر الجزيئات، وكذلك في تحليل السلاسل الزمنية حيث يتوجب على الأحداث أن تحدث ضمن تأخيرات زمنية محددة.

تقدم الورقة البحثية إطار عمل بحثي مبتكر يعتمد على تمثيل رسم بياني يعتمد على الجذور، حيث يتكون فضاء الحالة من عدد كبير من الرسوم البيانية الفرعية الجذرية. وللتعامل مع الانفجار التوافقي الناتج عن ذلك، تم استخدام استراتيجية بحث تكرارية تعتمد على تقنية الـ Beam Search، والتي تحافظ ديناميكيًا على مجموعة عالمية من العقد الجذرية الواعدة، مما يتيح التحكم الفعال في التنوع عبر التكرارات.

للاستفادة المثلى من البحث عن حلول عالية الجودة، تم دمج عدد من التقنيات المعروفة من أدبيات التسلسل المشترك الأطول في إجراء البحث المستقل. تعتبر هذه الدراسة، بحسب علمنا، أول دراسة حسابية شاملة لمشكلة VGLCS، حيث تم استخدام 320 حالة اصطناعية تضم ما يصل إلى 10 تسلسلات إدخال وما يصل إلى 500 حرف.

تشير النتائج التجريبية إلى فعالية الأسلوب المصمم مقارنة بتقنية الـ Beam Search الأساسية في أوقات تنفيذ مماثلة، ما يعكس تقدمًا ملحوظًا في قدرة النموذج على التعامل مع تنوع الحلول المتاحة وزيادة جودتها.