معلومة

ما هو الاستخدام الآخر لرسومات de Bruijn البيانية في المعلوماتية الحيوية باستثناء تجميع الحمض النووي؟

ما هو الاستخدام الآخر لرسومات de Bruijn البيانية في المعلوماتية الحيوية باستثناء تجميع الحمض النووي؟



We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

لقد قمت بتطبيق رسم بياني عام خاص بـ De Bruijn ، والذي أستخدمه لتجميع الحمض النووي (الأبجدية: A ، C ، G ، T). أحاول أن أجد غرضًا من الرسم البياني لـ De Bruijn لمشاكل أخرى في المعلوماتية الحيوية ، إن وجد بعضها. أريد استخدام / تعديل تطبيقي لحل هذه المشكلة. هل توجد مشاكل أخرى في المعلوماتية الحيوية يمكننا حلها باستخدام الرسوم البيانية لـ de Bruijn؟

لقد وجدت فقط تجميع الحمض النووي الريبي ، والذي يشبه تجميع الحمض النووي.


يقرأ تجميع طويل عرضة للخطأ باستخدام الرسوم البيانية De Bruijn

عندما تم توفير القراءات الطويلة التي تم إنشاؤها باستخدام تقنية se-quencing (SMS) أحادية الجزيء ، كان معظم الباحثين متشككين بشأن قدرة الخوارزميات الحالية على إنشاء تجميعات عالية الجودة من قراءات طويلة عرضة للخطأ. ومع ذلك ، أدت الاختراقات الحسابية الحديثة إلى العديد من مشاريع تسلسل الرسائل القصيرة الناجحة. ومع ذلك ، كما توضح التجميعات الحديثة لمسببات الأمراض النباتية المهمة ، فإن مشكلة تجميع القراءات الطويلة المعرضة للخطأ بعيدة كل البعد عن الحل حتى في حالة الجينومات البكتيرية القصيرة نسبيًا. نقترح نهجًا خوارزميًا لتجميع القراءات الطويلة المعرضة للخطأ ووصف مُجمّع ABruijn ، والذي ينتج عنه عمليات إعادة بناء دقيقة للجينوم.


أويلر ، ل. Commentarii Academiae Scientiarum Petropolitanae 8, 128–140 (1741).

سكينا ، س. دليل تصميم الخوارزمية (سبرينغر ، برلين ، 2008).

لاندر ، إي وآخرون. طبيعة سجية 409, 860–921 (2001).

فينتر ، جي سي وآخرون. علم 291, 1304–1351 (2001).

Kececioglu، J. & amp Myers، E. الخوارزمية 13, 7–51 (1995).

آدامز ، م وآخرون. علم 287, 2185–2195 (2000).

Fleischmann ، R. et al. علم 269, 496–512 (1995).

Schatz، M.، Delcher، A. & amp Salzberg، S. الدقة الجينوم. 20, 1165–1173 (2010).

Bandeira، N.، Pham، V.، Pevzner، P.، Arnott، D. & amp Lill، J. نات. التكنولوجيا الحيوية. 26, 1336–1338 (2008).

Pham، S. & amp Pevzner، P.A. المعلوماتية الحيوية 26, 2509–2516 (2010).

غرابير ، إم وآخرون. نات. التكنولوجيا الحيوية. 29, 644–652 (2011).

دي بروين ، ن. بروك. نديرل. العقاد. ويتينش. 49, 758–764 (1946).

Idury، R. & amp Waterman، M. J. كومبوت. بيول. 2, 291–306 (1995).

بيفزنر ، با ، تانغ ، إتش آند ووترمان ، إم. بروك. ناتل. أكاد. علوم. الولايات المتحدة الأمريكية 98, 9748–9753 (2001).

بيفزنر ، با ، تانغ ، إتش آند تيسلر ، جي. الدقة الجينوم. 14, 1786–1796 (2004).

تشيسون ، إم آند بيفزنر ، ب. الدقة الجينوم. 18, 324–330 (2008).

Zerbino، D. & amp Birney، E. الدقة الجينوم. 18, 821–829 (2008).

بتلر ، جيه وآخرون. الدقة الجينوم. 18, 810–820 (2008).

Simpson، J. et al. الدقة الجينوم. 19, 1117–1123 (2009).

لي ، آر وآخرون. الدقة الجينوم. 20, 265–272 (2010).

Paszkiewicz ، K. & amp Studholme ، D. نبذة. بيوينفورم. 11, 457–472 (2010).

ميلر ، ج. ، كورين ، إس. & أمبير ؛ ساتون ، ج. علم الجينوم 95, 315–327 (2010).

Drmanac ، R. ، Labat ، I. ، Brukner ، I. & amp Crkvenjakov ، R. علم الجينوم 4, 114–128 (1989).

طلب براءة اختراع جنوب المملكة المتحدة gb8810400 (1988).

ليسوف ، واي وآخرون. أكاديمية Doklady Nauk اتحاد الجمهوريات الاشتراكية السوفياتية 303, 1508–1511 (1988).

بيفزنر ، ب. J. بيومول. هيكل. دين. 7, 63–73 (1989).


رسم بياني De-Bruijn مع إطار MapReduce لتصنيف البيانات الميتاجينومية

تصنيفات الجينات الميتاجينومية مهمة في المعلوماتية الحيوية وأبحاث البيولوجيا الحاسوبية. هناك مجموعات بيانات ضخمة مترابطة تتعامل مع الخصائص البشرية والأمراض والوظائف الجزيئية. يعد تحليل إعادة التنظيم الميتاجينومي مشكلة صعبة بسبب تنوعها وأدوات التصنيف الفعالة. يمكن لنهج MapReducing المستند إلى الرسم البياني التعامل بسهولة مع التنوع الجيني. يتكون MapReduce من جزأين مثل التعيين والتقليل. في مرحلة رسم الخرائط ، يتم استخدام خوارزمية عودية ساذجة لتوليد K-mers. الرسم البياني De-Bruijn هو تمثيل مضغوط لـ k-mers ويكتشف المسار الأمثل (الحل) لتجميع الجينوم. تم استخدام مقاييس التشابه لإيجاد التشابه بين متواليات الحمض النووي الريبي (DNA) De-Oxy. في تقليل الجانب ، يتم استخدام تشابه Jaccard ونقاء التجميع كمصنف لمجموعات البيانات لتصنيف التسلسلات بناءً على تشابهها. يمكن لمرحلة التخفيض تصنيف تسلسل الحمض النووي بسهولة من قاعدة بيانات كبيرة. أظهر التحليل التجريبي المكثف أن تحليل MapReduce القائم على الرسم البياني يولد الحلول المثلى. تم تسجيل ومراقبة تحسينات ملحوظة في الزمان والمكان. أثبتت النتائج أن أداء الإطار المقترح أسرع من SSMA-SFSD عند زيادة العناصر المصنفة. قدمت دقة أفضل لتجميع البيانات الميتاجينومية.


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

مجمعات الخوارزمية الجشعة هي مجمعات تجد أفضلية محلية في محاذاة قراءات أصغر. تتميز مجمعات الخوارزمية الجشعة عادةً بعدة خطوات: 1) حساب المسافة الزوجية للقراءات ، 2) تجميع القراءات بأكبر قدر من التداخل ، 3) تجميع القراءات المتداخلة في contigs أكبر ، و 4) التكرار. لا تعمل هذه الخوارزميات عادةً بشكل جيد لمجموعات القراءة الأكبر ، لأنها لا تصل بسهولة إلى المستوى الأمثل العالمي في التجميع ، ولا تؤدي أداءً جيدًا في مجموعات القراءة التي تحتوي على مناطق تكرار. [1] استخدمت مجمعات تسلسل دي نوفو المبكرة ، مثل SEQAID [2] (1984) و CAP [3] (1992) ، خوارزميات جشعة ، مثل خوارزميات التداخل والتخطيط والتوافق (OLC). تجد هذه الخوارزميات تداخلًا بين جميع القراءات ، وتستخدم التداخل لتحديد تخطيط (أو تبليط) للقراءات ، ثم إنتاج تسلسل إجماعي. بعض البرامج التي تستخدم خوارزميات OLC تتميز بالترشيح (لإزالة أزواج القراءة التي لن تتداخل) وطرق إرشادية لزيادة سرعة التحليلات.

