مسئله بزرگ‌ترین زیردنباله مشترک

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

بزرگترین زیردنباله مشترک (به انگلیسی: Longest Common Subsequence)، روشی است که برای پیدا کردن بزرگترین زیردنباله در مجموعه‌ای از دنباله‌ها (غالباً دو دنباله) به کار می‌رود و مساله‌ای قدیمی در علم کامپیوتر است و همین طور اساس کار برنامه‌های مقایسه کننده فایل است که تفاوت دو فابل را نمایش می‌دهد. همین طور در بیوانفورماتیک برای مقایسه رشته‌های دی ان ای کاربرد دارد.

شرح مساله[ویرایش]

دو رشته زیر را در نظر بگیرید:


S_{1}=ACCGGTCGAGTGCGCGGAGCCGGCCGAA\,\!


S_{2}=GTCGTTCGGAATGCCGTTGCTCTGTAAA\,\!

هدف مقایسه این دو رشته و پیدا کردن شباهت بین آنها است. بزرگترین زیردنباله مشترک این طور تعریف می‌شود که دنباله‌ای مانند S_{3} است به طوری که حروف موجود در S_{3} با حفظ ترتیب در S_{1} و S_{2} موجود باشد. اما مطلقاً لزومی ندارد که متوالی باشد. از طرفی S_{3} باید بزرگترین دنباله ممکن با خواص بالا باشد. به طور کلی اگر دو رشته X=\langle x_{1},x_{2},... ,x_{n}\rangle و Y=\langle y_{1},y_{2},... ,y_{n}\rangle را در نظر بگیریم٫ یک بلندترین زیر دنباله مشترک را می‌توان با استفاده از برنامه نویسی پویا پیدا کرد.

راه حل برای دو دنباله[ویرایش]

مساله LCS دارای خصوصیت زیر ساختار بهینه (Optimal Substructure) است:

مساله LCS را می‌توان به زیر مساله‌های کوچکتر تقسیم نمود.

که این زیر مساله‌ها جفت دنباله‌های پیشوندی دو دنباله ورودی هستند. اگر داشته باشیم: X=\langle x_{1},x_{2},... ,x_{n}\rangle٫ آن گاه X_{i} به این صورت تعریف می‌شود: X_{i}=\langle x_{1},x_{2},... ,x_{i}\rangle

فرض کنید X=\langle x_{1},x_{2},... ,x_{m}\rangle و Y=\langle y_{1},y_{2},... ,y_{n}\rangle دو رشته باشند و Z=\langle z_{1},z_{2},... ,z_{k}\rangle بلندترین زیردنباله مشترک یا LCS دو رشته Y و X باشند. پیاده سازی الگوریتم با استفاده از روش برنامه نویسی پویا به این صورت است:

۱)اگر X_{m}=Y_{n}\,\! باشد٫ آن گاه Z_{k}=X_{m}=Y_{n} و Z_{k-1} یک LCS برای Y_{k-1} و X_{k-1} است.

۲)اگر X_{m}\ne\; Y_{n} باشد٫ آن گاه Z_{k}\ne\;X_{m} نتیجه می‌دهد که Z یک LCS برای Y و X_{m-1} است.

۳)اگر X_{m}\ne\; Y_{n} باشد٫ آن گاه Z_{k}\ne\;Y_{m} نتیجه می‌دهد که Z یک LCS برای Y_{n-1} و X است.

قضیه فوق نشان می‌دهد: LCS دو رشته٫ در داخل خودش٫ حاوی یک LCS برای پیشوندهای آن دو رشته نیز می‌باشد.

یک راه حل بازگشتی برای پیداکردن LCS[ویرایش]

