موضوع مقاله: فیلتر بلوم در بیوانفورماتیک | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # فیلتر بلوم در بیوانفورماتیک | مقدمه: فیلترهای بلوم در بیوانفورماتیک نوعی داده‌ساختار احتمالاتی هستند که برای ذخیره‌سازی اعضای یک مجموعه، و جستجو کردن اعضا درون آن مجموعه هستند. | ## بخش 1: فیلتر بلوم در بیوانفورماتیک | هدف استفاده از این طراحی این است که بتوانیم تعدادی از پرس‌وجوها را با سرعت و به صورت قطعی پاسخ دهیم، و در مواقعی حافظهٔ مورد نیاز را نیز کاهش دهیم. به عنوان مثال طراحی فیلتر بلوم به این شکل است که اگر پاسخ پرس‌وجو از فیلتر بلوم منفی باشد، قطعاً عضو مورد نظر در مجموعهٔ متناظر وجود ندارد (و این را صراحتاً می‌توانیم اعلام کنیم). اما اگر پاسخ پرس‌وجو مثبت باشد، نمی‌توان به‌طور قطع گفت که این عضو در مجموعهٔ مورد نظر وجود دارد یا خیر، و باید عملیات محاسباتی دیگری را برای تأیید یا رد حرف خود به کار بگیریم. از این داده‌ساختار، برای بهبود حافظه و سرعت برخی از برنامه‌های کاربردی در زمینه بیوانفورماتیک به وفور استفاده می‌شود. در این مقاله، برخی از کاربردهای فیلتر بلوم در حل مسائل بیوانفورماتیک را بررسی می‌کنیم. در این شکل، داده‌های ، و در داده‌ساختار اضافه شده‌اند، و عبارت مورد پرسمان قرار گرفته‌است. از آن‌جایی که AND بیتی خانه‌های متناظر با یک نیست، می‌توان قطعاً گفت که در داده‌ساختار موجود نیست. فیلتر بلوم، از تعدادی تابع درهم‌ساز استفاده می‌کند و هر تابع، اعضای مجموعه را به یک اندیس از یک آرایه بیتی متناظر می‌کند. | ## بخش 2: فیلتر بلوم در بیوانفورماتیک | برای اضافه کردن یک عضو به فیلتر بلوم، به ازای هر تابع درهم‌ساز، آن عضو را Hash می‌کنیم و اندیس خروجی تابع را در آرایه بیتی، ۱ می‌کنیم. برای پرس‌وجو از این فیلتر نیز ورودی را به ازای تمام توابع درهم‌ساز، Hash کرده و اندیس‌های متناظر خروجی را با هم AND می‌کنیم. مشخص است که اگر عضوی در داده‌ساختار اضافه شده باشد، تمام بیت‌های متناظر با اندیس‌های خروجی توابع، ۱ هستند و در نتیجه خروجی پرسمان نیز مثبت است (و بالطبع اگر حاصل پرسمان منفی باشد، قطعاً عضو مورد نظر در داده‌ساختار وجود ندارد)؛ اما اگر عضوی در داده‌ساختار اضافه نشده باشد نیز ممکن است پرسمان خروجی مثبت بدهد (مثبت کاذب). کاربردها بازسازی توالی ژنوم در تحقیقات بیوانفورماتیک روی ژنوم‌ها و کارکرد هر قسمت از آن‌ها، نمی‌توان یک ژنوم را به‌طور کامل و یک‌تکه مورد بررسی قرار داد. به این منظور، ژنوم را به چندین قسمت کوچک‌تر تقسیم می‌کنند، و سپس برای یک‌پارچه‌سازی، آن‌ها را کنار هم قرار می‌دهند. در این گراف، به ازای هر تایی (k-mer) از رشته‌های ژنوم، یک رأس در نظر گرفته می‌شود، و بین دو رأس و در صورتی که یک کاراکتر آخر با کاراکتر ابتدای برابر باشد، یال جهت‌دار گذاشته می‌شود. برای کاهش حافظهٔ مصرفی، فیلتر بلوم را به‌کار می‌گیریم، و رئوس گراف را در یک فیلتر بلوم نگه می‌داریم. برای پیمایش گراف نیز از یک رأس، تمام ۴ حالتی که برای کاراکتر آخر رأس بعدی وجود دارد را در فیلتر بلوم پرسمان می‌کنیم. | ## بخش 3: فیلتر بلوم در بیوانفورماتیک | مشکلی که این راه‌حل دارد، این است که ممکن است فیلتر بلوم به مثبت کاذب بخورد و خروجی اشتباه به ما بدهد. به عنوان مثال، می‌توانیم چندین فیلتر بلوم را به صورت متوالی قرار دهیم، به این صورت که در فیلتر بلوم هر لایه، مثبت‌های کاذب لایهٔ قبلی را نگه داریم؛ در زمان پرس‌وجو، کافی است اولین لایه‌ای (مانند ) را پیدا کنیم که عضو مربوطه در لایه یافت می‌شود اما در لایهٔ یافت نمی‌شود. در صورتی که فرد باشد، می‌توان گفت پاسخ اصلی مثبت است، و در صورتی که فرد باشد، می‌توان گفت که پاسخ منفی است. حال اگر برای نگه‌داری هر کاراکتر در رئوس این گراف، به ۲ بیت نیاز داشته باشیم، به‌ازای یک رشته ۱۶-تایی از ژنوم‌ها، به ۶۴ بیت حافظه نیاز داریم. اما با استفاده از یک بلوم فیلتر (به عنوان مثال در الگوریتم Minia مطالعه خصوصیت‌های توالی‌ها طبقه‌بندی توالی‌های یک رشته DNA قسمت وسیعی از تحقیقات بیوانفورماتیک را شامل می‌شود. به عنوان مثال، در مطالعات فراژنومی، گاهی لازم است بدانیم یک قسمت از یک ژنوم، نسبت به یک پایگاه‌داده‌ی مرجع، متعلق به یک جاندار جدید است یا خیر. | ## جمع‌بندی | به این ترتیب که داده‌های پایگاه مرجع را در فیلتر بلوم اضافه می‌کنیم، و سپس رشته‌های مورد بررسی را در آن پرس‌وجو می‌کنیم.