مجمعات طريقة الرسم البياني [4] تأتي في نوعين: خيط ودي بروين. تم تقديم مجمعات طريقة الرسم البياني String Graph و De Bruijn في ورشة عمل DIMACS [5] في 1994 بواسطة Waterman [6] و Gene Myers. [7] مثلت هاتان الطريقتان خطوة مهمة إلى الأمام في تجميع التسلسل ، حيث يستخدم كلاهما خوارزميات للوصول إلى المستوى العالمي الأمثل بدلاً من المستوى المحلي الأمثل. بينما أحرزت كلتا الطريقتين تقدمًا نحو تجميعات أفضل ، أصبحت طريقة الرسم البياني De Bruijn الأكثر شيوعًا في عصر تسلسل الجيل التالي. أثناء تجميع الرسم البياني De Bruijn ، يتم تقسيم القراءات إلى أجزاء أصغر بحجم محدد ، k. ثم يتم استخدام k-mers كعقد في تجميع الرسم البياني. يتم بعد ذلك توصيل العقد التي تتداخل بمقدار ما (بشكل عام ، k-1) بواسطة حافة. سيقوم المُجمِّع بعد ذلك ببناء التسلسلات بناءً على الرسم البياني لـ De Bruijn. عادةً ما تعمل مجمعات الرسم البياني De Bruijn بشكل أفضل على مجموعات القراءة الأكبر من مجمعات الخوارزمية الجشعة (خاصةً عندما تحتوي على مناطق تكرار).

التقنيات مؤلف قدم /

تم تصميم المجمعات المختلفة لنوع مختلف من تقنيات القراءة. عادةً ما تكون القراءات من تقنيات الجيل الثاني (تسمى تقنيات القراءة القصيرة) مثل Illumina قصيرة (مع أطوال 50-200 زوج أساسي) ولديها معدلات خطأ تتراوح بين 0.5 و 2٪ ، مع وجود أخطاء بشكل رئيسي في أخطاء الاستبدال. ومع ذلك ، فإن القراءات من تقنيات الجيل الثالث مثل PacBio وتقنيات الجيل الرابع مثل Oxford Nanopore (تسمى تقنيات القراءة الطويلة) أطول مع أطوال قراءة عادةً بالآلاف أو عشرات الآلاف ولديها معدلات خطأ أعلى بكثير من حوالي 10-20٪ مع وجود أخطاء بشكل رئيسي عمليات الإدراج والحذف. هذا يتطلب خوارزميات مختلفة للتجميع من تقنيات القراءة القصيرة والطويلة.

هناك العديد من البرامج لتجميع تسلسل de novo وتمت مقارنة العديد منها في Assemblathon. Assemblathon هو جهد تعاوني دوري لاختبار وتحسين المجمعات العديدة المتاحة. حتى الآن ، تم الانتهاء من تجمعين (2011 و 2013) والثالث قيد التنفيذ (اعتبارًا من أبريل 2017). فرق من الباحثين من جميع أنحاء العالم تختار برنامجًا وتجمع الجينومات المحاكاة (Assemblathon 1) وجينومات الكائنات الحية النموذجية التي تم تجميعها مسبقًا وتوضيحها (Assemblathon 2). ثم تتم مقارنة التجميعات وتقييمها باستخدام العديد من المقاييس.

Assemblathon 1 تحرير

تم عقد التجمع 1 [22] في عام 2011 وضم 59 تجمعًا من 17 مجموعة مختلفة ومنظمين. كان الهدف من هذا Assembalthon هو تجميع جينوم بشكل كامل ودقيق يتكون من نمطين فرديين (يحتوي كل منهما على ثلاثة كروموسومات 76.3 و 18.5 و 17.7 ميجا بايت على التوالي) تم إنشاؤه باستخدام Evolver. تم استخدام العديد من المقاييس لتقييم التجميعات ، بما في ذلك: NG50 (النقطة التي يتم عندها الوصول إلى 50٪ من إجمالي حجم الجينوم عند جمع أطوال السقالات من الأطول إلى الأقصر) ، LG50 (عدد السقالات التي تكون أكبر من أو تساوي إلى ، طول N50) ، وتغطية الجينوم ، ومعدل خطأ الاستبدال.

  • مقارنة البرامج: ABySS ، Phusion2 ، phrap ، Velvet ، SOAPdenovo ، PRICE ، ALLPATHS-LG
  • تحليل N50: كان أداء التجميعات من قبل مجموعة تجميع الجينوم النباتية (باستخدام المجمع Meraculous) و ALLPATHS ، معهد برود ، الولايات المتحدة الأمريكية (باستخدام ALLPATHS-LG) الأفضل في هذه الفئة ، بترتيب من حيث الحجم على المجموعات الأخرى. سجلت هذه التجميعات N50 من القواعد & GT8،000،000.
  • تغطية الجينوم بالتجميع: بالنسبة لهذا المقياس ، كان أداء تجميع BGI عبر SOAPdenovo أفضل ، حيث تمت تغطية 98.8٪ من إجمالي الجينوم. كان أداء جميع المجمعات جيدًا نسبيًا في هذه الفئة ، مع تغطية جميع المجموعات بنسبة 90٪ فما فوق ، باستثناء ثلاث مجموعات ، وكانت أقل تغطية إجمالية تبلغ 78.5٪ (قسم علوم الشركات ، جامعة شيكاغو ، الولايات المتحدة الأمريكية عبر Kiki).
  • أخطاء الاستبدال: تم إرسال التجميع الذي يحتوي على أقل معدل خطأ في الاستبدال من قبل معهد Wellcome Trust Sanger ، فريق المملكة المتحدة باستخدام برنامج SGA.
  • بشكل عام: لم يكن أداء أحد المجمعين أفضل بشكل ملحوظ في الآخرين في جميع الفئات. في حين أن بعض المجمعات تفوقت في فئة واحدة ، إلا أنها لم تفعل في فئة أخرى ، مما يشير إلى أنه لا يزال هناك مجال كبير لتحسين جودة برامج المجمّع.

Assemblathon 2 تحرير

