فیلتر بلوم در بیوانفورماتیک

فیلترهای بلوم در بیوانفورماتیک (به انگلیسی: Bloom filters in bioinformatics) نوعی داده‌ساختار احتمالاتی هستند که برای ذخیره‌سازی اعضای یک مجموعه، و جستجو کردن اعضا درون آن مجموعه هستند. هدف استفاده از این طراحی این است که بتوانیم تعدادی از پرس‌وجوها را با سرعت و به صورت قطعی پاسخ دهیم، و در مواقعی حافظهٔ مورد نیاز را نیز کاهش دهیم.

به عنوان مثال طراحی فیلتر بلوم به این شکل است که اگر پاسخ پرس‌وجو از فیلتر بلوم منفی باشد، قطعاً عضو مورد نظر در مجموعهٔ متناظر وجود ندارد (و این را صراحتاً می‌توانیم اعلام کنیم). اما اگر پاسخ پرس‌وجو مثبت باشد، نمی‌توان به‌طور قطع گفت که این عضو در مجموعهٔ مورد نظر وجود دارد یا خیر، و باید عملیات محاسباتی دیگری را برای تأیید یا رد حرف خود به کار بگیریم.

از این داده‌ساختار، برای بهبود حافظه و سرعت برخی از برنامه‌های کاربردی در زمینه بیوانفورماتیک به وفور استفاده می‌شود. در این مقاله، برخی از کاربردهای فیلتر بلوم در حل مسائل بیوانفورماتیک را بررسی می‌کنیم.

مقدمه[ویرایش]

فیلتر بلوم، از تعدادی تابع درهم‌ساز استفاده می‌کند و هر تابع، اعضای مجموعه را به یک اندیس از یک آرایه بیتی متناظر می‌کند. برای اضافه کردن یک عضو به فیلتر بلوم، به ازای هر تابع درهم‌ساز، آن عضو را Hash می‌کنیم و اندیس خروجی تابع را در آرایه بیتی، ۱ می‌کنیم. برای پرس‌وجو از این فیلتر نیز ورودی را به ازای تمام توابع درهم‌ساز، Hash کرده و اندیس‌های متناظر خروجی را با هم AND می‌کنیم.

مشخص است که اگر عضوی در داده‌ساختار اضافه شده باشد، تمام بیت‌های متناظر با اندیس‌های خروجی توابع، ۱ هستند و در نتیجه خروجی پرسمان نیز مثبت است (و بالطبع اگر حاصل پرسمان منفی باشد، قطعاً عضو مورد نظر در داده‌ساختار وجود ندارد)؛ اما اگر عضوی در داده‌ساختار اضافه نشده باشد نیز ممکن است پرسمان خروجی مثبت بدهد (مثبت کاذب). در روش‌های طراحی فیلتر بلوم، تلاش می‌شود تا این معیار مثبت کاذب کاهش داده شود.

کاربردها[ویرایش]

بازسازی توالی ژنوم[ویرایش]

در تحقیقات بیوانفورماتیک روی ژنوم‌ها و کارکرد هر قسمت از آن‌ها، نمی‌توان یک ژنوم را به‌طور کامل و یک‌تکه مورد بررسی قرار داد. به این منظور، ژنوم را به چندین قسمت کوچک‌تر تقسیم می‌کنند، و سپس برای یک‌پارچه‌سازی، آن‌ها را کنار هم قرار می‌دهند.

یکی از پرکاربردترین روش‌ها در این موضوع، استفاده از گراف دی‌براین است. در این گراف، به ازای هر $k$ تایی (k-mer) از رشته‌های ژنوم، یک رأس در نظر گرفته می‌شود، و بین دو رأس $A$ و $B$ در صورتی که یک $k-1$ کاراکتر آخر $A$ با $k-1$ کاراکتر ابتدای $B$ برابر باشد، یال جهت‌دار گذاشته می‌شود. برای کاهش حافظهٔ مصرفی، فیلتر بلوم را به‌کار می‌گیریم، و رئوس گراف را در یک فیلتر بلوم نگه می‌داریم. برای پیمایش گراف نیز از یک رأس، تمام ۴ حالتی که برای کاراکتر آخر رأس بعدی وجود دارد را در فیلتر بلوم پرسمان می‌کنیم.

