عنقودي

• Clustal : البرنامج الأصلي لمحاذاة التسلسلات المتعددة، الذي أنشأه ديس هيغينز في عام 1988، كان يعتمد على استخلاص شجرة توجيه من تسلسلات ثنائية من الأحماض الأمينية أو النيوكليوتيدات . ^{[ 10 ]}
• ClustalV : الجيل الثاني من برنامج Clustal، صدر عام 1992. وقد أتاح إمكانية إنشاء محاذاة جديدة من المحاذاة الموجودة في عملية تُعرف باسم إعادة بناء الشجرة التطورية. كما أضاف ClustalV خيار إنشاء الأشجار باستخدام طريقة الربط الجواري . ^{[ 7 ]}
• ClustalW : الجيل الثالث، صدر عام 1994. وقد حسّن خوارزمية المحاذاة التدريجية، بما في ذلك خيارات ترجيح التسلسل بناءً على التشابه والاختلاف . بالإضافة إلى ذلك، أضاف خيار تشغيل Clustal في وضع الدُفعات من سطر الأوامر . ^{[ 11 ]}
• ClustalX : تم إصداره في عام 1997، وكان هذا أول إصدار يحتوي على واجهة مستخدم رسومية. ^{[ 9 ]}
• Clustal2 : قام هذا التحديث بتحديث كل من ClustalW و ClustalX بدقة وكفاءة أعلى في عام 2007. ^{[ 12 ]}
• ClustalΩ (Omega) : الإصدار الحالي، الذي تم إصداره في عام 2011. ^{[ 13 ] [ 14 ]}

يقبل هذا البرنامج مجموعة واسعة من تنسيقات الإدخال، بما في ذلك NBRF/ PIR و FASTA وEMBL/ Swiss-Prot وClustal وGCC/MSF وGCG9 RSF وGDE.

يمكن أن يكون تنسيق الإخراج واحدًا أو أكثر مما يلي: Clustal، NBRF/ PIR ، GCG /MSF، PHYLIP ، GDE، أو NEXUS.

يتم عرض نفس الرموز لكل من محاذاة الحمض النووي / الحمض النووي الريبي ومحاذاة البروتين ، لذلك في حين أن الرموز * (النجمة) مفيدة لكليهما، يجب تجاهل رموز الإجماع الأخرى لمحاذاة الحمض النووي / الحمض النووي الريبي.

يمكن للمستخدم تعديل معلمات عقوبة فتح الفجوة وعقوبة تمديد الفجوة.

يستخدم كلا الإصدارين نفس الخوارزمية التقريبية السريعة لحساب درجات التشابه بين التسلسلات، مما ينتج عنه محاذاة ثنائية. تعمل الخوارزمية بحساب درجات التشابه كعدد تطابقات k-tuple بين تسلسلين، مع مراعاة عقوبة الفجوات. كلما زاد تشابه التسلسلات، ارتفعت الدرجة. بعد حساب درجات التسلسلات، يتم إنشاء مخطط شجري باستخدام خوارزمية UPGMA لترتيب محاذاة التسلسلات المتعددة. تتم محاذاة التسلسلات بترتيب تنازلي حسب ترتيب المجموعة. تسمح هذه الخوارزمية بمعالجة مجموعات بيانات ضخمة جدًا وتتميز بالسرعة. مع ذلك، تعتمد السرعة على نطاق تطابقات k-tuple المُختار لنوع التسلسل المحدد. ^{[ 16 ]}

من أبرز الإضافات في ClustalV ميزة محاذاة الملفات التعريفية، وخيارات واجهة سطر الأوامر الكاملة. تتيح ميزة محاذاة الملفات التعريفية للمستخدم محاذاة سلسلتين أو أكثر من المحاذاة السابقة مع محاذاة جديدة، ونقل السلاسل غير المتطابقة (ذات الدرجات المنخفضة) إلى أسفل ترتيب المحاذاة. وهذا يمنح المستخدم خيار إنشاء محاذاة سلاسل متعددة بشكل تدريجي ومنهجي مع تحكم أكبر من الخيار الأساسي. ^{[ 15 ]} كما أن خيار التشغيل من سطر الأوامر يُسرّع عملية محاذاة السلاسل المتعددة. ويمكن تشغيل السلاسل باستخدام أمر بسيط.

