المعلوماتية الحيويّة - الجزء الخامس

استمع على ساوندكلاود 🎧

بعد أن تعرَّفْنا على أهم طرق البحث عن السلاسل الجينية غير المعروفةِ في الجينوم المرجعي، سنختتمُ هذا الموضوعَ اليومَ عبر التعرف على طرق المقارنة التقريبية ومقارنة عدةِ سلاسلَ في وقتٍ واحد.

ماذا تعني المطابقة التقريبية ولماذا نحتاج إليها؟

إذا كُنَّا نبحثُ عن السلسلة التالية: ACGCTC

ووجدنا بدلاً منها السلسلة: ACGCAC

فهل يعني هذا أن هذه النتيجة غير مهمة وأن هذه السلسلة لا تنتمي للجينوم الذي نبحث فيه؟

في الحقيقة، هذه النتيجة قد تكون ذاتَ معنىً في الحالات التالية مثلاً:

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

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

أحياناً كذلك يكون للعديد من السلاسل التي تختلف بحرفٍ واحدٍ أو أكثر وظائفُ متشابهة، لنفرضْ مثلاً أننا نبحثُ عن الحمضِ الأميني "البرولين" والذي يُمكن تمثيلُه كما بقيّة الحموض الأمينية بسلسلةٍ من الأحرف التي تعبر عن النكليوتيدات:

سنجدُ أن هذه السلاسل الأربع تُعبِّرُ عن البرولين: CCA، CCC، CCG، CCT.

إذاً سوف نبحث عن السلسلة CCX حيث يمثل X أيَّ حرفٍ ممكن!

يُدعى هذا البحث الذي يسمح بالقليل من الاختلاف، بالمقارنة التقريبية. وقبل البدء به يجب أن نحدِّدَ مقدار الاختلاف الذي نريده، يُدعى هذا بـ "مسافة التعديل" (Edit Distance)، وهي بالنسبة لسلسلتين A وB، أقلُّ عددٍ من التغييرات التي إن قمنا بإجرائها على السلسلة A نحصل على السلسلة B.

لنأخذ المثال التالي:

باعتبار:

فإنَّ أقلَّ عددٍ من التغييرات التي يُمكن أن نقوم بها لتحويل A إلى B هو 2 وذلك عبر تحويل الـ G الأولى إلى C وتحويل الـ C الثانية إلى T (موضّحة بالألوان)، وبالتالي مسافة التعديل هي 2.

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

لنقم بجولةٍ على أهمِّ الخوارزميّاتِ المُستَخدمة:

1- مقارنة السلسلة مع الجينوم خطوةً خطوةً كما في المطابقة التامة:

من أوائل الأفكار التي قد نفكر بها هي تطبيق الخوارزميات السابقة ذاتِها مع السماح بعددٍ من التعديلات يساوي مسافة التعديل المسموحة. لكنّ هذه الطريقة تستغرقُ الكثير من الوقت، ولذلك يتمُّ استخدامُ ما يُعرف بـ "البرمجة الديناميكية" وتطبيق عدّة خوارزميّات لتسريع العملية عبرَ حساب كلِّ خطوةٍ بناءً على الخطوة السابقة، وبالتالي يتمُّ توفيرُ الوقت والمساحة.

2- استخدام المؤتمِتات غيرِ المحدَّدة منتهية الحالات:

وذلك يُشابه ما قُمنا به في حالة المطابقة التامة، لكن في هذه الحالة يتمُّ استخدامُ عدَّة نسخٍ من سلسلة الحالات في المؤتمتة لضبط حالات المطابقة التقريبية. فإن أردنا البحث عن السلسلة ACCA في النص ACTACCA بما يسمحُ بوجود مسافة تعديل تساوي 1، يجب استخدام نسختين من سلسلة الحالات كما يلي:

تدلُّ الأسهمُ مختلفةُ الألوان على إمكانيّةِ الانتقالِ من حالةٍ إلى أُخرى وفق الحرف التالي في السلسلة:

