ويكيبيديا

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


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

تمثل الصورة الاستعلام عن مرشح بلوم(Bloom)، وهوk-mers من تسلسل DNA. الخطوة الاولى هي تخزين k-mers من تسلسل في مرشح بلوم(Bloom). يتم الاستعلام بطريقة مماثلة حيث يتم تقسيم تسلسل الاستعلام إلى k-mers المطابقة له ،ويتم استخدام k-mers للإستعلام عن مرشح بلوم(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 (1 يوليو 2010). "Classification of DNA sequences using Bloom filters". Bioinformatics. ج. 26 ع. 13: 1595–1600. DOI:10.1093/bioinformatics/btq230. ISSN:1367-4803. PMC:2887045. PMID:20472541. مؤرشف من الأصل في 2020-05-19.
  2. ^ Chu، Justin؛ Sadeghi، Sara؛ Raymond، Anthony؛ Jackman، Shaun D.؛ Nip، Ka Ming؛ Mar، Richard؛ Mohamadi، Hamid؛ Butterfield، Yaron S.؛ Robertson، A. Gordon (1 ديسمبر 2014). "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. PMC:4816029. PMID:25143290. مؤرشف من الأصل في 2017-04-15.
  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. PMC:4053813. PMID:24580807. مؤرشف من الأصل في 2020-02-17.{{استشهاد بدورية محكمة}}: صيانة الاستشهاد: دوي مجاني غير معلم (link)
  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. PMC:4804353. PMID:26854477. مؤرشف من الأصل في 19 مايو 2020. {{استشهاد بدورية محكمة}}: تحقق من التاريخ في: |تاريخ= (مساعدة)
  5. ^ Pell، Jason؛ Hintze، Arend؛ Canino-Koning، Rosangela؛ Howe، Adina؛ Tiedje، James M.؛ Brown، C. Titus (14 أغسطس 2012). "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. PMC:3421212. PMID:22847406. مؤرشف من الأصل في 2020-05-19.
  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. PMC:5411771. PMID:28232478. مؤرشف من الأصل في 19 مايو 2020. {{استشهاد بدورية محكمة}}: تحقق من التاريخ في: |تاريخ= (مساعدة)
  7. ^ Chikhi، Rayan؛ Rizk، Guillaume (16 سبتمبر 2013). "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. PMC:3848682. PMID:24040893. مؤرشف من الأصل في 2020-05-19.{{استشهاد بدورية محكمة}}: صيانة الاستشهاد: دوي مجاني غير معلم (link)
  8. ^ Victoria، Xin؛ Blades، Natalie؛ Ding، Jie؛ Sultana، Razvan؛ Parmigiani، Giovanni (30 يوليو 2012). "Estimation of sequencing error rates in short reads". BMC Bioinformatics. ج. 13: 185. DOI:10.1186/1471-2105-13-185. ISSN:1471-2105. PMC:3495688. PMID:22846331. مؤرشف من الأصل في 2020-05-19.{{استشهاد بدورية محكمة}}: صيانة الاستشهاد: دوي مجاني غير معلم (link)
  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. Archived from the original on 19 مايو 2020. {{استشهاد بدورية محكمة}}: تحقق من التاريخ في: |تاريخ= (help)
  10. ^ Heo، Yun؛ Wu، Xiao-Long؛ Chen، Deming؛ Ma، Jian؛ Hwu، Wen-Mei (15 مايو 2014). "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. PMC:6365934. PMID:24451628. مؤرشف من الأصل في 2020-05-19.
  11. ^ Liu, Yongchao; Schröder, Jan; Schmidt, Bertil (1 Feb 2013). "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. Archived from the original on 2020-04-30.
  12. ^ Pellow، David؛ Filippova، Darya؛ Kingsford، Carl (1 يونيو 2017). "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. PMC:5467106. PMID:27828710. مؤرشف من الأصل في 2020-05-19.
  13. ^ Zhang، Zhaojun؛ Wang، Wei (15 يونيو 2014). "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. PMC:4058932. PMID:24931995. مؤرشف من الأصل في 2020-05-19.
مجلوبة من «https://ar.wikipedia.org/w/index.php?title=مرشحات_بلوم_في_المعلوماتية_الحيوية&oldid=65634784»