مشکلی که این راه‌حل دارد، این است که ممکن است فیلتر بلوم به مثبت کاذب بخورد و خروجی اشتباه به ما بدهد. برای رهایی از این تله، باید راهکارهای تکمیلی را به‌کار گیریم. به عنوان مثال، می‌توانیم چندین فیلتر بلوم را به صورت متوالی قرار دهیم، به این صورت که در فیلتر بلوم هر لایه، مثبت‌های کاذب لایهٔ قبلی را نگه داریم؛ در زمان پرس‌وجو، کافی است اولین لایه‌ای (مانند $i$ ) را پیدا کنیم که عضو مربوطه در لایه $i$ یافت می‌شود اما در لایهٔ $i+1$ یافت نمی‌شود. در صورتی که $i$ فرد باشد، می‌توان گفت پاسخ اصلی مثبت است، و در صورتی که $i$ فرد باشد، می‌توان گفت که پاسخ منفی است. با این راهکار می‌توان به سادگی، پاسخ‌های مثبت کاذب را حذف کرد.

حال اگر برای نگه‌داری هر کاراکتر در رئوس این گراف، به ۲ بیت نیاز داشته باشیم، به‌ازای یک رشته ۱۶-تایی از ژنوم‌ها، به ۶۴ بیت حافظه نیاز داریم. اما با استفاده از یک بلوم فیلتر (به عنوان مثال در الگوریتم Minia

مطالعه خصوصیت‌های توالی‌ها[ویرایش]

طبقه‌بندی توالی‌های یک رشته DNA قسمت وسیعی از تحقیقات بیوانفورماتیک را شامل می‌شود. به عنوان مثال، در مطالعات فراژنومی، گاهی لازم است بدانیم یک قسمت از یک ژنوم، نسبت به یک پایگاه‌داده‌ی مرجع، متعلق به یک جاندار جدید است یا خیر. برای این منظور، به سادگی می‌توانیم از بلوم فیلتر استفاده کنیم. به این ترتیب که داده‌های پایگاه مرجع را در فیلتر بلوم اضافه می‌کنیم، و سپس رشته‌های مورد بررسی را در آن پرس‌وجو می‌کنیم. ابزارهایی همچون FACS^[۱] و BioBloom^[۲] با به‌کارگیری این روش، یک الگوریتم کارا از نظر حافظه ارائه می‌دهند.

پانویس[ویرایش]

مشارکت‌کنندگان ویکی‌پدیا. «Bloom filters in bioinformatics». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۶ ژوئن ۲۰۲۰.

منابع[ویرایش]

↑ Lundeberg, Joakim; Arvestad, Lars; Andersson, Björn; Allander, Tobias; Käller, Max; Stranneheim, Henrik (2010-07-01). "Classification of DNA sequences using Bloom filters". Bioinformatics. 26 (13): 1595–1600. doi:10.1093/bioinformatics/btq230. ISSN 1367-4803. PMC 2887045. PMID 20472541.
↑ 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-4811. PMC 4816029. PMID 25143290.

[1] Lundeberg, Joakim; Arvestad, Lars; Andersson, Björn; Allander, Tobias; Käller, Max; Stranneheim, Henrik (2010-07-01). "Classification of DNA sequences using Bloom filters". Bioinformatics. 26 (13): 1595–1600. doi:10.1093/bioinformatics/btq230. ISSN 1367-4803. PMC 2887045. PMID 20472541.

[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-4811. PMC 4816029. PMID 25143290.

[۱]

[۲]