رضا ندیمی

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