معلومة

2.6: المحاذاة المتعددة - علم الأحياء

2.6: المحاذاة المتعددة - علم الأحياء



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.

محاذاة ثلاثة متواليات

الآن وقد رأينا كيفية محاذاة زوج من التسلسلات ، فمن الطبيعي توسيع هذه الفكرة إلى مضاعف التسلسلات. كيف يمكننا المضي قدما؟

تذكر أنه عندما نقوم بمحاذاة تسلسلين S و T ، فإننا نختار الحد الأقصى لثلاثة احتمالات للموضع النهائي للمحاذاة (التسلسل T محاذيًا للفجوة ، أو التسلسل S المحاذي للفجوة ، أو التسلسل S المحاذي للتسلسل T):

[F_ {i، j} = max left { start {array} {l}
F_ {i، j-1} + d
F_ {i-1، j} + d
F_ {i-1، j-1} + s left (S_ {i}، T_ {j} right)
نهاية {مجموعة} صحيح. لا يوجد رقم ]

لثلاثة تسلسلات S و T و U ، هناك سبعة احتمالات للموضع النهائي للمحاذاة. أي أن هناك ثلاث طرق للحصول على فجوتين في الموضع النهائي ، وثلاث طرق للحصول على فجوة واحدة ، وطريقة واحدة لمحاذاة التسلسلات الثلاثة جميعها ( left ( left ( begin {array} {l}
3 \
1
نهاية {مجموعة} يمين) + يسار ( تبدأ {مجموعة} {l}
3 \
2
نهاية {مجموعة} يمين) + يسار ( تبدأ {مجموعة} {l}
3 \
3
نهاية {مجموعة} يمين) = 7 يمين) ). قاعدة التحديث الآن:

[F_ {i، j، k} = max left { start {array} {l}
F_ {i-1، j، k} + s left (S_ {i}، -، - right)
F_ {i، j-1، k} + s left (-، T_ {j}، - right)
F_ {i، j، k-1} + s left (-، -، U_ {k} right)
F_ {i-1، j-1، k} + s left (S_ {i}، T_ {j}، - right)
F_ {i-1، j، k-1} + s left (S_ {i}، -، U_ {k} right)
F_ {i، j-1، k-1} + s left (-، T_ {j}، U_ {k} right)
F_ {i-1، j-1، k-1} + s left (S_ {i}، T_ {j}، U_ {k} right)
نهاية {مجموعة} صحيح. لا يوجد رقم ]

حيث s هي الوظيفة التي تصف درجات الفجوة والمطابقة وعدم التطابق.

ومع ذلك ، فإن هذا النهج أسي في عدد التسلسلات التي نقوم بمحاذاة. إذا كان لدينا تسلسل k من الطول (n ) ، فإن حساب المحاذاة المثلى باستخدام مصفوفة البرمجة الديناميكية ذات البعد k تستغرق (O left ((2 n) ^ {k} right) ) الوقت (عامل 2 ناتج عن حقيقة أن k-cube به 2ك الرؤوس ، لذلك علينا أخذ الحد الأقصى 2ك - خلية واحدة مجاورة لكل إدخال في مصفوفة النتيجة). كما يمكنك أن تتخيل ، فإن هذه الخوارزمية سرعان ما تصبح غير عملية مع زيادة عدد التسلسلات.

محاذاة متعددة ارشادية

يُطلق على أحد الأساليب الشائعة الاستخدام لمحاذاة التسلسل المتعدد المحاذاة المتعددة التقدمية. افترض أننا نعرف الشجرة التطورية المرتبطة بكل تسلسل من متوالياتنا. ثم نبدأ بإجراء محاذاة زوجية للتسلسلين الأكثر ارتباطًا. تسمى هذه المحاذاة الأولية محاذاة البذور. ثم ننتقل إلى محاذاة أقرب تسلسل تالي للبذرة ، وهذه المحاذاة الجديدة تحل محل البذرة. تستمر هذه العملية حتى يتم إنتاج المحاذاة النهائية.

من الناحية العملية ، لا نعرف عمومًا الشجرة التطورية (أو شجرة الدليل) ، وعادةً ما يتم إقران هذه التقنية بنوع من خوارزمية التجميع التي قد تستخدم مقياس تشابه منخفض الدقة لإنشاء تقدير للشجرة.

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

لاحظ أننا لم نوضح بعد كيفية محاذاة تسلسل مقابل محاذاة موجودة. تتمثل إحدى الطرق الممكنة في إجراء محاذاة زوجية للتسلسل الجديد مع كل تسلسل موجود بالفعل في محاذاة البذور (نفترض أن أي موضع في المحاذاة الأولية التي هي بالفعل فجوة ستبقى واحدة). ثم يمكننا إضافة التسلسل الجديد إلى محاذاة البذور بناءً على أفضل محاذاة ثنائية (تم وصف هذا النهج مسبقًا بواسطة Feng و Doolittle [4]). بدلاً من ذلك ، يمكننا استنباط وظيفة لتسجيل محاذاة تسلسل مع محاذاة أخرى (غالبًا ما تستند وظائف التسجيل هذه على مجموع الدرجات الزوجي في كل موضع).

يعد تصميم أدوات محاذاة التسلسل المتعددة الأفضل مجالًا نشطًا للبحث. يوضح القسم 2.7 بعض الأعمال الحالية في هذا المجال.


شاهد الفيديو: تصنيف الكائنات الحية و أهمية علم التصنيف و تاريخه ومستويات التصنيف الحديث (أغسطس 2022).