تُعدُّ معرفة الترتيب الصحيح للجينوم إحدى أهم الأهداف لخبراء المعلوماتية الحيوية الذين يتنافسون على تطوير الخوارزميات الأكثر سرعة وفعالية لتحقيق هذا الهدف.
عندما نمتلك قطع الجينوم هناك سبيلان يمكن عن طريقِهما التوصُّلُ إلى الترتيب الصحيح له:
1- بالاعتماد على جينوم مرجعي:
وهو أن نمتلك جينوماً مرتباً بشكلٍ صحيح (كالذي حصلنا عليه من مشروع الجينوم البشري بين العامين 1989 و2001) ثُمَّ نقوم بترتيب قطع الجينوم التي نملكها بالاعتماد على هذا الجينوم المرجعي.

2- ترتيب الجينوم دون أيِّ معلوماتٍ مُسبقة باستخدام de novo assembly:
ويتم ذلك بالاعتماد على السلاسل المتداخلة. مثلاً إن كان لدينا السلسلتان ACGTGT وTGTAACA، يُمكن ملاحظة أنَّ السلسلة الأولى تنتهي بـTGT والثانية تبدأ بـTGT أيضاً، وبالتالي يمكن استنتاج السلسلة: ACGTGTAACA.

لتسهيل العمل في ترتيب الجينوم، يتم تشكيلُ رسمٍ بيانيٍّ من هذه السلاسل ويمكن فعل ذلك بطريقين:
1- بناء الرسم البياني المعتَمِد على مسار هاملتون (بيان التداخل Overlap Graph):
إن كان لدينا مجموعة من السلاسل التي نريد ترتيبها، وكانت كلُّ سلسلةٍ تمثّلُ عقدةً في الرسم البياني وتوجد أضلاعٌ تربط بينها، فإنَّ الطريق الذي يمر من كافة العقد، بأن يمر من كلِّ عقدةٍ مرةً واحدةً فقط يدعى مسار هاملتون. كمثال المخطط التالي:


Image: syr-res.com

يمتلك هذا المخطط مسار هاملتون ممثَّلاً باللون الأزرق:


Image: syr-res.com

بعد إيجاد السبيل، يتم بناء المخطط بناءً على تداخل السلاسل ويدعى بمخطط التداخل، وإن حساب هذا السبيل مكلفٌ حسابياً.

2-بناء الرسم البياني المعتمد على مسار أويلر (بيان دي بروين De Bruijn Graph):
بأخذ المثال السابق فإن المسار الذي يمر عبر كلِّ ضلعٍ مرةً واحدة يدعى بمسار أويلر، ويمكن إيجاده في مثالنا السابق (اتبع الأسهم وترتيب الأرقام):


Image: syr-res.com

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


Image: syr-res.com

يمكن أن نحاول الحصول على ترتيبِ هذه القطع وبالتالي الجينوم كما تكلمنا مسبقاً، عبر محاولة إيجاد التداخل بين القطع لنحصل على الشكل التالي:


Image: syr-res.com

بالتالي يمكن استنتاج الترتيب الأصلي للجينوم:


Image: syr-res.com

مع ملاحظة أنَّ القطع الملونة تمثل احتمالين لم نتمكن من معرفة الصحيح بينهما.

أما إن أردنا بناء مخطط دي بروين من هذه القطع، نقوم أولاً بتقطيعها إلى قطع متساوية الطول k، و ليكن k=4، بأن تكون آخر k-1=3 أحرف من القطعة الأولى تطابق أول 3 أحرف من الثانية. لنأخذ مثالاً:
نأخذ القطعة TGAAC، سنحصل منها على القطع التالية: TGAA، GAAC.
وهكذا بتطبيق هذه العملية على كافة القطع، سنحصل على القطع التالية:


Image: syr-res.com

يمكننا الآن بناء مخطط دي بروين:


Image: syr-res.com

يتم الآن العمل على تحسين هذا المخطط كما يلي:
1- تجميع السلاسل التي تملك احتمالاً واحداً:
ليصبح المخطط كما يلي:


Image: syr-res.com

2- التخلص من الاحتمالات المختلفة في السلاسل الطرفية ما يسمى بـ Tips:
في حالتنا نلاحظ وجود سلسلتين CCTG وACTG ويجب اختيار أحدهما لتبدأ السلسلة الكاملة بـ C أو A، هنا يمكن الاختيار حسب الحرف الأكثر تكراراً، ما يسمى بالتغطية Coverage، ولتكن في حالتنا السلسلةُ الأكثر تكراراً هي CCTG. ليصبح المخطط بالشكل التالي:


Image: syr-res.com

3- التخلص من الاحتمالات المختلفة في وسط المخطط، ما يسمى بالفقاعات Bubbles:
وفي حالتنا نلاحظ وجود احتمالين للعبور وسط المخطط ويجب اختيار إما CA أو TG. ويتم ذلك أيضاً عبر مفهوم التغطية Coverage. وليكن في حالتنا وجدنا أن السلسلة AATTGTGC هي الأكثر وروداً فيتم اختيارها ليصبح المخطط بالشكل التالي:


Image: syr-res.com

وهكذا نكون قد حصلنا على الترتيب الصحيح للجينوم:
CCTGCTGGACATAAACCAATTGTGCTGTACTGTAG

تعرَّفنا من خلال هذا المقال على أهم النقاط المتعلقة بمخطط دي بروين واستخدامه في المعلوماتية الحيوية. نتمنّى أن تكونوا قد استمتعتم واستفدتم من هذه السلسلة الشيّقة!

-------------------------------------------------------------------------------------------------
المصادر:
[1] Algorithms for Sequence Analysis Lecture Notes- Saarland University
[2] هنا
[3] هنا

-------------------------------------------------------------------------------------------------
المقالات السابقة من هذه السلسلة:

هنا
هنا
هنا
هنا
هنا