الگوریتم سریع مرزبندی دنباله ها در بیوانفورماتیک با استفاده از بلوم فیلتر

دراین مقاله الگوریتمی برای مرزبندی دنباله ها در بیوانفورماتیک با استفاده از بلوم فیلتر ارائه میشود. ایده بکار گرفته شده در این پژوهش یافتن زیررشته های همسان در دو دنباله و مرزبندی با استفاده از این زیررشته ها میباشد. برای تعیین زیررشته های همسان از بلوم فیلتر که عملیات مقایسه را سرعت میبخشد استفاده میشود. هدف از ارائه این الگوریتم سرعت بخشیدن به انجام عملیات مرزبندی دنباله ورودی با شبیه ترین دنباله ی پایگاه داده، در مقایسه باروشهای گذشته میباشد. با استفاده از این الگوریتم پیچیدگی زمانی از O(m^2 در روش برنامه سازی پویا به O(m برای مقایسه دو دنباله، که m طول دنباله میباشد، کاهش یافته است

کلیدواژه ها:

بلوم فیلتر ، رشته ورودی ، رشته هدف ، زیررشته