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

لنفترض أنّنا نملكُ السّلسلةَ ACGT ونريدُ التَّحقُّقَ من وجودِها في السّلسلةِ التّالية:
ATTGCACGTGA
إنَّ الحلَّ البديهيَّ هو أن نقومَ بمقارنةِ السّلسلةِ الأولى مع كلِّ 4 حروفٍ من السّلسلةِ الثّانية كما يلي:


Image: syr-res.com

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

لقد استغرقت العمليّةُ 6 خطواتٍ لنجدَ السّلسلةَ، فهل من أفكارٍ لتسريعِ البحث؟
هناك بالفعلِ العديدُ من الأفكارِ ولنبدأ بالخوارزميّةِ الأولى الّتي تعتمدُ على تحريكِ نافذةِ المقارنةِ بشكلٍ أسرعَ:
في التّجربةِ السّابقةِ كنّا نقومُ بتحريكِ نافذةِ المقارنةِ بمقدارِ حرفٍ واحدٍ في كلِّ مرّةٍ، لكن في الحقيقةِ يمكن تسريعُ هذه العمليّةِ عبرَ تحريكها لمسافةٍ أطولَ، لنعد إلى مثالنا السّابق: في المقارنةِ الثّانيةِ كنّا نقارنُ السّلسلةَ المطلوبةَ مع السّلسلةِ TTGC، لكنَّ السّلسلةَ المطلوبةَ لا تبدأ أصلاً بـT، فهذه المقارنة إذاً بلا فائدةٍ و يمكنُ تجاوزُها ما يجعلُ العمليّةَ أسرعَ.
فإذاً كيف نعرفُ مقدارَ التّجاوزِ الّذي يمكنُ القيامَ به؟ يتمُّ ذلكَ عبرَ عدَّةِ خوارزميّاتٍ من ضمنِها خوارزميّاتُ هورسبول Horspool الّتي تنصُّ على ما يلي:
يتعلَّقُ مقدارُ التّجاوزِ (الإزاحةِ) بالحرفِ الأخيرِ من النّافذةِ، إذ يتمُّ بدايةً دراسةُ السّلسلةِ المطلوبةِ وبناءُ جدولٍ يُوضِّحُ مقدارَ الإزاحةِ المُمكنةِ بالنّسبةِ لكلِّ حرفٍ إذا تواجَدَ في الموقعِ الأخيرِ من النّافذةِ. لنوضِّحَ ذلكَ بالمثالِ التّالي:
للبحثِ عن السّلسلةِ التّاليةِ CAAAAC ضمنَ السّلسلةَ AC CTACGAGCAAAAC
نقومُ ببناءِ الجدولِ بالطّريقةِ التّاليةِ: بدايةً نُحدِّدُ مقدارَ الإزاحةِ لجميعِ الأحرفِ بطولِ السّلسلةِ الكاملِ وهو 6، ثمَّ نقومُ باستكشافِ السّلسلةِ حرفاً حرفاً باستثناءِ الحرفِ الأخيرِ ونُنْقِصُ مقدارَ الإزاحةِ للحرفِ الحاليِّ، في مثالنا نقومُ أولًا بتحديدِ مقدارِ الإزاحةِ بـ 6 للجميع:


Image: syr-res.com

الآنَ نبدأُ استكشافَ السّلسلةِ والحرفِ الأوّلِ هو C لذلكَ يُصبحِ مقدارَ الإزاحةِ لـ C يعادلُ (طولَ السّلسلةِ - الموضعُ الحاليُّ للحرفِ -1) أي 6-0-1=5 لأنّ الموضعَ الأوّلَ هو 0:


Image: syr-res.com

الحرفُ التّالي هو A لذلك يصبحُ مقدارُ الإزاحةِ له 6-1-1=4:


Image: syr-res.com

و الأحرفُ الثّلاثةِ التّالية هي AAA لذلكَ نكرّرُ الخطوةَ السّابقةَ ليُصبحَ الجدولُ كالتّالي:


Image: syr-res.com

نتوقفُ عند الحرفِ الأخيرِ من السّلسلةِ ولا نُجري عليه الحساباتِ السّابقة.
لقد أصبح الجدولُ جاهزًا، يمكننا الآنَ معرفةُ مقدارِ الإزاحةِ وفقًا للحرفِ الأخيرِ من النّافذةِ، فإن كان C يمكننا إزاحةُ السّلسلةِ 5 حروفٍ إلى اليمينِ لأنَّ الحرفَ C لن يتكرَّرَ في السّلسلةِ إلّا بعد 5 خطواتٍ فيمكنُ تجاوزَ المقارنةِ بأمانٍ إلى ذلكَ الحينِ !
لنُطبِّقَ ذلكَ على المثال:


Image: syr-res.com

الحرفُ الأخيرُ في النّافذةِ هو C وبالعودةِ إلى الجدولِ يمكننا إزاحةُ النّافذةِ بمقدارِ 5 حروفٍ:


Image: syr-res.com

الحرفُ الأخيرُ في النّافذةِ هو A وبالعودةِ إلى الجدولِ يمكننا إزاحةُ النّافذةِ بمقدارِ حرفٍ واحدٍ:


Image: syr-res.com

الحرفُ الأخيرُ في النّافذةِ هو A وبالعودةِ إلى الجدولِ يمكننا إزاحةُ النّافذةِ بمقدارِ حرفٍ واحدٍ:


Image: syr-res.com

الحرفُ الأخيرُ في النّافذةِ هو A وبالعودةِ إلى الجدولِ يمكننا إزاحةُ النّافذةِ بمقدارِ حرفٍ واحدٍ:


Image: syr-res.com

الحرفُ الأخيرُ في النّافذةِ هو A وبالعودةِ إلى الجدولِ يمكننا إزاحةُ النّافذةِ بمقدارِ حرفٍ واحدٍ:


Image: syr-res.com

تمَّ إيجادُ السّلسلةِ وذلكَ عبرَ 5 إزاحاتٍ للنّافذةِ بدلًا من 10.
تُعدُّ هذه الطّريقةُ سريعةً وفعّالةً للنُّصوصِ الطّويلةِ ذاتِ الحروفِ الكثيرةِ، وهناكَ العديدُ من الخوارزميّاتِ الّتي تعملُ بنفسِ الطّريقةِ وتختلفُ بطريقةِ تكوينِ جدولِ الإزاحةِ مثلَ خوارزميّةِ Sunday الّتي تنظرُ إلى الحرفِ الّذي يلي النّافذةَ إلى اليمينِ بدلًا من الحرفِ الأخيرِ فيها لتحديدِ مقدارِ الإزاحةِ.

كانت هذه إحدى طرقِ تسريعِ البحثِ، سنتحدَّثُ في المقالِ القادمِ عن الطّريقةِ التّاليةِ لتسريعِ البحثِ وجعلِهِ أكثرَ كفاءًة، وهي تعتمدُ على تمثيلِ الأحرفِ بنقاطٍ (عُقَدٍ) والانتقالِ بينها وفقَ نظامٍ يُعرفُ بـ "المؤتمتاتِ المُحدَّدةِ منتهيةِ الحالاتِ"، كونوا معنا في المقالِ القادمِ!

------------------------------------------------------------------------
المصادر:
Algorithms for Sequence Analysis Lecture Notes- Saarland University
Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences، Navarro،G. and Raffinot،M.