الرئيسيةعريقبحث

مرشحات بلوم في المعلوماتية الحيوية

☰ جدول المحتويات


تمثل الصورة الاستعلام عن مرشح بلوم(Bloom)، وهوk-mers من تسلسل DNA. الخطوة الاولى هي تخزين k-mers من تسلسل في مرشح بلوم(Bloom). يتم الاستعلام بطريقة مماثلة حيث يتم تقسيم تسلسل الاستعلام الى k-mers المطابقة له ،ويتم استخدام k-mers للإستعلام عن مرشح بلوم(Bloom).

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

تستخدم مرشحات بلوم في المقام الأول في المعلوماتية الحيوية لاختبار وجود k-mer في تسلسل أو مجموعة من التسلسلات. يتم فهرسة k-mers للتسلسل في مرشح (Bloom) ، ويمكن الاستعلام عن أي k-mer من نفس الحجم مقابل مرشح Bloom. هذا هو البديل المفضل لتجزئة k-mers في تسلسل مع جدول تجزئة ، خاصة عندما يكون التسلسل طويلًا جدًا، حيث يتطلب تخزين أعداد كبيرة من k-mers في الذاكرة.

مقارنة بين جدول التجزئة و مرشح بلوم(Bloom) لتخزين الرسم البياني de bruijn في الذاكرة . لاحظ انه بينما يمكن الاحتفاظ بمعلومات الحافة في جدول التجزئة ، الا انه لا يتم تخزينها في مرشح بلوم(Bloom)، الأمر الذي يعقد اجتياز الرسم البياني . سوف يبقى مرشح بلوم(Bloom) بنفس حجم جدول التجزئة و يستخدم مساحة أقل بسبب عدم تخزين قيم k-mres نفسها

تطبيقات

تمييز أو وصف التسلسل

خطوة المعالجة في العديد من تطبيقات المعلوماتية الحيوية تتضمن تصنيف التسلسل، والتصنيف الأولي للقراءات من تجربة تسلسل الحمض النووي DNA. على سبيل المثال، في دراسات علم الجينوم البيئي (الميتاجينوميات) من المهم أن تكون قادراً على معرفة إذا كانت قراءة التسلسل تنتمي إلى نوع جديد.[1] وفي مشاريع التسلسل السريري، من الضروري ترشيح أو تصفية القراءات من مجموعة العوامل الوراثية(جينومات)للكائنات الحية الملوثة. هنالك العديد من أدوات المعلوماتية الحيوية التي تستخدم مرشحات بلوم (Bloom) لتصنيف القراءات بواسطة الاستفسار أو الاستعلام من k-mers لقراءة مجموعة من مرشحات بلوم (Bloom) المولدة من مجموعة العوامل الوراثية (جينومات) مرجعية معروفة. بعض الأدوات التي تستخدم هذه الطريقة هيFACS[1] و أدوات BIOBLOOM.[2] في حين هذه الطرق يمكن أن لا تتفوق على أدوات تصنيف المعلوماتية الحيوية الأخرى،[3] مثل Kraken،فإنها تقدم بديلاً أو خياراً مقتصداً للذاكرة .

مجال حديث للبحث مع مرشحات بلوم (Bloom) في تمييز التسلسل، ويكون بتطوير طرق للإستعلام عن القراءات

الأولية من تجارب التسلسل.على سبيل المثال، كيف يمكن للشخص أن يحدد أي قراءات تحتوي على 30-mer معينة في

أرشيف قراءة تسلسل NCBI بأكمله؟ هذه المهمة تتطلب إعادة قراءات محددة تحتوي على K-mer BLAST، و أدوات مماثلة لا يمكنها التعامل مع هذه المشكلة بكفاءة، لذلك تم تنفيذ هياكل البيانات القائمة على مرشح

بلوم (Bloom) لتحقيق هذا الغرض أو هذه الغاية. أشجار الازدهار الثنائية،[4] هي أشجار ثنائية لمرشحات بلوم التي تسهل الإستعلام عن النسخ في تجارب RNA-seq الكبيرة.

تركيب مجموعة المادة الوراثية (الجينوم) في الإنسان

لقد تم استخدام كفاءة الذاكرة لمرشح بلوم (Bloom) في تجميع مجموعة المادة الوراثية (الجينوم) كوسيلة لتقليل مساحة بصمة القدم للk-mers من البيانات المتسلسلة . مساهمة أساليب التجميع المرتكزة على مرشح بلوم (Bloom) تكون من خلال الدمج بين مرشحات بلوم (Bloom) والرسوم البيانية de bruijn في نموذج يسمى الرسم البياني الاحتمالي de bruijn،[5] الذي يعمل على تحسين استخدام الذاكرة على حساب المعدل الإيجابي الخاطئ الملازم لمرشحات بلوم(Bloom)، وبدلاً من تخزين الرسم البياني de bruijn في جدول تجزئة يتم تخزينه في عند استخدام مرشح بلوم (Bloom) لتخزين الرسم البياني de bruijn يؤدي ذلك إلى تعقيد مرحلة اجتياز الرسم البياني لبناء التجميع وتأخير هذه الخطوة، ولأن معلومات الحواف ليس مشفرة في مرشح بلوم (Bloom)، لذلك يتم إنجاز تمرير واجتياز الرسم البياني عن طريق الاستعلام عن مرشح بلوم (Bloom) لأي خيار من الأربعة خيارات الممكنة التالية لنقطة k-mers الحالية. على سبيل المثال :إذا كانت النقطة أو العقدة الحالية هي ACT يجب أن تكون العقدة التالية لها هي CTA أوCTG أو CTC أو CTT.

