معلومة

2.3: صيغ المشكلة - علم الأحياء

2.3: صيغ المشكلة - علم الأحياء


We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

في هذا القسم ، نقدم مشكلة بسيطة ونحللها ونزيد من تعقيدها بشكل متكرر حتى تشبه إلى حد بعيد مشكلة محاذاة التسلسل. يجب النظر إلى هذا القسم كإحماء للقسم 2.5 في خوارزمية Needleman-Wunsch.

الصيغة 1: أطول سلسلة فرعية مشتركة

كمحاولة أولى ، لنفترض أننا نتعامل مع متواليات النيوكليوتيدات كسلاسل فوق الأبجدية A و C و G و T. بالنظر إلى اثنين من هذه السلاسل ، S1 و S2 ، فقد نحاول مواءمتها من خلال إيجاد أطول سلسلة فرعية مشتركة بينهما. على وجه الخصوص ، لا يمكن أن تحتوي هذه السلاسل الفرعية على فجوات فيها.

على سبيل المثال ، إذا كانت S1 = ACGTCATCA و S2 = TAGTGTCA (راجع الشكل 2.4) ، فإن أطول سلسلة فرعية مشتركة بينهما هي GTCA. لذلك في هذه الصيغة ، يمكننا محاذاة S1 و S2 مع أطول سلسلة فرعية مشتركة بينهما ، GTCA ، للحصول على أكبر عدد من التطابقات. قد تكون الخوارزمية البسيطة هي محاولة محاذاة S1 مع إزاحات مختلفة لـ S2 وتتبع أطول سلسلة فرعية تم العثور عليها حتى الآن. لاحظ أن هذه الخوارزمية تربيعية في طول أقصر تسلسل ، وهو أبطأ مما نفضله لمثل هذه المشكلة البسيطة.

الصيغة 2: أطول نتيجة مشتركة (LCS)

