محاذاة إحصائية سريعة

تبدأ الخوارزمية أولاً بتحديد الاحتمالات اللاحقة للمحاذاة${\displaystyle \mathbb {P} (A|X,Y)}$بين أي سلسلتين عشوائيتين من مجموعة السلاسل المراد محاذاتهما. تعزز الاحتمالات اللاحقة لكل عمود التنبؤ باحتمالية المحاذاة بين زوج من السلاسل، كما تعمل على استبعاد الأعمدة التي قد لا تكون محاذاتها موثوقة. تسمح هذه الاحتمالات أيضًا بالتنبؤ بالتشابه بين أي زوج من السلاسل وتقديره. يُستخدم نموذج ماركوف المخفي القياسي ذو الخمس حالات (Pair HMM) لتحديد هذه الاحتمالات اللاحقة للمحاذاة لأي سلسلتين مُدخلتين. يستخدم نموذج Pair HMM مجموعتين من حالات الحذف (D) والإدراج (I) لمراعاة حذف الرموز وإدراجها بين سلسلتين محاذيتين، ولكنه قد يحتوي أيضًا على ثلاث حالات دون فقدان كبير في الدقة.

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

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

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

تستخدم خوارزمية FSA تقنية تلدين التسلسل للتغلب على هذه المشكلة. تُستخدم الاحتمالات اللاحقة المرتبة مع تقنية تلدين التسلسل لإنشاء محاذاة متعددة. تجد هذه التقنية المحاذاة بين تسلسلين تُقلل المسافة المتوقعة إلى التسلسل الصحيح. في هذه الحالة، تُعرَّف المسافة بين تسلسلين بأنها عدد الأعمدة التي لا يكون فيها الحرف من أحد التسلسلين متماثلًا مع الحرف الموجود في نفس العمود من التسلسل الآخر.

تعتمد تقنية تلدين التسلسل، من خلال تحديد محاذاة ذات أقصر مسافة متوقعة إلى التسلسل الصحيح، على إيجاد المحاذاة ذات أعلى دقة متوقعة. وتعتمد دقة المحاذاة على محاذاة "صحيحة" كمرجع، وتشير إلى نسبة الأعمدة التي تتشابه فيها التسلسلات. تُستخدم هذه الدقة كدالة هدف تبدأ بالتسلسلات غير المحاذية (محاذاة فارغة) وتُحاذي الأحرف في أعمدة مختلفة بناءً على زيادة دقة المحاذاة.

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