تم تحسين Assemblathon 2 [23] في Assemblathon 1 من خلال دمج جينومات الفقاريات المتعددة (طائر (Melopsittacus undulatus)، سمكة (حمار وحشي Maylandia) وثعبان (بوا العاصرة)) مع الجينومات المقدرة بـ 1.2 و 1.0 و 1.6 جيجابت في الطول) وتقييمها بأكثر من 100 مقياس. تم منح كل فريق أربعة أشهر لتجميع الجينوم الخاص بهم من بيانات تسلسل الجيل التالي (NGS) ، بما في ذلك بيانات تسلسل Illumina و Roche 454.

  • مقارنة البرامج: ABySS و ALLPATHS-LG و PRICE و Ray و SOAPdenovo
  • تحليل N50: لتجميع جينوم الطيور ، كان لدى مركز تسلسل الجينوم البشري بكلية بايلور للطب وفرق ALLPATHS أعلى NG50s ، بأكثر من 16.000.000 وأكثر من 14.000.000 نقطة أساس ، على التوالي.
  • وجود الجينات الأساسية: كان أداء معظم التجميعات جيدًا في هذه الفئة (


هيكل تعليم إضافي لاجتياز الرسم البياني

العديد من تطبيقات NGS ، على سبيل المثال من جديد تجميع الجينومات [15] والترانسكريبتومات [2] ، و من جديد اكتشاف المتغير [6] ، يعتمد على (1) تبسيط و (2) اجتياز الرسم البياني لـ De Bruijn. ومع ذلك ، فإن الرسم البياني كما هو موضح في القسم السابق لا يدعم (1) التبسيط (لأنه غير قابل للتغيير) ولا (2) اجتياز (حيث لا يمكن لمرشح Bloom تخزين بت إضافي تمت زيارته لكل عقدة). لمعالجة المشكلة السابقة ، نجادل بأنه يمكن تجنب خطوة التبسيط من خلال تصميم إجراء اجتياز أكثر تعقيدًا بقليل [16].

نقدم آلية جديدة وخفيفة الوزن لتسجيل أجزاء الرسم البياني التي تمت زيارتها بالفعل. الفكرة من وراء هذه الآلية هي أنه لا يلزم تمييز كل عقدة. على وجه التحديد ، سيتم وضع علامة على العقد الموجودة داخل مسارات بسيطة (أي العقد التي تحتوي على درجة 1 ودرجة خارجية 1) إما جميعها أو غير محددة. سوف نشير إلى العقد التي تختلف درجتها الجامعية أو الخارجية عن 1 على النحو التالي مركب العقد. نقترح تخزين معلومات تعليم العقد المعقدة ، عن طريق تخزين العقد المعقدة بشكل صريح في جدول تجزئة منفصل. في الرسوم البيانية لجينوم De Bruijn ، فإن المجموعة الكاملة من العقد تقزم مجموعة العقد المعقدة ، لكن النسبة تعتمد على مدى تعقيد الجينوم [17]. استخدام الذاكرة لهيكل الوسم هو نجج، أين نج هو عدد العقد المعقدة في الرسم البياني و ج هو استخدام الذاكرة لكل إدخال في جدول التجزئة (ج≈2ك+8).


بيولوجيا حجم البايت

تقدمت مؤخرًا بطلب للحصول على منحة مؤسسة مور في علوم البيانات للعلوم البيولوجية. كجزء من التطبيق المسبق ، طُلب مني اختيار أفضل 5 أعمال في علم البيانات في مجالي. لست متأكدًا من علم البيانات ، لذلك اخترت ما أعتقد أنه أكثر الأعمال تأثيرًا في المعلوماتية الحيوية ، وهو ما كان يدور حوله اقتراحي. على أي حال ، كان الاختيار صعبًا ، وقد توصلت إلى ما يلي. الترتيب الذي أدرجت به الأعمال هو ترتيب زمني ، حيث إنني لا أحاول ترتيبها. إذا سألتني في التعليقات & # 8220 كيف يمكنك اختيار X على Y؟ & # 8221 سيكون ردي على الأرجح: & # 8220I didn & # 8217t & # 8221.

دايهوف ، M.O. ، Eck RV ، و Eck CM. 1972. نموذج للتغير التطوري في البروتينات. ص. 89-99 بوصة أطلس تسلسل البروتين وهيكله ، المجلد. 5 ، المؤسسة الوطنية للبحوث الطبية الحيوية ، واشنطن العاصمة

ملخص: هذا هو مقدمة لمصفوفة PAM ، الورقة التي مهدت الطريق لفهمنا للتطور الجزيئي على مستوى البروتين ، ومحاذاة التسلسل ، والتفجير الذي نقوم به جميعًا. السؤال المطروح: كيف يمكننا تحديد التغييرات بين تسلسل البروتين؟ كيف يمكننا تطوير نظام يخبرنا ، بمرور الوقت ، بالطريقة التي تتطور بها البروتينات؟ قامت دايهوف بتطوير طريقة إحصائية أنيقة للقيام بذلك ، والتي أطلقت عليها اسم PAM ، & # 8220Accepted Point Mutations & # 8221. قامت بمحاذاة مئات البروتينات واستنبطت التردد الذي تحل به الأحماض الأمينية المختلفة محل بعضها البعض. قدمت دايهوف نسخة أكثر قوة [PDF] في عام 1978 ، بمجرد زيادة عدد البروتينات التي يمكنها استخدامها لحساب عدد كبير من البدائل.

Altschul، S.F.، Madden، T.L.، Schaffer، AA، Zhang، J.، Zhang، Z.، Miller، W. & amp Lipman، D.J. (1997) Gapped BLAST و PSI-BLAST: جيل جديد من برامج البحث في قواعد بيانات البروتين. الدقة الأحماض النووية. 25:3389-3402.

BLAST ، أداة البحث عن المحاذاة المحلية الأساسية هي العمود الفقري الحسابي في علم الأحياء الجزيئي. إنها الورقة الأكثر استشهادًا في علوم الحياة ، لذا فهي على الأرجح الورقة الأكثر تأثيرًا في علم الأحياء اليوم. للمبتدئين: يسمح لك BLAST بأخذ تسلسل من البروتين أو الحمض النووي ، والبحث بسرعة عن تسلسلات مماثلة في قاعدة بيانات تحتوي على الملايين. يستغرق البحث باستخدام تسلسل واحد ثوانٍ أو بضع دقائق في أحسن الأحوال. تم تقديم بلاست في الواقع في ورقة أخرى في عام 1990. ومع ذلك ، فإن الاستدلال الذي تم تطويره هنا سمح بمحاذاة التسلسلات المتقطعة ، والبحث عن متواليات أقل تشابهًا ، مع قوة إحصائية. غيرت بلاست كل شيء في البيولوجيا الجزيئية ، ونقلت علم الأحياء إلى العلوم الغنية بالبيانات. إذا كان هناك أي قضية لمنح جائزة نوبل في علم وظائف الأعضاء أو الطب لشخص حاسوبي ، فإن بلاست هي.

Durbin R. ، Eddy S. ، Krogh A and Mitchison G تحليل التسلسل البيولوجي: النماذج الاحتمالية للبروتينات والأحماض النووية ، مطبعة جامعة كامبريدج 1998

طلب التماس مؤسسة مور & # 8220works & # 8221 بدلاً من & # 8220 أوراق بحثية & # 8221. إذا كان هناك أي شيء مشترك بين جميع مختبرات المعلوماتية الحيوية ، فسيكون هذا الكتاب هو & # 8217. نظرة عامة على طرق تحليل التسلسل الأساسية. تلخص هذه الكتب أساس ما قبل عام 2000 الذي بنيت عليه جميع معارفنا تقريبًا حاليًا: المحاذاة الزوجية ، ونماذج ماركوف ، ومحاذاة التسلسل المتعدد ، والملفات الشخصية ، و PSSM ، وعلم الوراثة.

علم الوجود الجيني: أداة لتوحيد علم الأحياء. اتحاد علم الوجود الجيني (2000) علم الوراثة الطبيعي 25: 25-29

ليست ورقة بحثية ، وليست كتابًا ، ولكنها & # 8220 تعليقًا & # 8221. شاع هذا العمل لاستخدام علم الوجود في المعلوماتية الحيوية وعزز GO باعتباره علم الوجود الرئيسي الذي نستخدمه.

بيفزنر با ، تانغ إتش ، ووترمان مس. نهج مسار أويلر لتجميع أجزاء الحمض النووي. Proc Natl Acad Sci USA. 2001 أغسطس 1498 (17): 9748-53.

تجميع التسلسل باستخدام الرسوم البيانية de-Bruijn ، مما يجعل التجميع قابلاً للتتبع لعدد كبير من التسلسلات. في ذلك الوقت ، لا يزال من الممكن تجميع تسلسلات البنادق التي ينتجها تسلسل سانجر في حل زمني محدود لمسار هاميلتوني. بمجرد أن بدأت بيانات التسلسل من الجيل التالي تتدفق ، أصبح استخدام الرسوم البيانية de-Bruijn ومسار Eulerian ضروريًا. للحصول على شرح رائع للانتقال المنهجي ، راجع هذه المقالة في طبيعة التكنولوجيا الحيويةذ

نعم ، أعلم أن هناك العديد من الأعمال المستحقة غير الموجودة هنا. عند الغليان إلى خمسة ، يكون الاختيار تعسفيًا تقريبًا. إذا شعرت بالإهانة لأن العمل الذي يعجبك ليس هنا ، فأنا آسف.


رسم بياني مضغوط لـ Bruijn

إعطاء سلسلة س من الطول ن وعدد طبيعي ك، الرسم البياني لـ de Bruijn لـ س يحتوي على عقدة لكل طول مميز ك سلسلة فرعية من س، يسمى ب ك-مر. عقدتان ش و الخامس متصلة بواسطة حافة موجهة (ش, الخامس) لو ش و الخامس تحدث على التوالي في س، على سبيل المثال ، (u = S [i..i + k-1] ) و (v = S [i + 1..i + k] ). يوضح الشكل 1 مثالاً. من الواضح أن الرسم البياني يحتوي على الأكثر ن العقد و ن حواف. من خلال البناء ، ستتداخل العقد المجاورة بمقدار (k-1 ) من الأحرف ، ويمكن أن يتضمن الرسم البياني مضاعف حواف تربط نفس زوج العقد أو الحلقات الذاتية التي تمثل تكرارات متداخلة. لكل عقدة ، باستثناء عقدة البداية (التي تحتوي على أول ك شخصيات س) وعقدة الإيقاف (التي تحتوي على آخر ك شخصيات س) ، تتزامن درجة البكالوريوس مع الدرجة العلمية الخارجية. يمكن "ضغط" رسم بياني Bruijn عن طريق دمج سلاسل غير متفرعة من العقد في عقدة واحدة بسلسلة أطول. بتعبير أدق ، إذا كانت العقدة ش هو السلف الوحيد للعقدة الخامس و الخامس هو الوريث الوحيد ل ش (ولكن قد تكون هناك حواف متعددة (ش, الخامس))، من ثم ش و الخامس يمكن دمجها في عقدة واحدة لها أسلاف ش وخلفاء الخامس. بعد ضغط الرسم البياني إلى أقصى حد ، يكون لكل عقدة (بصرف النظر عن عقدة البداية) ما لا يقل عن اثنين من سابقاتها المختلفة أو أن سابقتها المفردة لها على الأقل خليفتان مختلفتان على الأقل وكل عقدة (بصرف النظر عن عقدة التوقف) لها على الأقل اثنين من الخلفات المختلفة أو لها يوجد خلف واحد على الأقل سلفان مختلفان انظر الشكل 1. بالطبع ، يمكن بناء الرسم البياني المضغوط de Bruijn من نظيره غير المضغوط (رسم بياني أكبر بكثير) ، لكن هذا غير ملائم بسبب الاستهلاك الهائل للمساحة. هذا هو السبب في أننا سوف نبنيها مباشرة.

تمثيل صريح لرسم بياني مضغوط لـ Bruijn من الشكل 1

يوضح الشكل 2 كيف يمثل SplitMEM الرسم البياني لـ Bruijn المضغوط جي لـ (k = 3 ) والسلسلة (S = ) ACTACGTACGTACG $. تتوافق كل عقدة مع سلسلة فرعية ( أوميغا ) من س ويتكون من مكونات (هوية شخصية, لين, نقاط البيع, قائمة)، أين هوية شخصية هو رقم طبيعي يحدد العقدة بشكل فريد ، لين هو طول (| omega | ) ( omega ) ، نقاط البيع هي قائمة المواقف التي يحدث فيها ( omega ) س (مرتبة بترتيب تصاعدي) ، و قائمة هي قائمة خلفاء العقدة (مرتبة بطريقة يمكن للمشي خلالها جي ذلك يعطي س يتم إحداثه بواسطة قوائم الجوار: إذا كانت العقدة جي[هوية شخصية] تمت زيارتها من أجل أنا-th مرة ، فإن خليفتها هي العقدة التي يمكن العثور عليها في الموضع أنا في قائمة الجوار جي[هوية شخصية]).

يمكن تصنيف العقد في الرسم البياني المضغوط de Bruijn لعموم الجينوم على النحو التالي:

تمثل العقدة الفريدة سلسلة فرعية فريدة في عموم الجينوم ولها موضع بداية واحد (أي ، نقاط البيع يحتوي على عنصر واحد فقط)

تمثل العقدة المتكررة سلسلة فرعية تحدث مرتين على الأقل في الجينوم الشامل ، إما كتكرير في جينوم واحد أو كقطعة مشتركة بين عدة جينومات.

في تحليل الجينوم الشامل ، س هو عبارة عن سلسلة من التسلسلات الجينومية المتعددة ، حيث يتم فصل التسلسلات المختلفة برمز خاص ( # ). (من الناحية النظرية ، يمكن للمرء استخدام رموز مختلفة زوجية لفصل التسلسلات ، ولكن من الناحية العملية ، قد يؤدي ذلك إلى تفجير الأبجدية.) وهذا له تأثير أن ( # ) قد يكون جزءًا من التكرار. على عكس SplitMEM ، تتعامل الخوارزمية الخاصة بنا مع التكرارات المختلفة لـ ( # ) كما لو كانت أحرفًا مختلفة. وبالتالي ، لن يكون ( # ) جزءًا من التكرار. في نهجنا ، سيكون كل تواجد لـ ( # ) هو نهاية عقدة الإيقاف (على سبيل المثال ، هناك عقدة توقف لكل تسلسل).

وفقًا لـ [5] ، فإن الرسم البياني المضغوط لـ Bruijn هو الأكثر ملاءمة لتحليل عموم الجينوم: "بهذه الطريقة سيتم تمثيل عموم الجينوم الكامل في تمثيل رسومي مضغوط بحيث تكون الحالة المشتركة / الخاصة بالسلالة لأي سلسلة فرعية على الفور يمكن التعرف عليه ، جنبًا إلى جنب مع سياق التسلسلات المرافقة. تتيح هذه الإستراتيجية أيضًا إجراء تحليل طوبولوجي قوي للجينوم الشامل غير ممكن من التمثيل الخطي. " على الرغم من وجود عيب واحد: لا يمكن البحث بكفاءة عن عقد معينة ثم استكشاف الرسم البياني بالقرب من هذه العقد. قد يرغب المستخدم ، على سبيل المثال ، في البحث عن أليل معين في عموم الجينوم و- إذا كان موجودًا- لفحص جوار ذلك الأليل في الرسم البياني. هنا ، نقترح تمثيلًا جديدًا موفرًا للمساحة لرسم بياني مضغوط Bruijn يضيف هذه الوظيفة بالضبط.

نقوم بتخزين الرسم البياني في مصفوفة جي من الطول ن، أين ن هو عدد العقد في الرسم البياني المضغوط لـ de Bruijn. علاوة على ذلك ، نخصص لكل عقدة معرّفًا فريدًا (id in <1، dots، N > ). الأنود جي[هوية شخصية] الآن الشكل ((len، lb، size، <لاحقة> _ lb) ) ، حيث

المتغير لين هو طول السلسلة ( omega = S [ mathsf [lb] .. mathsf [lb] + len-1] ) التي تتوافق مع العقدة ذات المعرف هوية شخصية

([lb..lb + size-1] ) هو ( omega ) - الفاصل الزمني ، رطل هي حدوده اليسرى ، و بحجم هو حجمه

([<لاحقة> _ lb .. <لاحقة> _ lb + size-1] ) هي الفاصل الزمني ل ك طول لاحقة ​​( أوميغا )

هناك استثناء واحد: الحارس $ وكل تكرار للفاصل ( # ) سيكون نهاية عقدة الإيقاف. من الواضح أن اللاحقة $ of س يظهر في الفهرس 1 في مصفوفة اللاحقة لأن $ هو أصغر حرف في الأبجدية. الفاصل الزمني لصفيف اللاحقة $ هو [1..1] ، لذلك قمنا بتعيين (<لاحقة> _ lb = 1 ). بالمثل ، لاحقة س الذي يبدأ بـ ( # ) يظهر في فهرس (j in <2، dots، d > ) في صفيف اللاحقة (حيث (d ) هو عدد التسلسلات في س) لأن ( # ) هو ثاني أصغر حرف في الأبجدية ، لذلك قمنا بتعيين (<لاحقة> _ lb = ي ).

تمثيل ضمني لرسم بياني مضغوط لـ Bruijn من الشكل 1

يوضح الشكل 3 مثالاً. من الآن فصاعدًا ، سيُطلق على هذا التمثيل اسم التمثيل الضمني ، بينما يُطلق على التمثيل من الشكل 2 اسم التمثيل الصريح. من الواضح أنه في التمثيل الضمني ، توجد قائمة بجميع المواقف التي يحدث فيها ( omega ) س يمكن حسابها على النحو التالي: ([ mathsf [i] mid lb le i le lb + size-1] ). سيتم شرح ذلك لاحقًا ، كيف يمكن اجتياز الرسم البياني وكيف يمكن البحث عن نمط. سنرى أنه يمكن القيام بذلك بكفاءة عن طريق المكون الرابع (<لاحقة> _ lb ).


ما هو الاستخدام الآخر لرسومات de Bruijn البيانية في المعلوماتية الحيوية باستثناء تجميع الحمض النووي؟ - مادة الاحياء

المعلوماتية الحيوية ، 32 ، 2016 ، i201 - i208 doi: 10.1093 / المعلوماتية الحيوية / btw279 ISMB 2016

ضغط الرسوم البيانية لـ Bruijn من تسلسل البيانات بسرعة وفي ذاكرة منخفضة Rayan Chikhi1 و * و Antoine Limasset2 و Paul Medvedev3،4،5 1

CNRS ، CRIStAL ، ليل ، فرنسا ، 2ENS Cachan Brittany ، Bruz ، فرنسا ، 3 قسم علوم وهندسة الكمبيوتر ، جامعة ولاية بنسلفانيا ، الولايات المتحدة الأمريكية ، قسم الكيمياء الحيوية والبيولوجيا الجزيئية ، جامعة ولاية بنسلفانيا ، الولايات المتحدة الأمريكية ، ومعهد علوم الجينوم 5 في Huck ، جامعة ولاية بنسلفانيا ، الولايات المتحدة الأمريكية * لمن يجب توجيه المراسلات.

الدافع المجرد: مع زيادة كمية البيانات لكل تجربة تسلسلية ، أصبحت تحديات تجميع الأجزاء حسابية بشكل متزايد. الرسم البياني de Bruijn هو بنية بيانات مستخدمة على نطاق واسع في خوارزميات تجميع الأجزاء ، وتستخدم لتمثيل المعلومات من مجموعة من القراءات. يعد الضغط خطوة مهمة لتقليل البيانات في معظم الخوارزميات القائمة على الرسم البياني لـ Bruijn حيث يتم ضغط المسارات البسيطة الطويلة في رؤوس مفردة. أصبح الضغط مؤخرًا عنق الزجاجة في خطوط أنابيب التجميع ، ويعد تحسين وقت التشغيل واستخدام الذاكرة مشكلة مهمة. النتائج: نقدم خوارزمية وأداة BCALM 2 لضغط الرسوم البيانية لـ de Bruijn. BCALM 2 عبارة عن خوارزمية متوازية توزع المدخلات بناءً على تقنية التجزئة المصغرة ، مما يسمح بتوازن جيد في استخدام الذاكرة طوال تنفيذها. بالنسبة لبيانات التسلسل البشري ، يقلل BCALM 2 العبء الحسابي لضغط الرسم البياني de Bruijn إلى ما يقرب من ساعة و 3 جيجابايت من الذاكرة. طبقنا أيضًا BCALM 2 على مجموعات بيانات تسلسل الصنوبر loblolly 22 جيجابت في البوصة و 20 جيجابت في الثانية. تم إنشاء الرسوم البيانية المضغوطة من قراءات أولية في أقل من يومين و 40 جيجابايت من الذاكرة على جهاز واحد. وبالتالي ، يعد BCALM 2 على الأقل ترتيبًا من حيث الحجم أكثر كفاءة من الطرق الأخرى المتاحة. التوفر والتنفيذ: شفرة المصدر لـ BCALM 2 متاحة مجانًا على: https://github.com/ GATB / bcalm جهة الاتصال: [email & # 160protected]

1 مقدمة يمكن أن تولد تقنية التسلسل الحديثة مليارات القراءات من عينة ، سواء كانت RNA أو DNA الجينومي أو metagenome. في بعض التطبيقات ، يمكن أن يسمح الجينوم المرجعي برسم خرائط لهذه القراءات ، ولكن في كثير من التطبيقات الأخرى ، يكون الهدف هو إعادة بناء contigs الطويل. تُعرف هذه المشكلة باسم تجميع الأجزاء وتظل واحدة من أهم التحديات في مجال المعلوماتية الحيوية. تجميع الأجزاء هو المكون الحسابي المركزي وراء تجميع الجينومات الجديدة ، واكتشاف نسخ الجينات (RNA-seq) (Grabherr et al. ، 2011) ، واكتشاف الأنواع من metagenomes ، ودعوة المتغيرات الهيكلية (Iqbal et al. ، 2012). يمثل التحسين المستمر لتقنيات التسلسل والزيادات في كمية البيانات المنتجة لكل تجربة تحديًا خطيرًا لتجزئة خوارزميات التجميع. على سبيل المثال ، في حين أن هناك العديد من مجمعات الجينوم التي يمكنها تجميع جينومات بحجم البكتيريا ، فإن عدد المجمعات التي يمكنها تجميع جينوم للثدييات عالية الجودة محدود ، حيث تم تطوير معظمها بواسطة فرق كبيرة وتتطلب موارد مكثفة (Gnerre C The Author 2016 تم النشر بواسطة مطبعة جامعة أكسفورد

وآخرون ، 2011 Luo et al. ، 2012 Simpson et al. ، 2009). بالنسبة للجينومات الأكبر ، مثل 20 جيجا بايت Picea glauca (شجرة التنوب البيضاء) ، استغرق إنشاء الرسم البياني والضغط 4.3 تيرابايت من الذاكرة ، و 38 ساعة و 1380 نواة وحدة المعالجة المركزية (بيرول وآخرون ، 2013). في حالة أخرى ، تطلب تجميع الجينوم الكامل لـ 22 جيجابت بينوس تايدا (صنوبر لوبولي) 800 جيجابايت من الذاكرة وثلاثة أشهر من وقت التشغيل على جهاز واحد (Zimin et al. ، 2014). تستخدم معظم خوارزميات تجميع الأجزاء ذات القراءة القصيرة مخطط de Bruijn لتمثيل المعلومات من مجموعة من القراءات. بالنظر إلى مجموعة من القراءات R ، فإن كل k-mer مميز في R يشكل رأسًا للرسم البياني ، بينما تربط الحافة اثنين k-mers إذا تداخلتا مع حرف k - 1. يتكون استخدام الرسم البياني de Bruijn في تجميع الأجزاء من خط أنابيب متعدد الخطوات ، ومع ذلك ، فإن الخطوات الأكثر كثافة للبيانات هي عادةً الخطوات الثلاثة الأولى: تعداد العقد والضغط وتنظيف الرسم البياني. في الخطوة الأولى (تسمى أحيانًا عد k-mer) ، يتم استخراج مجموعة k-mers المميزة من القراءات. في الخطوة الثانية ، يتم ضغط جميع الوحدات (المسارات التي تحتوي جميعها باستثناء الرأس الأول على الدرجة 1 وجميع الرؤوس باستثناء الرأس الأخير الذي له درجة خارجية 1) يتم ضغطها في i201 واحد

هذا مقال مفتوح الوصول يتم توزيعه بموجب شروط الترخيص الإبداعي للإسناد غير التجاري (http://creativecommons.org/licenses/by-nc/4.0/) ، والذي يسمح بإعادة الاستخدام والتوزيع وغير التجاريين الاستنساخ بأي وسيلة ، بشرط الاستشهاد بالعمل الأصلي بشكل صحيح. لإعادة الاستخدام التجاري ، يرجى الاتصال بـ [email & # 160protected]

رأس i202. في الخطوة الثالثة ، تتم إزالة القطع الأثرية الناتجة عن أخطاء التسلسل وتعدد الأشكال من الرسم البياني. يتم أحيانًا تبديل الخطوتين الثانية والثالثة لزيادة ضغط الرسم البياني. بعد هذه الخطوات الأولية ، يتم تقليل حجم البيانات تدريجيًا ، على سبيل المثال لمجموعة بيانات بشرية مع 45 تغطية ، للتغلب على تحديات قابلية التوسع لتجميع أجزاء من مجموعات بيانات التسلسل الكبيرة ، كان هناك تركيز على تحسين استخدام الموارد لبناء الرسم البياني de Bruijn. على وجه الخصوص ، شهد عد k-mer تحسينات كبيرة في استخدام الذاكرة وسرعتها. نتيجة لذلك ، أصبح ضغط الرسم البياني هو عنق الزجاجة الجديد ولكنه لم يحظ باهتمام كبير (Kundeti et al. ، 2010). في الآونة الأخيرة ، قمنا بتطوير أداة ضغط تستخدم ذاكرة منخفضة ، ولكن دون تحسن في الوقت (Chikhi et al. ، 2014). تم اقتراح طرق متوازية أخرى للضغط ، كجزء من مجمعات الجينوم. ومع ذلك ، يتم تنفيذ معظمها فقط في سياق مُجمِّع محدد ، ولا يمكن استخدامها كوحدات نمطية لبناء مجمعات أجزاء أخرى أو لتطبيقات أخرى لرسومات de Bruijn الرسومية (مثل metagenomics). في هذا البحث ، نقدم خوارزمية سريعة ومنخفضة الذاكرة لضغط الرسم البياني. تتكون الخوارزمية الخاصة بنا من ثلاث مراحل: التوزيع الدقيق لمدخلات k-mers في الدلاء ، والضغط المتوازي للجرافات ، وخطوة إعادة التوحيد الموازية للصق السلاسل المضغوطة معًا في وحدات. تعتمد الخوارزمية على استخدام المصغرات لتقسيم الرسم البياني (Chikhi et al. ، 2014) ، ومع ذلك ، فإن استراتيجية التقسيم جديدة تمامًا منذ استراتيجية Chikhi et al. (2014) لا يفسح المجال للتوازي. نظرًا لتعقيد الخوارزمية ، فإننا نثبت رسميًا صحتها. ثم نقوم بتقييمه على بيانات تسلسل الجينوم البشري الكامل والصنوبر والتنوب. يتم ضغط الرسم البياني De Bruijn لمجموعة بيانات الجينوم البشري بالكامل في حوالي ساعة و 3 جيجابايت من الذاكرة باستخدام 16 مركزًا. بالنسبة لجينومات الصنوبر والتنوب> 20 جيجابت في البوصة ، يستغرق حساب k-mer وضغط الرسم البياني يومين فقط و 40 جيجابايت من الذاكرة ، مما يؤدي إلى تحسين النتائج المنشورة مسبقًا بترتيب من الحجم على الأقل.

2 الأعمال ذات الصلة تم استكشاف موازاة ضغط الرسم البياني لـ de Bruijn مسبقًا. في (Jackson et al.، 2010 Kundeti et al.، 2010) ، تم تقليل المشكلة إلى مشكلة ترتيب القائمة الكلاسيكية وحلها باستخدام تقنيات متوازية مثل القفز بالمؤشر. نهج آخر قائم على MPI هو تنفيذ جدول التجزئة الموزع ، حيث يتم توزيع k-mers والمعلومات حول أحيائهم بين العمليات. يقوم كل معالج بعد ذلك بتمديد البذور k-mers محليًا قدر الإمكان لبناء وحدات فرعية ثم تمريرها إلى معالجات أخرى لمزيد من التمديد. تم استخدام متغيرات هذا النهج في (Georganas et al.، 2014 Liu et al.، 2011 Simpson et al.، 2009). اقترحت أوراق أخرى استخدام بحث موازٍ للعمق أولاً (Zeng et al. ، 2013) أو نموذج متوازي غير متزامن للعالم الصغير (Meng et al. ، 2014 ، 2012). قبل أن يتم ضغط مخطط de Bruijn ، يجب تكوينه. تمثل المقاربات الموازية حاليًا أحدث ما توصلت إليه التكنولوجيا في هذا المجال. ركزت العديد من الجهود الأصلية على الرسوم البيانية لـ Bruijn ذات الحافة المركزية ، حيث يتم تمثيل الحواف بواسطة ðk þ 1Þ-mers. لقد تطلبوا تحديد كل من k-mers المتميزين و ðk þ 1Þmers (Jackson and Aluru ، 2008 Jackson et al. ، 2010 Kundeti et al. ، 2010 Lu et al. ، 2013 Zeng et al. ، 2013). ركزت الجهود الأحدث على الرسم البياني الذي يركز على العقدة ، والذي لا يتطلب سوى حساب عدد k-mers (Deorowicz et al.، 2014 Li et al.، 2013 Lu et al.، 2013 Marc¸ais and Kingsford، 2011 Melsted and Pritchard ، 2011 Rizk et al.، 2013 Simpson et al.، 2009).

R.Chikhi et al. في تجميع الجينوم ، لا يشكل بناء وضغط رسم دي بروين سوى المراحل الأولية. هناك أيضًا طرق بديلة لا تستخدم الرسم البياني لـ De Bruijn على الإطلاق (مثل الرسم البياني الجشع أو السلسلة). Numerous parallel assemblers are available for use, including ABySS (Simpson et al., 2009), SOAPdenovo (Luo et al., 2012), Ray (Boisvert et al., 2010), PASQUAL (Liu et al., 2013), PASHA (Liu et al., 2011), SAND (Moretti et al., 2012), SWAPAssembler (Meng et al., 2014). Other methods for parallel assembly have been published but without publicly available software (Duan et al., 2014 Garg et al., 2013 Georganas et al., 2015 Jackson et al., 2010). There has also been work done in reducing the overall memory footprint de Bruijn graph assembly. This challenge is most pronounced for k-mer counters. However, when scaling to mammaliansized genomes, memory usage continues to be an issue in downstream steps such as compaction. Chikhi et al. (2014) used minimizers to compact the de Bruijn graph of a human whole-genome dataset in under 50 MB of memory, but the algorithm did not improve the running time. Wu et al. (2012) propose an approach based on dividing the assembly problem into mutually independent instances. Ye et al. (2012) exploit the notion of graph sparseness for reducing memory use. Kleftogiannis et al. (2013) perform a comparative analysis and propose several memory-reducing strategies. Chikhi and Rizk (2012) use Bloom filters to reduce memory usage. Movahedi et al. (2012) propose a divide-and-conquer approach for compacting a de Bruijn graph.

3 Definitions We assume, for the purposes of this paper, that all strings are over the alphabet R ¼ fA C G Tg. A string of length k is called a k-mer. For a string s, we define its k-spectrum, spk ðsÞ, as the multi-set of all k-mer substrings of s. For a set of strings S, we define its multi-set k-spectrum as spk ðSÞ ¼ [s2S spk ðsÞ. For two strings u and v, we write u 2 v to mean that u is a substring of v. We write u½i::j to denote the substring of u from the ith to the jth character, inclusive. We define sufk ðuÞ ¼ u½juj k þ 1 juj and prek ðuÞ ¼ u½1::k . For two strings u and v such that sufk ðuÞ ¼ prek ðuÞ, we define a glue operation as u k v ¼ u v½k þ 1::jvj . The binary relation u ! v between two strings denotes that sufk 1 ðuÞ ¼ prek 1 ðvÞ. For a set of k-mers K, the de Bruijn graph of K is a directed graph such that the nodes are exactly the k-mers in K and the edges are given by the ! relation. Note that our definition of the de Bruijn graph is node-centric, where the edges are implicit given the vertices therefore, we use the terms de Bruijn graph and a set of k-mers interchangeably. Suppose we are given a de Bruijn graph, represented by a set of k-mers K. Consider a path p ¼ ðx1 . . . xm Þ over m 1 vertices. We allow the path to be a cycle, i.e. it is possible that x1 ¼ xm . The endpoints of a path are x1 and xm if it is not a cycle. A single-vertex path has one endpoint. A cycle does not have endpoints. The internal vertices of a path are vertices that are not endpoints. p is said to be a unitig if either jpj ¼ 1 or for all 1 ‘ and a string x with at least k characters, we define lmmðxÞ as the ‘-minimizer of the prefix ðk 1Þ-mer, and rmmðxÞ as the ‘-minimizer of the suffix ðk 1Þ-mer. We refer to these as the left and right minimizers of x, respectively. Two strings (u, v) are m-compactable in S if they are compactable in S and if m ¼ rmmðuÞ ¼ lmmðvÞ. The m-compaction of a set S is obtained from S by applying the compaction operation as much as possible in any order to all pairs of strings that are m-compactable in S.

4 Algorithm overview In this section, we give a high-level description of our BCALM 2 algorithm (Algorithm 1), leaving important optimizations and implementation details to Section 6. Recall that the input is a set of k-mers K and the output are the strings corresponding to all the maximal unitigs of the de Bruijn graph of K. If time and memory are not an issue, then there is a trivial algorithm: repeatedly find compactable strings and compact them until no further compactions are possible. However, such an approach requires loading all the data into memory, which is not feasible for larger genomes. Instead, BCALM 2 proceeds in three stages. In the first stage, the k-mers are distributed into buckets, with some k-mers being thrown into two buckets. In the second stage, each bucket is compacted, separately. In the third stage, the k-mers that were thrown into two buckets are glued back together so that duplicates are removed. Figure 1 shows the execution of BCALM 2 on a small example.

Input: the set of k-mers K. 1: for all parallel x 2 K do 2: Write x to FðlmmðxÞÞ. 3: if lmmðxÞ 6¼ rmmðxÞ then 4: Write x to FðrmmðxÞÞ. 5: for all parallel i 2 f1 . . . 4‘ g do 6: Run CompactBucket(i) 7: ReuniteðÞ

In the second stage of the algorithm, we process each bucket file using the CompactBucket procedure (Algorithm 2). After the k-mer distribution of the first stage, the bucket file F(i) contains all the k-mers whose left or right minimizer is i. We can therefore load F(i) into memory and perform i-compaction on it. Since the size of the bucket is small, this compaction can be performed using a simple inmemory algorithm. The resulting strings are then written to disk, and will be processed during the third stage. At the end of the second stage, when all CompactBucket procedures are finished, we have performed all the necessary compactions on the data. At this stage of the algorithm, notice that the k-mers x 2 K with lmmðxÞ 6¼ rmmðxÞ exist in two copies. We call such k-mers doubled. We will prove in Section 5 that these k-mers are always at the ends (prefix or suffix) of the compacted strings, never internal, and they can be recognized by the fact that the minimizer at that end does not correspond to the bucket where it resides. We record these ends that have doubled k-mers by marking them ‘lonely’ (lines 4 and 5 of Algorithm 2), since they will need to be ‘reunited’ at the third stage of the algorithm. Strings that have no lonely ends are maximal unitigs, therefore they are output (line 8).

Algorithm 3. Reunite() Input: the set of strings R from the Reunite file. 1: UF Union find data structure whose elements are the distinct k-mer extremities in R. 2: for all parallel u 2 R do 3: if both ends of u are lonely then 4: UF:unionðsufk ðuÞ prek ðuÞÞ 5: for all parallel classes C of UF do 6: P all u 2 R that have a lonely extremity in C 7: while 9u 2 P that does not have a lonely prefix do 8: Remove u from P 9: Let s ¼ u 10: while 9 v 2 P such that sufk ðsÞ ¼ prek ðvÞ do 11: s Glueðs vÞ 12: Remove v from P 13: Output s

Algorithm 4. Glue(u, v) In the first stage (lines 1–6 of Algorithm 1), BCALM 2 distributes the k-mers of K to files Fð1Þ . . . Fð4‘ Þ. These are called bucket files. Each k-mer x 2 K goes into file FðlmmðxÞÞ, and if lmmðxÞ 6¼ rmmðxÞ, also in FðrmmðxÞÞ. The parameter ‘ controls the minimizer size (in our implementation, we set ‘ ¼ 8). Algorithm 2. CompactBucket(i) 1: Load F(i) into memory. 2: U i-compaction of F(i). 3: for all strings u 2 U do 4: Mark u’s prefix as “lonely” if i 6¼ lmmðuÞ. 5: Mark u’s suffix as “lonely” if i 6¼ rmmðuÞ. 6: if u’s prefix and suffix are not lonely then 7: Output u. 8: else 9: Place u in the Reunite file

Input: strings u and v, such that sufk ðuÞ ¼ prek ðvÞ. 1: Let w ¼ u k v. 2: Set lonely prefix bit of w to be the lonely prefix bit of u. 3: Set lonely suffix bit of w to be the lonely suffix bit of v. 4: return w

At the third stage of the algorithm, we process the strings output by CompactBucket with the Reunite procedure (Algorithm 3). At a high level, the purpose of Reunite is to process each string u that has a lonely end, and find a corresponding string v that has a matching lonely end with the same k-mer. When one is found, then u and v are glued together (Algorithm 4), thereby ‘reuniting’ the doubled k-mer that was split in the k-mer distribution stage. The new string inherits its end lonely marks from the glued strings, and the process is then repeated for the next string u that has a lonely end. After Reunite() completes, all duplicate k-mers will have been removed, and the strings in the output will correspond to the maximal unitigs.

Fig. 1. Execution of BCALM 2 on a small example, with k ¼ 4 and ‘ ¼ 2. On the top left, we show the input de Bruijn graph. The maximal unitigs correspond to the path from CCCT to TCTA (spelling CCCTCTA), and to the k-mers CCCC, CCCA, CTAC, CTAA. In this example, minimizers are defined using a lexicographic ordering of ‘-mers. In the top right, we show the contents of the bucket files. Only five of the bucket files are non-empty, corresponding to the minimizers CC, CT, AA, AC and CA. The doubled k-mers are italicized. Below that, we show the set of strings that each i-compaction generates. For example in the bucket CC, the k-mers CCCT and CCTC are compacted into CCCTC, however CCCC and CCCT are not compactable because CCCA is another out-neighbor of CCCC. The lonely ends are denoted by •. In the bottom half we show the execution steps of the Reunite algorithm. Nodes in bold are output

To perform these operations efficiently in time and memory, Reunite first partitions the strings of R so that any two strings that need to be reunited are guaranteed to be in the partition. Then, each partition can be processed independently. To achieve the partition, we use a union-find (UF) data structure of all k-mers extremities. Recall that a UF data structure is created by first assigning a set to each distinct element (here, an element is the k-mer extremity of a string). Then, the union operation replaces the sets of two elements by a single set corresponding to their union. Here, union is applied to both k-mer extremities of a string. After the UF is constructed, the set of strings to be reunited is partitioned such that k-mer extremities of sequences in a partition all belong to the same UF set.

besides at t½p k þ 1 p . Since there are no duplicate k-mers in T, this is a contradiction. Now, we show that S T. Let s 2 S and let t 2 T such that s 2 t. By applying an argument symmetrical to the one above, there exists a s0 2 S such that t 2 s0 . This means that s 2 s0 , and, in particular, s½1::k 2 s0 . Since k-mers can only appear once in S, we must have that s ¼ s0 and hence s ¼ t 2 T. h Next, we characterize the k and k þ 1 spectrums of U. Given a multi-set M, we denote by Set(M) as the set version of M, with all multiplicity information implicitly removed. When referring to a set, such as K, as a multi-set, we will mean that all the elements have multiplicity one. LEMMA 2. spk ðUÞ ¼ K

5 Proof of correctness Recall that K is the input to the algorithm and let U be the strings corresponding to the set of all maximal unitigs of K. We will assume for our proof that U does not contain any circular unitigs. We note that since BCALM 2 outputs strings, it cannot represent circular unitigs in its output. Circular unitigs present a corner case for both the analysis and the algorithm itself, and, for the sake of presentation brevity, we do not consider them here. We prove the correctness of BCALM 2 by showing that it outputs U. We first give a Lemma that will allow us to show that the output is U by arguing about its k and k þ 1 spectrums. LEMMA 1. Let S and T be two sets of strings of length at least k such that spkþ1 ðSÞ ¼ spkþ1 ðTÞ and spk ðSÞ ¼ spk ðTÞ and all these spectrums are without duplicates. Then, S ¼ T. PROOF. We will prove that S T. The same argument will be symmetrically applicable to prove T S, which will imply S ¼ T. First, we show that for all s 2 S, there exists a t 2 T such that s 2 t. Let s 2 S and let p ¼ maxfi : 9t 2 T s½1::i 2 tg, and let t be a string achieving the max. Note that p k þ 1 since every ðk þ 1Þmer of S is also in T. Suppose for the sake of contradiction that p 362KB Sizes 0 Downloads 5 Views


مقدمة

The de Bruijn graph is a data structure first brought to bioinformatics as a method to assemble genomes from the experimental data generated by sequencing by hybridization [1]. It later became the key algorithmic technique in genome assembly [2, 3] that resulted in dozens of software tools [4–12]. In addition, the de Bruijn graphs have been used for repeat classification [13], de novo protein sequencing [14], synteny block construction [15, 16], multiple sequence alignment [17], and other applications in genomics and proteomics.

The breakpoint graph is a data structure introduced to study the reversal distance [18], which has formed the basis for much algorithmic research on rearrangements over the last two decades [19].

Since the connections between the breakpoint graphs and the de Bruijn graphs was never explicitly described, researchers studying genome rearrangements often do not realize that breakpoint graphs are merely de Bruijn graphs in disguise. As a result, they often do not know how to move from the traditional breakpoint graphs on synteny blocks to the breakpoint graphs on genomes (with "single nucleotide" resolution), particularly in the case of double-stranded genomes with inverted repeats. Likewise, researchers working in genome assembly are often unaware about the connections between the de Bruijn graphs and the breakpoint graphs. As a result, the exchange of ideas between these two communities has been limited. For example, Iqbal et al. [20] recently introduced the notion of the colored de Bruijn graphs that resulted in a popular Cortex assembler. While the notion of the colored de Bruijn graphs is essentially identical to the notion of the breakpoint graph, authors of [20] are probably unaware about this connection since they provided no references to previous genome rearrangement studies. This is unfortunate since various results about the breakpoint graphs (e.g., the connection between rearrangements and alternating cycles) remained beyond the scope of this very useful study.

Recently, genome rearrangement studies moved from the level of synteny blocks to the level of single nucleotides [21]. Likewise, genome assembly experts recently moved towards the analysis of structural variations and comparative assembly of related species based on the analysis of the de Bruijn graphs [20]. We thus argue that the time has come to explain that the breakpoint graphs and the de Bruijn graphs are two identical data structures (if one ignores a cosmetic difference between them) as they both represent specific instances of a general notion of the A-Bruijn graph introduced in [13]. The A-Bruijn graphs are based on representing genomes as sets of labeled paths and further gluing identically labeled edges (breakpoint graphs) or vertices (de Bruijn graphs) in the resulting paths.

We argue that a unified framework covering both breakpoint and de Bruijn graphs is important to bridge the divide between researchers working with breakpoint graphs (that usually focus in rearrangements and ignore repeats) and researchers working with de Bruijn graphs (that usually focus on repeats and ignore rearrangements). In reality, there exists a complex interplay between rearrangements and repeats, e.g., LINE repeats and segmental duplications often trigger rearrangements [22–24]. However, this interplay is not explicitly revealed by the breakpoint graphs since they do not even encode repeats (repeats are intentionally masked at the synteny block construction step). For example, the interplay between LINEs and rearrangements cannot be derived from the breakpoint graph alone forcing Zhao and Bourque [23] to perform additional analysis. Our goal is to introduce the graphs that encode both rearrangements and repeats and immediately reveal this interplay. For example, encoding repeats present in the breakpoint regions (that may potentially trigger rearrangements) leads to gluing alternating cycles in the breakpoint graphs and requires development of new algorithms that integrate rearrangements and repeats. In such graphs, the classical non-self-intersecting alternating cycles formed by edges alternating between two colors (the workhorse of genome rearrangement studies) may turn into self-intersecting cycles formed by edges alternating between 3 colors, where the third color corresponds to repeated elements (see Figure 1). Nurk and Pevzner [25] recently used this framework to develop a new comparative genome analysis tool SPArcle and applied it to analyzing multiple bacterial strains resulting from the "controlled evolution" experiments [26]. SPArcle is based on SPAdes assembler and, in difference from Cortex, it uses ideas from the previous genome rearrangement studies (e.g., alternating cycles) to analyze the resulting A-Bruijn graphs.

Genomes جي أ= س 1, س 2, س 3 و جي ب= س 1, − س 2, س 3 (represented as bicolored paths) differ from each other by a single reversal of segment س 2. The breakpoint graph BP(جي أ, G ب) and the alternating cycle constructed from genomes جي أ و جي ب (left: no repeats at the breakpoint regions right, a pair of repeats colored in green at the breakpoint regions).

Genome rearrangement studies usually start from constructing a set of synteny blocks shared by two genomes (see Figure 2). Each genome is defined as a sequence of synteny blocks separated by breakpoint regions and is represented as a path formed by alternating colored and black edges, where synteny blocks correspond to directed and labeled black edges and breakpoint regions correspond to undirected colored edges. Figure 3(a) presents paths corresponding to 11 synteny blocks shared by Human and Mouse × chromosomes. Each synteny block س أنا is represented as an directed black edge ( S i t , S i h ) , where S i t and S i h refer to the endpoints of the synteny blocks representing its tail and head, respectively. Two consecutive synteny blocks are separated by a breakpoint region in the Human (Mouse) × chromosome that is modeled by a red (blue) edge connecting the corresponding endpoints of these synteny blocks. The (traditional) breakpoint graph of Human and Mouse × chromosomes is obtained by "gluing" identically labeled black edges in these two paths as shown in Figure 3.

The 11 synteny blocks shared by Human and Mouse × chromosomes (adapted from Pevzner and Tesler [33]).


Publisher’s note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary Figure 1 A comparison of the Flye and HINGE assembly graphs on bacterial genomes from the BACTERIA dataset.

(Left) The Flye and Hinge assembly graphs of the KP9657 dataset. There is a single unique edge entering into (and exiting) the unresolved “yellow” repeat and connecting it to the rest of the graph. Thus, this repeat can be resolved if one excludes the possibility that it is shared between a chromosome and a plasmid. In contrast to HINGE, Flye does not rule out this possibility and classifies the yellow repeat as unresolved. (Right) The Flye and Hinge assembly graphs of the EC10864 dataset show a mosaic repeat of multiplicity four formed by yellow, blue, red and green edges (the two copies of each edge represent complementary strands). HINGE reports a complete assembly into a single chromosome.

Supplementary Figure 2 The assembly graph of the YEAST-ONT dataset.

Edges that were classified as repetitive by Flye are shown in color, while unique edges are black. Flye assembled the YEAST-ONT dataset into a graph with 21 unique and 34 repeat edges and generated 21 contigs as unambiguous paths in the assembly graph. A path v1, …vأنا, vi+1vن in the graph is called unambiguous if there exists a single incoming edge into each vertex of this path before vi+1 and a single outgoing edge from each vertex after vأنا. Each unique contig is formed by a single unique edge and possibly multiple repeat edges, while repetitive contigs consist of the repetitive edges which were not covered by the unique contigs. The visualization was generated using the graphviz tool (http://graphviz.org).

Supplementary Figure 3 The assembly graph of the WORM dataset.

Edges that were classified as repetitive by Flye are shown in color, while unique edges are black. Flye assembled the WORM dataset into a graph with 127 unique and 61 repeat edges and generated 127 contigs as unambiguous paths in the assembly graph. The visualization was generated using the graphviz tool (http://graphviz.org).

Supplementary Figure 4 Dot plots showing the alignment of reads against the Flye assembly, the Miniasm assembly and the reference C. elegans الجينوم.

(أ) The reference genome contains a tandem repeat of length 1.9 kb (10 copies) on chromosome X with the repeated unit having length ≈190 nucleotides. In contrast, the Flye and Miniasm assemblies of this region suggest a tandem repeat of length 5.5 kb (27 copies) and 2.8 kb (13 copies), respectively. 15 reads that span over the tandem repeat support the Flye assembly (the mean length between the flanking unique sequence matches the repeat length reconstructed by Flye) and suggests that the Flye length estimate is more accurate. (b) The reference genome contains a tandem repeat of length 2 kb on chromosome 1. In contrast, the Flye and Miniasm assemblies of this region suggest a tandem repeat of length 10 kb and 5.6 kb, respectively. A single read that spans over the tandem repeat supports the Flye assembly. Since the mean read length in the WORM dataset is 11 kb, it is expected to have a single read spanning a given 10.0 kb region but many more reads spanning any 5.6 kb region (as implied by the Miniasm assembly) or 2.0 kb region (as implied by the reference genome). Six out of 23 reads cross the “left” border (two out of 18 reads cross the “right” border) of this tandem repeat by more than 5.6 kb, thus contradicting the length estimate given by Miniasm and suggesting that the Flye length estimate is more accurate. (ج) The reference genome contains a tandem repeat of length 3 kb on chromosome X. In contrast, the Flye and Miniasm assemblies of this region suggest a tandem repeat of lengths 13.6 kb and 8 kb, respectively. A single read that spans over the tandem repeat reveals the repeat cluster to be of length 12.2k, which suggests that the Flye length estimate is more accurate. (د) The reference genome contains a tandem repeat of length 1.5 kb on chromosome 1. In contrast, the Flye and Miniasm assemblies of this region suggest tandem repeats of length 17 kb and 4.3 kb, respectively. One read that spans over the tandem repeat reveals the repeat cluster to be of length 18.0 kb, which suggests that the Flye length estimate is more accurate.


شاهد الفيديو: 4 علاقات لازم تهربي منها. هي وبس الحلقة الكاملة (أغسطس 2022).