- ننتقلُ وفق السهم الأسود إلى اليمين عند وجود تطابقٍ بين الحرف الحالي في السلسلة والحرف الحالي من النص (الجينوم).

- ننتقل وفق السهم الأخضر عند وجود عدمِ تطابقٍ بين الحرف الحالي في السلسلة والحرف الحالي من النص (الجينوم).

- ننتقل وفق السهم البرتقالي عند وجود حرفٍ زائدٍ في السلسلة عن الجينوم وهو ما يسمى بالإدخال (Insertion) مثل الحالة التالية: السلسلة 1 هي ACTA والسلسلة 2 هي ACA فنقول أنَّ السلسلة الأولى تحتوي إدخالاً يتمثّل بحرف T غيرِ موجودٍ في السلسلة الثانية.

- ننتقل وفق السهم الأزرق عند وجود حرفٍ ناقصٍ في السلسلة عن الجينوم وهو ما يسمى بالحذف (Deletion) إذ يُمكن أن نقول أنَّ السلسلة 2 من المثال السابق تحتوي حذفاً يتمثل بحرف T ينقصها مقارنةً بالسلسلة 1.

يزدادُ عددُ الأسطرِ بازديادِ عددِ الاختلافات المسموحة، أي بزيادة مسافة التعديل، وكُلَّما ظهر اختلافٌ بين السلسلة والجينوم، يتم أخذه بعين الاعتبار وإكمال المقارنة.

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

ماذا عن البحث عن عدة سلاسلَ معاً؟

يُمكن طبعاً القيام بذلك بالبحث عن كلٍّ منها بشكلٍ منفرد، لكنَّ هذا سيستغرق وقتاً طويلاً، لذلك حاول الباحثون إيجاد طُرُقٍ أكثرَ كفاءةً تشمُل الطرق التالية:

1- استخدام المؤتمتاتِ غير المحددة منتهية الحالات:

و ذلك عبر تشكيل مؤتمتةٍ لكلِّ سلسلةٍ وتمريرُ النَّص عليها جميعاً معاً، فإن كانت مجموعة السلاسل التي نريد البحث عنها هي السلاسل التالية: ACA، TGCA، GT، فيمكن تشكيل المؤتمتات التالية:

2- باستخدام خورازمية الانتقال من المؤتمتات غير المحددة منتهية الحالات (NFA) إلى المؤتمتات المحددة منتهية الحالات (DFA) عبر الخوارزمية التي تحدثنا عنها سابقاً وهي خوارزمية Knuth-Morris-Pratt:

ويتمُّ ذلك باختصار عبر بناء شجرةٍ تتضمن كافة السلاسل بحيث يحملُ كُلُّ ضلعٍ فيها حرفاً واحداً، تُدعى هذه البنية الشجرية عندها بالـTrie بدلاً من Tree (الشجرة التي يمكن أن يحمل كل ضلع فيها أكثر من حرف). ويتمُّ بعدَها البدءُ من جذر الشجرة والبحث عن السلاسل المطلوبة ضمن النص. في مثالنا السابق يُمكن بناء البنية التالية:

ثم يتم استخدام خورازمية KMP مع بعض التعديلات لتحديد الانتقال بين الحالات.

ننهي بهذه الخلاصةِ السريعة الحديثَ حول طرق البحث عن سلسلة جينية معينة ضمن الجينوم المرجعي الذي نملكه، وهو من أهم المواضيع التي يعمل عليها باحثو المعلوماتية الحيوية.

سنتطرق في المقال القادم إلى ناحيةٍ أُخرى هامة في هذا المجال وهي كيفية الحصول على الترتيب الصحيح للجينوم بالاعتماد على خوارزميات المعلوماتية الحيوية.

-------------------------------------------------------

المصادر:

[1] Algorithms for Sequence Analysis Lecture Notes- Saarland University

[2] Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences، Navarro،G. and Raffinot،M.