مرجع
آخر الزيارات

أطول تسلسل مشترك (رياضيات)

2٬104 كلمة•0 مشاهدة•🗒️ منذ 18 يوماً
باختصار: مسألة أطول تسلسل مشترك هي مشكلة إيجاد أطول تتابع مشترك لكل المتتاليات في مجموعة من المتسلسلات (متسلسلتين فقط في كثير من الأحيان) إنها تختلف عن مشكلة أخرى في إيجاد سلاسل فرعية، على عكس المتسلسلة الفرعية، المتسلسلات الجزئية لا تتطلب شغل مراتب…. في هذه المقالة 34 قسماً: «if C[i-1,j] ≥ C[i,j-1]»، «تقليل المشاكل» و«مثال» وغيرها.
المحتويات
  1. if C[i-1,j] ≥ C[i,j-1]
  2. تقليل المشاكل
  3. مثال
  4. تعريف الـ LCS
  5. العلاقة مع المشاكل الاخري
  6. if C[i,j-1] ≥ C[i-1,j]
  7. مثال
  8. for j := start..n_end
  9. if C[i,j-1] > C[i-1,j]
  10. البادئات
  11. حساب طول الـ LCS
  12. المتسلسله Y: BCDGK
  13. n_end := n_end - 1
  14. else if X[i] = Y[j]
  15. قراءة LCS
  16. else if X[i] = Y[j]
  17. تقليل وقت المقارنة
  18. تقليل المساحة المطلوبة
  19. طباعه الفرق
  20. الخاصية الاولي
  21. قراءة جميع LCS
  22. نمذجه الكود
  23. print " " + X[i]
  24. else
  25. else
  26. نهج ال Traceback
  27. n_end := n
  28. else
  29. start := start + 1
  30. سلوك متسلسلات عشوائيه
  31. print "+ " + Y[j]
  32. التعقيد
  33. حل المتتاليتين
  34. S3 = AGC
أطول تسلسل مشترك (رياضيات)

بدايةً، مسألة أطول تسلسل مشترك هي مشكلة إيجاد أطول تتابع مشترك لكل المتتاليات في مجموعة من المتسلسلات (متسلسلتين فقط في كثير من الأحيان) إنها تختلف عن مشكلة أخرى في إيجاد سلاسل فرعية، على عكس المتسلسلة الفرعية، المتسلسلات الجزئية لا تتطلب شغل مراتب متتالية داخل المتسلسلة الأصلية. مشكلة أطول تسلسل مشترك تعتبر مشكلة علوم حاسب كلاسيكية، ولها تطبيقات في المعلوماتية الحيوية. كما أنها تستعمل على نطاق واسع من قبل أنظمة التحكم مثل GIT للتوفيق بين الكثير من التغيرات علي مجموعة من الملفات. ونتناول فيما يلي مزيدًا من التفاصيل.

if C[i-1,j] ≥ C[i,j-1]

R := R ∪ backtrackAll(C, X, Y, i-1, j)

return R

تقليل المشاكل

  • function LCS(X[1..m], Y[1..n])
  • start := 1
  • m_end := m

كذلك، المصفوفه C في الخوارزميه تنمو تربيعيا بالتناسب مع طول المتتاليات للمصفوفتين ذات ال 100 عنصر، مصفوفه 10.000 عنصر مطلوبه ومطلوب حدوث 10.000 مقارنه

مثال

وفي هذا السياق، الارقام الملونه تظهر مسار الدالة من الاسفل الي الاعلي. عند تساوي ال x و y يكونا جزء من ال LCS وتتحرك للاعلي بأتجاه اليسار وفي حاله عدم التساوي يكون المسار للاعلي أو لليسار معتمدة علي الخلية ذات اعلي رقم

في هذا الإطار، بفرض ان X هي XMJYAUZ و Y هي MZJAWXU. أطول متسلسله جزئيه مشتركه بين X و Y هي MJAU . الجدول C الموضح بالاسفل يبين لنا طول أطول متسلسله جزئيه مشتركه بين البادئات. صفوف الـ i واعمدة j تظهر طول الـ LCS

تعريف الـ LCS

من جانب آخر، بفرض ان LCSXi, Yj تعبر عن مجموعه من أطول تسلسل مشنرك في البادئات Xi و Yj, مجموعه المتتاليات ممكن وصفها كالاتي:

من جهة ثانية، لإيجاد أطول تسلسل مشترك لل Xi و Yj , قارن العناصر xi و yj , إذا تساوت العناصر، اذن تزداد المتسلسله (LCS(Xi-1,)Yj-1) إذا لم تتساوي، يتم حفظ أطول متسلسه من (LCS(Xi-1,Yj

ومن جهة أخرى، بفرض ان المتسلسلتين يتم تعريفهم كالاتي X = =x1, x2...xm و Y = y1, y2...yn . البادئات ل x هي X1, 2,...m ; والبادئه y هي =Y1, 2,...n., 2,...n .

العلاقة مع المشاكل الاخري

كود لحل البرمجة الديناميكيه

من جانب آخر، و المسافة في حاله الحذف أو الاضافه أو عندما تكون تكلفه التبديل ضعف تكلفه الحذف أو الاضافه كالتالي:

لـ و , طول أقصر متسلسله جزئيه مشتركه مرتبط ب طول ال LCS

if C[i,j-1] ≥ C[i-1,j]

R := R ∪ backtrackAll(C, X, Y, i, j-1)

مثال

وفي هذا السياق، لـ (LCS(R3, C3 , ال C وال C متشابهان لذلك يتم اضافه C لـ (LCS(RLCS(R2, C2, الذي يحتوي على متسلسلتان جزئيتان A و G لتصبح النتيجة النهائيه AC و GC

  • (LCS(R1, C4 ، وبالمثل، هو (G).
  • (LCS(R1, C5 ، وبالمثل، هو (G).
  • لـ (LCS(R2, C1 تتم مقارنه A مع ال A . عند التشابه، يتم اضافه A للخانه Ø لتصبح A

وعلى صعيد آخر، (LCS(R1, C2 يمكن التعرف عليها عن طريق مقارنه ال G مع ال G . في حاله التشابه، يتم اضافه G للمتسلسله

(LCS(R0, C1 التي هي (Ø) لتصبح (ØG) التي هي (G)

من جهة ثانية، هذا الجدول يستعمل لتخزين المتسلسله LCS لكل خطوة من الحسابات. العمود الثاني والصف الثاني بهم Ø لان عند وجود عنصر فارغ يتم مقارنته بعنصر آخر غير فارغ، يكون وبهذا يكون أطول تسلسل مشترك فارغ

من جانب آخر، لـ (LCS(R2, C2 و C و A مختلفان والمتسلسله (LCS(R1, C2 تحتوي علي المتسلسلات A و G : حيث (LCS(R1, C2 هي G التي هي موجودة كذلك في (LCS(R2, C1 . وبهذا تكون النتيجة ان LCS(R2, C3) تحتوي علي A و G

وفي السياق ذاته، أطول تسلسل مشترك ل (C = (AGCAT, و (R = (GAC يمكن إيجادها لان داله ال LCS تستعمل عناصر صفريه، يكون من المناسب تعريف البادئه التي قيمتها صفر بـ C0 = Ø ; و R0 = Ø جميع البادئات يتم وضعها في جدول كالتالي:

وعلى صعيد آخر، (LCS(R1, C1 تعرف عن طريق مقارنه أول عنصر من كل متتاليه حيث G و A مختلفين لذلك، باستخدام الخاصية الثانية لإيجاد أطول متسلسله من (LCS(R1, C0 و (LCS(R0, C1 . رجوعا للجدول، كلا من المتسلسلات فارغين لذلك (LCS(R1, C1 كذلك فارغ كما هو موضح بالجدول. الاسهم تعبر عن اتجاه المتسلسله من الخليا العليا والخلبه علي اليسار.

وفي هذا السياق، و اخيرا لـLCS(R3,C5) C و T لا يتشابهان وبهذا تكون النتيجة (LCS(R3, C5 تحتوي كذلك علي (AC), (GC), و (GA).

إضافةً إلى ذلك، لـ (LCS(R2, C4 تتم مقارنه A مع ال A . عند التشابه، يتم اضافه A للخانه الاعلي علي اليسار لتصبح GA

وعلى صعيد آخر، لـ (LCS(R1, C3 الـ G وال C مختلفان وبالتالي تكون المتسلسله فارغه، الخلية علي اليسار تحتوي علي العنصر G باختيار أطول متسلسله من (LCS(R1, C3 يكون G . نشير الاسهم لليسار بما أنها المتسلسله الأطول بين المتسلسلتين.

ومن جهة أخرى، لـ (LCS(R3, C1 و G ,C مختلفان. وكلا من (LCS(R3, C1 و LCS(R2,C2) لهم عنصر واحد. وبهذا تكون النتيجة ان (LCS(R2, C2 تحتوي علي متسلسلتان جزئيتان A و G

وفي هذا السياق، لـ (LCS(R3, C4 و C,A مختلفان، وبدمج (LCS(R3, C3 الذي يحتوي على (AC) و (GC) و (LCS(R2, C4 الذي يحتوي على (GA), نحصل علي نتيجه (AC), (GC), و (GA).

وفي هذا السياق، لـ (LCS(R2, C5 و C,A مختلفان، لذلك (LCS(R2, C5 تصبح أطول متسلسله A

وفي هذا السياق، النتيجة الأخيرة ان آخر خليه في الجدول تحتوي علي جميع أطول متسلسلات جزئيه مشتركه لـ (AGCAT) و (GAC) الا وهي (AC), (GC), و (GA). وأيضا الجدول يوضح أطول متسلسله مشتركه لكل زوج من البادئات

for j := start..n_end

the algorithm continues as before ...

وعلى صعيد آخر، في أفضل سيناريو، وتسلسل بدون أي تغييرات، وهذا من شأنه ان يقضي تماما على الحاجة إلى المصفوفة C. في السيناريو الأسوأ، أي تغيير على البنود الأولى والأخيرة في تسلسل، لا يتم تنفيذ سوى اثنين من المقارنات إضافية.

if C[i,j-1] > C[i-1,j]

return backtrack(C, X, Y, i, j-1)

البادئات

S2 = AG

علاوةً على ذلك، المشاكل الثانويه تصبح ابسط كلما أصبحت المتسلسله أقصر. المتتاليات القصيرة تم وصفها باستخدام مصطلح «البادئه». بدايه المتسلسله هي عبارة عن متسلسله بدون نهايه. بفرض ان s هي المتسلسله (AGCA) ثم نعتبر (AG) واحدة من بادئات ال S . البادئات ترمز لاسم المتسلسله متبوعه بشرح يشير الي عدد حروف البادئه. البادئه (ِAG) تعبر عن ال S2 . بما أنها تحتوي علي أول عنصرين من S . البادئات الممكن لل S هي:S1 = A

حساب طول الـ LCS

  • C[i,j] . ويحتوي C[m,n] علي طول الـ LCS
  • function LCSLength(X[1..m], Y[1..n])
  • C = array(0..m, 0..n)
  • for i := 0..m
  • C[i,0] = 0
  • for j := 0..n
  • C[0,j] = 0
  • for i := 1..m
  • for j := 1..n
  • if X[i] = Y[j]
  • C[i,j] := C[i-1,j-1] + 1

من جانب آخر، في الكود التالي المتسلسلات هي X[1..m] و Y[1..n] ويتم حساب الـ بين X[1..i] و Y[1..j] لكل 1 ≤ i ≤ m و 1 ≤ j ≤ n وتقوم بحفظها في

المتسلسله Y: BCDGK

كذلك، و بهذا لا تنتهي ب K وبهذا لا يضر عند ازاله العنصر K من المتسلسله y لو كانت ال K في ال LCS وبهذا تكون LCS(Xn,Ym) = LCS(Xn, Ym-1).الحالة الثانية:

ال LCS للمتسلسلتين اما ينتهي ب G أو لا

في الحالة الأولي: ال LCS ينتهي ب G

وفي السياق ذاته، عندما لا تحتوي ال LCS علي عنصر ال G وبهذا حذف ال G2 من المتسلسله x وبهذا تستطيع كتابه LCS(Xn,Ym) = LCS(Xn-1, Ym).

علاوةً على ذلك، في أي حاله، الLCS الذي نبحث عنه هو واحد من LCS(Xn, Ym-1) أو LCS(Xn-1, Ym) وبهذا يكون LCS(X,Y) الأطول بين المتسلسلات

n_end := n_end - 1

  • C = array(start-1..m_end, start-1..n_end)
  • only loop over the items that have changed
  • for i := start..m_end

else if X[i] = Y[j]

  • return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
  • else
  • R := {}

قراءة LCS

ومن جهة أخرى، الكود التالي به تنخفض الاختيارات عند حساب جدول C , إذا كان آخر عنصر من البادئات متساوي، يجب أن تكون في الـ LCS بالاحتفاظ بـ X و Y

  • function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)
  • if i = 0 or j = 0
  • return ""

else if X[i] = Y[j]

else

return backtrack(C, X, Y, i-1, j-1) + X[i]

تقليل وقت المقارنة

في هذا الإطار، أغلب الوقت المستغرق من قبل خوارزمية بسيطه يمر في أداء المقارنات بين العناصر في متواليات. لمتواليات نصية مثل شفرة المصدر، وكنت ترغب في عرض خطوط باعتبارها عناصر تسلسل بدلا من أحرف واحدة. هذا يمكن أن يعني مقارنات سلاسل طويلة نسبيا لكل خطوة في الخوارزمية. ويمكن إجراء اثنين من التحسينات التي يمكن أن تساعد على تقليل الوقت المستهلك في هذه المقارنات.

تقليل المساحة المطلوبة

من جهة ثانية، إذا كنت بحاجة لطول LCS، يمكن تقليل المصفوفة ل مصفوفة بكل سهولة، أو ل حيث أن البرمجة الديناميكية يحتاج فقط الأعمدة الحالية والسابقة للمصفوفة. خوارزمية هرشبيرغ تسمح للبناء التسلسل الأمثل نفسها في نفس الوقت من الدرجة الثانية.

طباعه الفرق

  • لاحظ انك سوف تجد اجابات مختلفه في كل مرة تقوم بتغير ≥ و <, بـ > و ≤
  • function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
  • if i > 0 and j > 0 and X[i] = Y[j]
  • printDiff(C, X, Y, i-1, j-1)

الخاصية الاولي

من جهة ثانية، و البادئات X1 ل Xn-1 و Y1 ل 'Ym-1و بهذا: xn=ym LCS(Xn, Ym) = LCS(Xn-1, Ym-1) ^ xn الخاصية الثانية

وفي السياق ذاته، بفرض ان المتسلسلتين x و y لا تنتهي بنفس العنصر، اذن ال LCS لهما يصبح الأطول بين المتسلسلتين LCS(Xn,Ym-1)و LCS(Xn-1,Ym). لفهم هذة الخاصية بفرض ان المتسلسلتين كالاتي

علاوةً على ذلك، بفرض ان متسلسلتين ينتهون عند نفس العنصر. لإيجاد LSC للمتتاليه يجب تقصيرها بأزاله آخر عنصر، ثم إيجاد LSC المتتاليه الجديدة بعد التقصير ثم الحاق العنصر الذي تم ازالته مجددا للمتسلسله. مثلًا، هناك متتاليتين لهما نفس العنصر الاخير (ATANA) و (BANANA). قم بأزاله آخر عنصر واستمر بإعادة الخطوات حتي تصل لمرحله يصبح التسلسل الذي تم حذفه هو (ANA). وبهذا تصبح المتسلسله الجديدة هي (AT) و (BAN). ال LCS لاخر متسلسلتين (A), والحاقها للعناصر التي تمت ازالتها لتكون (AANA) وهكذا تكون ال LCS للمتسلسله الاصليه.

المتسلسله X: ABCDEFG

وفي هذا السياق، في العموم، للمتسلسلتين X, Y بطول n , m بالإشارة للعنصر x1 ل xn و y1 ل ym

قراءة جميع LCS

كذلك، إذا كان اختيار X و Y سوف يعطينا نتيجه طويله، فقم بقراءة نتائج المتسلسلات الجزئية. لاحظ ان هذة الدالة ليست كثيرة الحدود

  • function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
  • if i = 0 or j = 0
  • return {""}

نمذجه الكود

وعلى صعيد آخر، يمكن إجراء بعض التحسينات علي الخوارزميه المذكورة اعلاه لتسريعها

print " " + X[i]

else if j > 0 and (i = 0 or C[i,j-1] ≥ C[i-1,j])

printDiff(C, X, Y, i, j-1)

else

return backtrack(C, X, Y, i-1, j)

else

C[i,j] := max(C[i,j-1], C[i-1,j])

return C[m,n]

نهج ال Traceback

وعلى صعيد آخر، حساب ال LCS من صف في الجدول لا يتطلب سوي التوصل لحلول نفس الصف والصفوف السابقه. المتسلسله الطويله يمكن أن تصبح أكبر متطلبه مساحه تخزين أكبر. مساحه التخزين من الممكن حفظها عن طريق طول المتسلسله واتجاه الاسهم كما هو موضح بالجدول

وعلى صعيد آخر، المتسلسله الجزئية الفعليه تم استخلاصها في خطوات Traceback التي تتبع الاسهم، ابتداء من آخر خليه بالحدول. عندما يقل طول المتسلسله يجب أن تكون لها عنصر مشترك. الكثير من المسارات تصبح متاحه في الخلية التي يتوفر فيها سهمين. الجدول النهائي يوضح ما تم شرحه والأرقام الملونه بالخلية تعبر عن طول المتسلسله

n_end := n

إضافةً إلى ذلك، while start ≤ m_end and start ≤ n_end and X[start] = Y[start]

trim off the matching items at the beginning

else

print ""

start := start + 1

  • trim off the matching items at the end
  • while start ≤ m_end and start ≤ n_end and X[m_end] = Y[n_end]
  • m_end := m_end - 1

سلوك متسلسلات عشوائيه

انظر كذلك

أطول متتالية جزئية متزايدة

من جانب آخر، بدءا (Chvátal & Sankoff (1975 عدد من الباحثين التحقيق في سلوك أطول مدة subsequence مشتركه عندما يتم رسم اثنين من سلاسل معينة بشكل عشوائي من نفس الأبجدية. عندما يكون حجم الأبجدية هو ثابت، والطول المتوقع للLCS يتناسب مع طول السلسلتين، وثوابت التناسب (اعتمادا على حجم الأبجدية) والمعروفة باسم الثوابت Chvátal-Sankoff

print "+ " + Y[j]

  • else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])
  • printDiff(C, X, Y, i-1, j)
  • print "- " + X[i]

التعقيد

وفي السياق ذاته، لاحظ ان ال LSC ليست فريدة، مثلًا ال LSC للحروف ‘ABC ‘ و ‘ACB ‘ هي نفسها ‘AB’ و ‘AC‘, في الواقع غالبا ما يتم تعريف المشكلة LSC علي ان تكون إيجاد جميع المتتاليات المشتركة ذات أكبر طول.

إضافةً إلى ذلك، في هذة الحالة المتتاليتين n و m, الوقت المستهلك للبرمجة الديناميكيه يكون O(n × m)

وفي هذا الصدد، للحالة العامة من أي عدد من تسلسل المدخلات، المشكلة هي NP-hard عندما يكون عدد المتسلسلات ثابت، المشكلة تكون قابلة للحل في وقت كثير الحدود عن طريق البرمجة الديناميكية.

لكل رقم من المتتابعة، البرمجة الديناميكية تعطي حل في:

ومن ناحية أخرى، هذه المشكلة لها أكبر قدر من التعقيد حيث كان عدد المتسلسلات رقم أسي.

وفي هذا السياق، هذة الطرق اقل تعقيدا، التي غالبا تعتمد علي طول ال LSC , حجم الحروف أو كلاهما

إضافةً إلى ذلك، بفرض ان هناك عدد متسلسلات بطول . البحث الخاطئ يقوم باختيار كل متتالية من المتتاليات لتحديد ما إذا كانت كذلك هي المتتالية الجزئية للمتتاليات الأخرى. كل جزء من المتتالية يمكن اختيارة في الوقت، لذلك يمكن وصف الوقت لهذة الخوارزمية كالاتي:

حل المتتاليتين

كذلك، مشاكل الLSC لها كيان امثل: المشكلة ممكن تقسيمها الي مشاكل اصغر وابسط حيث يمكن تقسيمها الي مشاكل اصغر وهكذا. في النهاية الحل يصبح صغير جدا. مشاكل الLSC لها كذلك مشاكل ثانوية متداخلة.

كذلك، الحل لاعلي مرحله من المشاكل الثانية غالبا يعيد استخدام المشاكل الثانويه للمرحله الأقل. المشاكل ذات هاتان الخاصيتان «الكبان الامثل والمشاكل الثانويه المتداخله» يمكن أن تصاغ عن طريق تقنيه حل المشكلات تسمي البرمجة الديناميكبه. حيث أنها تقوم بحفظ الحل بدلا من حسابه مرارا وتكرارا. الخطوات تتطلب memorization لحفظ الحلول لكل مرحله من المشاكل الثانويه في الجدول، وبهذا تكون الحلول متوفرة للمراحل المتقدمه من المشاكل الثانويه.

S3 = AGC

S4 = AGCA.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.