إذا كان الاستعلام عن k-mers موجود وفعال في مرشح بلوم (Bloom) فسيتم إضافة k-mers إلى المسار، لذلك هناك مصدران لنتيجة ايجابية خاطئة للاستعلام عن مرشح بلوم (Bloom)، وذلك عندما يتم اجتياز الرسم البياني ل de bruijn، لذلك هناك احتمال لوجود عنصر أو أكثر من ثلاثة عناصر خاطئة في مكان آخر من مجموعة التسلسل لإعادة نتيجة ايجابية خاطئة واحدة فقط. هناك نسبة للنتائج الايجابية الخاطئة ملازم لها ومذكو سابقاً لمرشح بلوم (Bloom) نفسه، لذلك فإن أدوات التجميع التي تستخدم مرشح بلوم (Bloom) يجب أن تعمل على حساب مصادر النتائج الايجابية الخاطئة في اساليبها وطرقها، ومن الأمثلة على المجموعات التي تستخدم هذا الأسلوب والنهج لتجميع de novo هي ([6]ABySS2) و(Minia).[7]

تصحيح خطأ التسلسل

إن طرق تسلسل وترتيب الجيل (NGS) سمحت واتاحت لنا فرص لتوليد تسلسلات مجموعة المادة الوراثية(الجينوم) جديدة بشكل أسرع وأقل تكلفة بكثير من الطرق القديمة، وبالرغم من ذلك فإن هذه الطرق لديها نسبة خطأ أكثر،[8][9] الأمر الذي يعقد التحليل النهائي للتسلسل، ومن الممكن أيضاً أن يؤدي إلى استنتاجات خاطئة . وقد تم تطوير الكثير من الطرق لتصحيح الأخطاء في قراءة (NGS)، ولكنها تستخدم مساحات كبيرة من الذاكرة مما يجعلها وسيلة غير عملية وغير مجدية بالنسبة لمجموعة المادة الوراثية (الجينوم)الكبيرة، مثل مجموعة المادة الوراثية في الإنسان . لذلك تم تطوير أدوات تستخدم مرشحات بلوم (Bloom) لمعالجة هذه المشاكل مع ضرورة الأستفادة من الاستخدام الصحيح الفعال للذاكرة، ومن الأمثلة على هذه الأدوات ([10]BLESS) و (Musket).[11]

وهاتان الطريقتان تستخدمان اسلوب الطيف في k-mer لتصحيح الخطأ. الخطوة الاولى في هذا الاسلوب هي حساب تضاعف k-mers، اما طريقة (BLESS) تستخدم فقط مرشحات بلوم (Bloom) لتخزين العدد الإجمالي، اما طريقة (Musket) فهي تعتمد على استخدام مرشحات بلوم (Bloom) فقط لحساب k-mers الوحيدة غير المشابهة

لغيرها، اما باقي k-mers المتشابهة فيتم تخزينها في جدول التجزئة.[12]

تسلسل وترتيب RNA

ومن اسخدمات مرشحات بلوم(Bloom) الاستفادة منها في خطوط وتوصيلات متسلسلة RNA، وفي مجموعات متسلسلة RNA،[13] وأيضاً تستخدم مرشحات بلوم (Bloom) لإيجاد sig-mers: k-mers التي توجد فقط في إحدى الكتل والعقد. وبعد ذلك، يتم استخدام هذه النتائج لتخمين وتقدير مستويات التطابق، لذلك فإنه لا يعمل على تحليل كل k-mers المحتملة، مما يؤدي إلى تحسينات في الأداء، وفي استخدام الذاكرة، وقد ظهر بالبحث انه يعمل مثل الطرق السابقة .

