مدل بندی مساله هضم جزئی بصورت مساله شبکه جریان

نگاشت نقاط مرزی یکی از مسائل جالب توجه در زیست شناسی محاسباتی به شمار می رود. یک رشته DNA به صورت دنباله ای از حروف A, T, C, G می باشد. هنگامی که یک آنزیم محدود کننده به یک محلول DNA اضافه می شود، مولکول DNA از مکان های خاصی بریده می شود. هدف از نگاشت نقاط مرزی پیدا کردن نقاط برش برای یک آنزیم معین است. در روش هضم جزیی، برشها طوری انجام می شود که فاصله دو به دوی همه نقاط برش حاصل شود. در بیان ریاضی مساله، فاصله دو به دوی n نقطه واقع بر یک پاره خط داده شده است و هدف بدست آوردن خود این نقاط است. در بیوانفورماتیک این مساله به مساله هضم جزیی معروف شده است. در این مقاله یک مدل شبکه جریان تعمیم یافته برای مساله ارایه می دهیم. با توجه به اینکه کلاس پیچیدگی این مساله یکی از قدیمی ترین و مهمترین مسایل باز در بیوانفورماتیک نظری است(تاکنون نه الگوریتمی با زمان چند جمله ای و نه اثباتی بر Np-complete بودن آن ارایه شده است)، کاهش مساله هضم جزیی به مساله شبکه جریان دریچه جدیدی را برای چالش با این مساله می گشاید.