فرض کنید c[i,j]\,\! یک عنصر از آرایه C باشد که نشان دهنده طول LCS دو دنبالهX_{i} و Y_{i} است. بنابراین اگر i=0 یا j=0 باشد٫ یکی از دنباله‌ها دارای طول صفر است و در نتیجه LCS دو دنباله صفر خواهد شد. 
c[i,j] =
 \begin{cases}
 0 & i=0\ or\ j=0 \\
  c[i-1,j-1]+1 & i,j>0\ and\ X_{i}= Y_{j} \\
 max(c[i-1,j],c[i,j-1]) & i,j>0\ and\ X_{i}\ne Y_{j}
 \end{cases}
 بنابراین وقتی که X_{i}\ne\; Y_{j} باشد٫ زیر مساله ما پیدا کردن LCS برای X_{i-1} و Y_{i-1} است. در غیر این صورت ما دو زیر مساله داریم:

پیدا کردن LCS برای Y_{i} و X_{i-1} و

پیدا کردن LCS برای Y_{i-1} و X_{i}

شکل ۱

االگوریتم را با استفاده از روش برنامه نویسی پویا پیاده سازی می‌کنیم. الگوریتم دو رشته X=\langle x_{1},x_{2},... ,x_{m}\rangle و Y=\langle y_{1},y_{2},... ,y_{n}\rangle را به عنوان ورودی دریافت می‌کند(شکل ۲). الگوریتم مقادیر c[i,j]\,\! که نشان دهدنده طول LCS است را داخل آرایه c[1..m,1..n]\,\! ذخیره می‌کند. عناصر آرایه به ترتیب row-major پر می‌شوند. یهنی ابتدا اولین سطر c به ترتیب از چپ به راست پر می‌شود، سپس سطر دوم و الی آخر. علاوه بر این الگوریتم آرایه دیگری به نام b[1..m,1..n]\,\! را نیز پر می‌کند. این آرایه جهت حرکت را ذخیره می‌کند.

شکل ۲

مقدار b با علامت‌های جهت \leftarrow,\uparrow,\nwarrow پر می‌شود. همین طور مقدار c[i,j]\,\! به این بستگی دارد که آیا x_i=y_i باشد (خط ۹). جهت فلش‌ها طوری انتخاب می‌شود که همواره حرکت به سمت خانه‌ای با طول LCS بزرکتر را تضمین می‌کند. در نهایت برای پیدا کردن LCS از گوشه سمت راست و پایین آرایه b در جهت پیکان‌ها به سمت گوشه بالا و چپ آرایه حرکت می‌کنیم.

function print_LCS (b,X,i,j)
  if i=0 or j=0 then
     return
  if b[i,j] = '\nwarrow' then
     print_LCS(b,X,i-1,j-1)
     print x_i
  else if b[i,j]= '\uparrow' then
     print_LCS(b,X,i,j-1)
  else print_LCS(b,X,i,j-1)

پیچیدگی زمانی[ویرایش]

زمانی که تعداد دنباله‌های ورودی ثابت باشند٫ این مساله توسط برنامه نویسی پویا در زمان چندجمله‌ای حل می‌شود. فرض کنید N دنباله ورودی به طول n_1,n_2,... ,n_N داشته باشیم. یک راه حل ابتدایی برای جستجوی LCS این است که هر یک از2^{n_1} زیردنباله دنباله اولی را برررسی کنیم که آیا زیر دنباله برای دیگر دنباله‌های ورودی است یا خیر. هر زیر ددنباله در زمانی خطی متناسب با طول دنباله‌های باقی مانده بررسی می‌شود. بنابراین زمان الگوریتم برابر خواهد بود با:O\left(2^{n_1} \sum_{i>1} n_i\right). برای حالت ورودی با دو دنباله با n و m عنصر٫ پیچیدگی زمانی الگوریتم برابر O(mn)\,\! خواهد بود. برای تعداد ورودی‌های دلخواه برنامه نویسی پویا راه حلی با این زمان ارایه می‌کند:O\left(N \prod_{i=1}^{N} n_i\right).

توابعی با پیچیدگی کمتر موجود است،[۱]

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

  1. L. Bergroth and H. Hakonen and T. Raita. A Survey of Longest Common Subsequence Algorithms. . SPIRE (IEEE Computer Society) 00 (2000): 39–48. 

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