أقرب سلسلة

في علم الحاسوب النظري ، تعتبر أقرب سلسلة مشكلة حسابية صعبة من نوع NP ، ^{[ 1 ]} والتي تحاول إيجاد المركز الهندسي لمجموعة من سلاسل الإدخال.

لفهم كلمة "مركز"، من الضروري تحديد المسافة بين سلسلتين. عادةً ما تُدرس هذه المسألة مع الأخذ في الاعتبار مسافة هامينغ .

بصورة أدق، إذا كان لدينا n سلسلة نصية s₁, s₂, ..., sₙ بطول m ، فإن _مسألة أقرب _سلسلة تبحث عن _سلسلة نصية جديدة s بطول m بحيث يكون d ( s , sᵢ ₎ ≤ k لجميع قيم i ، حيث d هي مسافة هامينغ ، و k أصغر ما يمكن. ^{[ 2 ]} أما نسخة مسألة القرار من مسألة أقرب سلسلة، وهي مسألة NP-كاملة ، فتأخذ k كمدخل إضافي وتتساءل عما إذا كانت هناك سلسلة نصية ضمن مسافة هامينغ k من جميع السلاسل المدخلة. ^{[ 1 ]}

يمكن اعتبار مشكلة أقرب سلسلة حالة خاصة من مشكلة المركز الواحد العامة التي يتم فيها قياس المسافات بين العناصر باستخدام مسافة هامينغ.

في مجال المعلوماتية الحيوية ، تعتبر مشكلة أقرب سلسلة جانبًا مدروسًا بشكل مكثف من مشكلة إيجاد الإشارات في الحمض النووي .

قد تحتوي أمثلة دالة أقرب سلسلة نصية على معلومات غير أساسية للمسألة. بمعنى آخر، تحتوي المدخلات المعتادة لهذه الدالة على معلومات لا تُساهم في صعوبة المسألة. على سبيل المثال، إذا احتوت بعض السلاسل النصية على الحرف "a" ، ولكن لم تحتوي أي منها على الحرف "z" ، فإن استبدال جميع السلاسل التي تحتوي على "a " بالسلاسل التي تحتوي على "z " سيُنتج مثالًا مكافئًا جوهريًا، أي أنه من حل المثال المُعدَّل، يُمكن استعادة الحل الأصلي، والعكس صحيح.

تطبيع المدخلات

عند كتابة جميع سلاسل الإدخال التي تتشارك نفس الطول فوق بعضها البعض، فإنها تُشكّل مصفوفة. ولأنواع معينة من الصفوف نفس التأثير على الحل. على سبيل المثال، قد يؤدي استبدال عمود يحتوي على القيم ( a , a , b ) بعمود آخر ( x , x , y ) إلى سلسلة حل مختلفة، ولكنه لا يؤثر على قابلية الحل، لأن كلا العمودين يُعبّران عن نفس البنية، أي أن أول قيمتين متساويتان، ولكنهما مختلفتان عن القيمة الثالثة.

يمكن تطبيع بيانات الإدخال باستبدال الحرف الأكثر تكرارًا في كل عمود بالحرف "أ" ، والحرف الذي يليه تكرارًا بالحرف "ب" ، وهكذا. وبمعرفة حلٍّ للبيانات المُطَبَّعة، يمكن إيجاد البيانات الأصلية بإعادة تعيين أحرف الحل إلى نسختها الأصلية في كل عمود.

لا يؤثر ترتيب الأعمدة على صعوبة المسألة. بمعنى آخر، إذا قمنا بتبديل جميع سلاسل الإدخال وفقًا لتبديل معين π وحصلنا على سلسلة حل s لتلك الحالة المعدلة، فإن π ⁻¹ ( s ) ستكون حلاً للحالة الأصلية.

مثال

بافتراض وجود ثلاث سلاسل إدخال هي uvwx و xuwv و xvwu ، يمكن كتابة ذلك على شكل مصفوفة كما يلي:

u	v	w	x
x	u	w	v
x	v	w	u

يحتوي العمود الأول على القيم ( u , x , x ). بما أن x هو الحرف الأكثر تكرارًا، نستبدله بـ a ، ونستبدل u ، ثاني أكثر الأحرف تكرارًا، بـ b ، فنحصل على العمود الأول الجديد ( b , a , a ). يحتوي العمود الثاني على القيم ( v , u , v ). كما هو الحال في العمود الأول، نستبدل v بـ a و u بـ b ، فنحصل على العمود الثاني الجديد ( a , b , a ). بتطبيق نفس العملية على جميع الأعمدة، نحصل على المصفوفة المُعَيَّرة.

ب	أ	أ	أ
أ	ب	أ	ب
أ	أ	أ	ج

تقليل البيانات الناتج عن التطبيع

يؤدي توحيد المدخلات إلى تقليل حجم الأبجدية إلى عدد سلاسل الإدخال كحد أقصى. وهذا مفيد للخوارزميات التي تعتمد أوقات تشغيلها على حجم الأبجدية.

قام لي وآخرون بتطوير مخطط تقريبي متعدد الحدود ^{[ 3 ]} وهو غير قابل للاستخدام عمليًا بسبب الثوابت الخفية الكبيرة.

يمكن حل مسألة أقرب سلسلة في${\displaystyle O(kL+kd\cdot d^{d})}$حيث k هو عدد سلاسل الإدخال، وL هو طول جميع السلاسل، و d هي أقصى مسافة مطلوبة من سلسلة الحل إلى أي سلسلة إدخال. ^{[ 4 ]}

تُعدّ مسألة أقرب سلسلة حالةً خاصةً من مسألة أقرب سلسلة فرعية الأكثر عمومية ، والتي تُعتبر أكثر صعوبةً بشكلٍ عام. في حين أن مسألة أقرب سلسلة قابلة للحل باستخدام معلمات ثابتة بعدة طرق، فإن مسألة أقرب سلسلة فرعية تُصنّف ضمن المسائل الصعبة من الفئة W[1] فيما يتعلق بهذه المعلمات.