clustalv nameoffile . seq

أو

clustalv / infile = nameoffile . seq

سيحدد البرنامج نوع التسلسل الذي يحلله. عند اكتمال البرنامج، تُحفظ مخرجات محاذاة التسلسلات المتعددة، بالإضافة إلى مخطط التفرع، في ملفات بامتداد .aln و .dnd على التوالي. تستخدم واجهة سطر الأوامر المعلمات الافتراضية، ولا تسمح بخيارات أخرى. ^{[ 16 ]}

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

أولًا، تحسب الخوارزمية مصفوفة المسافة بين كل زوج من التسلسلات ( محاذاة التسلسلات الثنائية ). ثانيًا، تستخدم طريقة الربط الجواري تقنية التأصيل من نقطة المنتصف لإنشاء شجرة توجيه شاملة. ^{[ 17 ]} يوضح الشكل على اليمين مخططًا لهذه الطريقة. أخيرًا، تُستخدم شجرة التوجيه كقالب تقريبي لإنشاء محاذاة شاملة.

يبلغ التعقيد الزمني لـ ClustalW${\displaystyle O(N^{2})}$بسبب استخدامها لطريقة الربط بين الجيران.

أضاف ClustalW2 خيارًا لاستخدام خوارزمية UPGMA، وهي أسرع مع أحجام الإدخال الكبيرة. يُستخدم خيار سطر الأوامر التالي لاستخدامها بدلًا من خوارزمية الانضمام المجاورة:

- التجميع = UPGMA

كمثال تقريبي، في حين أن إدخال 10000 تسلسل سيستغرق أكثر من ساعة لعملية الربط بين الجيران، فإن UPGMA سيكملها في أقل من دقيقة.

أضافت ClustalW2 أيضًا ميزة تحسين دقة المحاذاة التكرارية. لا تُحسّن هذه الميزة الكفاءة، ولكنها تُتيح إمكانية زيادة دقة المحاذاة، وهو أمرٌ مفيدٌ للغاية خاصةً مع مجموعات البيانات الصغيرة.

تُفعّل العلامات التالية عملية المحاذاة التكرارية:

- التكرار = محاذاة - التكرار = شجرة - عدد

يُحسّن الخيار الأول عملية المحاذاة النهائية. أما الخيار الثاني فيُدمج المخطط في خطوة المحاذاة التدريجية. ويُحدد الخيار الثالث عدد دورات التكرار، حيث تكون القيمة الافتراضية 3. ^{[ 18 ]}

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

عند مقارنة خوارزميات محاذاة التسلسلات المتعددة في عام 2014، كان ClustalW من أسرعها، حيث حقق نتائج بالدقة المطلوبة. مع ذلك، لم يكن دقيقًا كخوارزميات منافسة تعتمد على الاتساق، مثل T-Coffee. ^{[ 19 ]} من بين MAFFT وT-Coffee وClustal Omega، يتميز ClustalW بأقل دقة في محاذاة التسلسلات الكاملة، لكن دقته لا تزال مقبولة. إضافةً إلى ذلك، كان ClustalW الأكثر كفاءة في استخدام الذاكرة بين الخوارزميات المدروسة. ^{[ 19 ]} وقد ساهمت التحديثات المستمرة للبرنامج في زيادة دقة ClustalW2 مع الحفاظ على هذه السرعة. ^{[ 18 ]}

يحتوي برنامج Clustal Omega على خمس خطوات رئيسية لإنشاء محاذاة التسلسل المتعدد .