صيغة أخرى هي السماح للفجوات في تكراراتنا اللاحقة وليس فقط حصر أنفسنا في سلاسل فرعية بدون فجوات. بالنظر إلى التسلسل ، ( mathrm {X} = left (x_ {1} ، ldots ، x_ {m} right) ) نحدد رسميًا (Z = left (z_ {1} ، ldots ، z_ {k} right) ) لتكون نتيجة لاحقة لـ X إذا كان هناك تسلسل متزايد بشكل صارم (i_ {1}

في أطول مشكلة لاحقة شائعة (LCS) ، حصلنا على تسلسلين X و Y ونريد إيجاد الحد الأقصى للطول المشترك التالي Z. ضع في اعتبارك مثال المتواليات S1 = ACGTCATCA و S2 = TAGTGTCA (راجع الشكل 2.5) . أطول سلسلة لاحقة شائعة هي AGTTCA ، وهي تطابق أطول من مجرد أطول سلسلة فرعية مشتركة.

الصيغة 3: محاذاة التسلسل كتحرير المسافة

صياغة

صيغة LCS السابقة قريبة من مشكلة محاذاة التسلسل الكامل ، ولكن حتى الآن لم نحدد أي وظائف تكلفة يمكنها التفريق بين الأنواع الثلاثة لعمليات التحرير (الإدراج والحذف والاستبدال). ضمنيًا ، كانت دالة التكلفة لدينا موحدة ، مما يعني أن جميع العمليات متساوية في الاحتمال. نظرًا لأن الاستبدالات أكثر احتمالًا ، فنحن نرغب في تحيز حل LCS الخاص بنا باستخدام دالة التكلفة التي تفضل الاستبدالات على عمليات الإدراج والحذف.

نحن نعيد صياغة محاذاة التسلسل كحالة خاصة لتحرير المسافة الكلاسيكية6 مشكلة في علوم الكمبيوتر (CLRS 366). نضيف عقوبات مختلفة لعمليات التحرير المختلفة لتعكس الأحداث البيولوجية. أحد الأسباب البيولوجية لقرار التسجيل هذا هو احتمالات نسخ القواعد بشكل غير صحيح أثناء البلمرة. من بين قواعد النوكليوتيدات الأربعة ، A و G عبارة عن بورينات (أكبر ، حلقتان مدمجتان) ، بينما C و T هما بيريميدين (أصغر ، حلقة واحدة). وهكذا بوليميريز الحمض النووي7 من المرجح أن يخلط بين اثنين من البيورينات أو اثنين من بيريميدينات لأنها متشابهة في التركيب. نموذج مصفوفة الدرجات في الشكل 2.6 الاعتبارات المذكورة أعلاه. لاحظ أن الجدول متماثل - وهذا يدعم التصميم القابل للانعكاس بمرور الوقت.

يتطلب حساب الدرجات التناوب بين التفسير الاحتمالي لعدد المرات التي تحدث فيها الأحداث البيولوجية والتفسير الحسابي لتعيين درجة لكل عملية. تكمن المشكلة في العثور على تسلسل العملية الأقل تكلفة (حسب مصفوفة التكلفة) والذي يمكن أن يحول تسلسل النوكليوتيدات الأولي إلى تسلسل النوكليوتيدات النهائي.

تعقيد تحرير المسافة

تعمل جميع الخوارزميات لحل مسافة التحرير بين سلسلتين في وقت قريب من كثير الحدود. في عام 2015 ، باكورس وإنديك [؟ ] نشر دليلًا على أن مسافة التحرير لا يمكن حلها بشكل أسرع من (O left (n ^ {2} right) ) في الحالة العامة. تعتمد هذه النتيجة على فرضية الوقت الأسي القوي (SETH) ، والتي تنص على أنه لا يمكن حل مشكلات NP المكتملة في وقت مضاعف في الحالة الأسوأ.

2.3.4 الصياغة 4: نماذج تكلفة فجوة متنوعة

من الناحية البيولوجية ، فإن تكلفة إنشاء فجوة تكون أكثر تكلفة من تكلفة توسيع الفجوة التي تم إنشاؤها بالفعل. وبالتالي ، يمكننا إنشاء نموذج يراعي هذا التباين في التكلفة. هناك العديد من هذه النماذج التي يمكننا استخدامها ، بما في ذلك ما يلي:

• عقوبة الفجوة الخطية: التكلفة الثابتة لجميع الفجوات (نفس الصيغة 3).
• جزاء فجوة صغيرة: افرض تكلفة أولية كبيرة لفتح فجوة ، ثم تكلفة إضافية صغيرة لكل امتداد فجوة.

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

• جزاء الفجوة مع مراعاة الإطار: قم بتخصيص دالة التكلفة لتأخذ في الاعتبار الاضطرابات التي تحدث في إطار التشفير (تؤدي التحولات التي تسبب تحولات الإطار في العناصر الوظيفية عمومًا إلى تعديلات نمطية مهمة).

2.3.5 العد

تذكر أنه من أجل حل صياغة أطول سلسلة فرعية مشتركة ، يمكننا ببساطة تعداد جميع المحاذاة الممكنة وتقييم كل منها واختيار الأفضل. كان هذا بسبب وجود محاذاة O (n) للسلسلتين فقط. بمجرد أن نسمح بوجود فجوات في مواءمتنا ، لم يعد هذا هو الحال. من المعروف أنه لا يمكن تعداد جميع المحاذاة الفراغية الممكنة (على الأقل عندما تكون التسلسلات طويلة). على سبيل المثال ، مع وجود تسلسلين بطول 1000 ، يتجاوز عدد المحاذاة الممكنة عدد الذرات في الكون.

بالنظر إلى مقياس لتسجيل محاذاة معينة ، تعدد خوارزمية القوة الغاشمة البسيطة جميع المحاذاة الممكنة ، وتحسب درجة كل منها ، وتختار المحاذاة مع الحد الأقصى للدرجة. هذا يؤدي إلى السؤال ، "كم عدد المحاذاة الممكنة هناك؟" إذا كنت تفكر فقط في الدوري الاميركي للمحترفين8 ن> م ، عدد المحاذاة

[ left ( start {array} {c}
ن + م
م
نهاية {مجموعة} يمين) = فارك {(n + m)!} {n! m!} almost frac {(2 n)!} {(n!) ^ {2}} almost frac { sqrt {4 pi n} frac {(2 n) ^ {2 n}} {e ^ {2 n}}} {( sqrt { left.2 pi n frac {(n) ^ {n}} {e ^ {n}} right) ^ {2}}} = فارك {2 ^ {2 n}} { sqrt { pi n}} ]

ينمو هذا الرقم بسرعة كبيرة ، وبالنسبة لقيم n حيث أن 30 الصغيرة تكون كبيرة جدًا (> 1017) لتكون استراتيجية العد هذه مجدية. وبالتالي ، فإن استخدام خوارزمية أفضل من القوة الغاشمة يعد ضرورة.


6 تعد مسافة التحرير أو مسافة ليفنشتاين مقياسًا لقياس مقدار الاختلاف بين تسلسلين (على سبيل المثال ، تمثل مسافة ليفينشتين المطبقة على سلسلتين الحد الأدنى لعدد التعديلات اللازمة لتحويل سلسلة إلى أخرى).

7 بوليميراز DNA هو إنزيم يساعد على نسخ خيط DNA أثناء النسخ المتماثل.

8 محاذاة غير مملة ، أو محاذاة حيث تقترن الفجوات دائمًا بالنيوكليوتيدات.


شاهد الفيديو: الأحياء - 3ث - الدعامة والحركة: الحركة الدورانيه للسيتوبلازم (ديسمبر 2022).