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

نگاشت نقاط مرزی یکی از مسائل جالب توجه در زیست شناسی محاسباتی به شمار می‌رود. یک رشته dna به صورت دنباله‌ای از حروف a, t, c, g می‌باشد. هنگامی که یک آنزیم محدود کننده به یک محلول dna اضافه می‌شود، مولکول dna از مکان‌های خاصی بریده می شود. هدف از نگاشت نقاط مرزی پیدا کردن نقاط برش برای یک آنزیم معین است. در روش هضم جزیی، برشها طوری انجام می‌شود که فاصله دو به دوی همه نقاط برش حاصل شود. در بیان ریاضی مساله، فاصله دو به دوی n نقطه واقع بر یک پاره خط داده شده است و هدف بدست آوردن خود این نقاط است. در بیوانفورماتیک این مساله به مساله هضم جزیی معروف شده است. در این مقاله یک مدل شبکه جریان تعمیم یافته برای مساله ارایه می‌دهیم. با توجه به اینکه کلاس پیچیدگی این مساله یکی از قدیمی‌ترین و مهمترین مسایل باز در بیوانفورماتیک نظری است(تاکنون نه الگوریتمی با زمان چند جمله ای و نه اثباتی بر npcomplete بودن آن ارایه شده است)، کاهش مساله هضم جزیی به مساله شبکه جریان دریچه جدیدی را برای چالش با این مساله می‌گشاید.