المراجع

  1. Stranneheim, Henrik; Käller, Max; Allander, Tobias; Andersson, Björn; Arvestad, Lars; Lundeberg, Joakim (2010-07-01). "Classification of DNA sequences using Bloom filters". Bioinformatics. 26 (13): 1595–1600. doi:10.1093/bioinformatics/btq230. ISSN 1367-4803. PMID 20472541. مؤرشف من الأصل في 19 مايو 2020.
  2. Chu, Justin; Sadeghi, Sara; Raymond, Anthony; Jackman, Shaun D.; Nip, Ka Ming; Mar, Richard; Mohamadi, Hamid; Butterfield, Yaron S.; Robertson, A. Gordon (2014-12-01). "BioBloom tools: fast, accurate and memory-efficient host species sequence screening using bloom filters". Bioinformatics. 30 (23): 3402–3404. doi:10.1093/bioinformatics/btu558. ISSN 1367-4803. PMID 25143290. مؤرشف من الأصل في 15 أبريل 2017.
  3. Wood, Derrick E; Salzberg, Steven L (2014). "Kraken: ultrafast metagenomic sequence classification using exact alignments". Genome Biology. 15 (3): R46. doi:10.1186/gb-2014-15-3-r46. ISSN 1465-6906. PMID 24580807. مؤرشف من الأصل في 17 فبراير 2020.
  4. Solomon, Brad; Kingsford, Carl (2016-3). "Fast Search of Thousands of Short-Read Sequencing Experiments". Nature biotechnology. 34 (3): 300–302. doi:10.1038/nbt.3442. ISSN 1087-0156. PMID 26854477. مؤرشف من الأصل في 19 مايو 2020.
  5. Pell, Jason; Hintze, Arend; Canino-Koning, Rosangela; Howe, Adina; Tiedje, James M.; Brown, C. Titus (2012-08-14). "Scaling metagenome sequence assembly with probabilistic de Bruijn graphs". Proceedings of the National Academy of Sciences of the United States of America. 109 (33): 13272–13277. doi:10.1073/pnas.1121464109. ISSN 0027-8424. PMID 22847406. مؤرشف من الأصل في 19 مايو 2020.
  6. Jackman, Shaun D.; Vandervalk, Benjamin P.; Mohamadi, Hamid; Chu, Justin; Yeo, Sarah; Hammond, S. Austin; Jahesh, Golnaz; Khan, Hamza; Coombe, Lauren (2017-5). "ABySS 2.0: resource-efficient assembly of large genomes using a Bloom filter". Genome Research. 27 (5): 768–777. doi:10.1101/gr.214346.116. ISSN 1088-9051. PMID 28232478. مؤرشف من الأصل في 19 مايو 2020.
  7. Chikhi, Rayan; Rizk, Guillaume (2013-09-16). "Space-efficient and exact de Bruijn graph representation based on a Bloom filter". Algorithms for Molecular Biology : AMB. 8: 22. doi:10.1186/1748-7188-8-22. ISSN 1748-7188. PMID 24040893. مؤرشف من الأصل في 19 مايو 2020.
  8. Victoria, Xin; Blades, Natalie; Ding, Jie; Sultana, Razvan; Parmigiani, Giovanni (2012-07-30). "Estimation of sequencing error rates in short reads". BMC Bioinformatics. 13: 185. doi:10.1186/1471-2105-13-185. ISSN 1471-2105. PMID 22846331. مؤرشف من الأصل في 19 مايو 2020.
  9. Loman, Nicholas J.; Misra, Raju V.; Dallman, Timothy J.; Constantinidou, Chrystala; Gharbia, Saheer E.; Wain, John; Pallen, Mark J. (2012-05). "Performance comparison of benchtop high-throughput sequencing platforms". Nature Biotechnology (باللغة الإنجليزية). 30 (5): 434–439. doi:10.1038/nbt.2198. ISSN 1546-1696. مؤرشف من الأصل في 19 مايو 2020.
  10. Heo, Yun; Wu, Xiao-Long; Chen, Deming; Ma, Jian; Hwu, Wen-Mei (2014-05-15). "BLESS: Bloom filter-based error correction solution for high-throughput sequencing reads". Bioinformatics. 30 (10): 1354–1362. doi:10.1093/bioinformatics/btu030. ISSN 1367-4803. PMID 24451628. مؤرشف من الأصل في 19 مايو 2020.
  11. Liu, Yongchao; Schröder, Jan; Schmidt, Bertil (2013-02-01). "Musket: a multistage k-mer spectrum-based error corrector for Illumina sequence data". Bioinformatics (باللغة الإنجليزية). 29 (3): 308–315. doi:10.1093/bioinformatics/bts690. ISSN 1367-4803. مؤرشف من الأصل في 30 أبريل 2020.
  12. Pellow, David; Filippova, Darya; Kingsford, Carl (2017-06-01). "Improving Bloom Filter Performance on Sequence Data Using k-mer Bloom Filters". Journal of Computational Biology. 24 (6): 547–557. doi:10.1089/cmb.2016.0155. ISSN 1066-5277. PMID 27828710. مؤرشف من الأصل في 19 مايو 2020.
  13. Zhang, Zhaojun; Wang, Wei (2014-06-15). "RNA-Skim: a rapid method for RNA-Seq quantification at transcript level". Bioinformatics. 30 (12): i283–i292. doi:10.1093/bioinformatics/btu288. ISSN 1367-4803. PMID 24931995. مؤرشف من الأصل في 19 مايو 2020.

موسوعات ذات صلة :