1. يتم إنتاج محاذاة ثنائية باستخدام طريقة k-tuple. هذه طريقة استدلالية لا تضمن إيجاد حل أمثل، ولكنها أكثر كفاءة من استخدام البرمجة الديناميكية .
2. يتم تجميع التسلسلات باستخدام طريقة mBed المعدلة. ^{[ 22 ]} تحسب طريقة mBed المسافة بين الأزواج باستخدام تضمين التسلسل.
3. يتم تطبيق طريقة التجميع k -means.
4. يتم إنشاء شجرة توجيهية باستخدام طريقة UPGMA . يوضح الشكل على اليمين هذه العملية على شكل خطوات متعددة لشجرة التوجيه تؤدي إلى إنشاء شجرة توجيهية نهائية واحدة، وذلك بسبب الطبيعة التجميعية لطريقة UPGMA. في كل خطوة (الممثلة بالمعينات في مخطط التدفق)، يتم دمج أقرب مجموعتين. وتتكرر هذه العملية حتى يتم تقييم شجرة نهائية شاملة.
5. يتم إنتاج محاذاة التسلسل المتعدد النهائية باستخدام حزمة HHAlign من HH-Suite باستخدام نموذجين من نماذج ماركوف المخفية (HMM) للملف الشخصي . نموذج ماركوف المخفي للملف الشخصي هو آلة حالة خطية تتكون من سلسلة من العقد، كل منها يتوافق تقريبًا مع موضع (عمود) في المحاذاة التي تم بناؤها منها. ^{[ 23 ]}

التعقيد الزمني لحساب المحاذاة المثلى بدقة لـ${\displaystyle N}$سلاسل من الطول${\displaystyle L}$يكون ${\displaystyle O(L^{N})}$وهو أمرٌ باهظ التكلفة حتى بالنسبة لعدد قليل من التسلسلات. وللتغلب على هذه المشكلة، يستخدم برنامج Clustal Omega نسخةً معدلةً من mBed ذات تعقيدٍ يبلغ${\displaystyle O(N\log N)}$[ ^{22 ] [ 24 ]} ، وينتج أشجار توجيهية بدقة تضاهي دقة تلك الناتجة عن الطرق التقليدية. تُعزى سرعة ودقة أشجار التوجيه في Clustal Omega إلى تطبيق خوارزمية mBed مُعدّلة. كما أنها تُقلل من وقت الحساب ومتطلبات الذاكرة اللازمة لإتمام عمليات المحاذاة على مجموعات البيانات الكبيرة ^.

تُعدّ دقة برنامج Clustal Omega على عدد قليل من التسلسلات، في المتوسط، مشابهة جدًا لدقة برامج محاذاة التسلسلات عالية الجودة. أما على مجموعات البيانات الضخمة للغاية التي تضم مئات الآلاف من التسلسلات المدخلة، فيتفوق Clustal Omega على جميع الخوارزميات الأخرى من حيث الوقت والذاكرة ودقة النتائج. ^{[ 25 ]} وهو قادر على معالجة أكثر من 100,000 تسلسل على معالج واحد في غضون ساعات قليلة.

يستخدم برنامج Clustal Omega حزمة HHAlign من HH-Suite، والتي تُجري محاذاة لنموذجين من نماذج ماركوف المخفية بدلاً من مقارنة نموذجين. يُحسّن هذا من جودة الحساسية والمحاذاة بشكل ملحوظ. ^{[ 25 ]} هذا، بالإضافة إلى طريقة mBed، يمنح Clustal Omega ميزته على برامج محاذاة التسلسلات الأخرى.

في مجموعات البيانات ذات القواعد الطرفية غير المحفوظة، قد يكون Clustal Omega أكثر دقة من Probcons أو T-Coffee ، على الرغم من أن كليهما يعتمد على اتساق البيانات. في اختبار كفاءة البرامج التي تُنتج درجات دقة عالية، كان MAFFT الأسرع، يليه Clustal Omega مباشرةً. كان كلاهما أسرع من T-Coffee، إلا أن MAFFT وClustal Omega يتطلبان ذاكرة أكبر للتشغيل. ^{[ 19 ]}