فیلتر بلوم در بیوانفورماتیک: تفاوت میان نسخه‌ها

محتوای حذف‌شده محتوای افزوده‌شده
Rezabot (بحث | مشارکت‌ها)
جز ربات:مرتب‌سازی عنوان‌ها+املا+تمیز+
جز ویرایش با ابزار زدودن تبلیغ
خط ۲۱:
مشکلی که این راه‌حل دارد، این است که ممکن است فیلتر بلوم به مثبت کاذب بخورد و خروجی اشتباه به ما بدهد. برای رهایی از این تله، باید راهکارهای تکمیلی را به‌کار گیریم. به عنوان مثال، می‌توانیم چندین فیلتر بلوم را به صورت متوالی قرار دهیم، به این صورت که در فیلتر بلوم هر لایه، مثبت‌های کاذب لایهٔ قبلی را نگه داریم؛ در زمان پرس‌وجو، کافی است اولین لایه‌ای (مانند <math>i</math>) را پیدا کنیم که عضو مربوطه در لایه <math>i</math> یافت می‌شود اما در لایهٔ <math>i+1</math> یافت نمی‌شود. در صورتی که <math>i</math> فرد باشد، می‌توان گفت پاسخ اصلی مثبت است، و در صورتی که <math>i</math> فرد باشد، می‌توان گفت که پاسخ منفی است. با این راهکار می‌توان به سادگی، پاسخ‌های مثبت کاذب را حذف کرد.
 
حال اگر برای نگه‌داری هر کاراکتر در رئوس این گراف، به ۲ بیت نیاز داشته باشیم، به‌ازای یک رشته ۱۶-تایی از ژنوم‌ها، به ۶۴ بیت حافظه نیاز داریم. اما با استفاده از یک بلوم فیلتر (به عنوان مثال در [[الگوریتم]] Minia<ref>{{Cite journal|last=Chikhi|first=Rayan|last2=Rizk|first2=Guillaume|date=2013-09-16|title=Space-efficient and exact de Bruijn graph representation based on a Bloom filter|journal=Algorithms for Molecular Biology|volume=8|issue=1|pages=22|doi=10.1186/1748-7188-8-22|issn=1748-7188|pmc=3848682|pmid=24040893}}</ref>)، می‌توان این حافظه را تا ۱۲ بیت، و با استفاده از ۴ بلوم فیلتر به صورت متوالی، تا ۸ بیت کاهش داد.<ref>{{یادکرد وب |نام خانوادگی۱=شریفی زارچی |نام۱=علی |عنوان=بلوم فیلتر در الگوریتم‌های بیوانفورماتیک |نشانی=https://maktabkhooneh.org/course/الگوریتم-بیوانفورماتیک-mk633/فصل-اول-الگوریتم-بیوانفورماتیک-ch1754/ویدیو-Bloom-Filter/ |وبگاه=مکتب‌خونه}}</ref>
 
=== مطالعه خصوصیت‌های توالی‌ها ===