books solve the two sequences

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

البادئات

المشاكل الثانويه تصبح ابسط كلما أصبحت المتسلسله أقصر . المتتاليات القصيرة تم وصفها باستخدام مصطلح " البادئه " . بدايه المتسلسله هي عبارة عن متسلسله بدون نهايه . بفرض ان s هي المتسلسله ( AGCA) ثم نعتبر (AG ) واحدة من بادئات ال S . البادئات ترمز لاسم المتسلسله متبوعه بشرح يشير الي عدد حروف البادئه . البادئه (ِAG) تعبر عن ال S2 . بما أنها تحتوي علي أول عنصرين من S . البادئات الممكن لل S هي

S₁ = A

S₂ = AG

S₃ = AGC

S₄ = AGCA.

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

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

في العموم، للمتسلسلتين X, Y بطول n , m بالإشارة للعنصر x₁ ل x_n و y₁ ل y_m و البادئات X₁ ل X_n-1 و Y₁ ل "Y_m-1

و بهذا

x_n=y_m

LCS(X_n, Y_m) = LCS( X_n-1, Y_m-1) ^ x_n

الخاصية الثانيه

بفرض ان المتسلسلتين x و y لا تنتهي بنفس العنصر، اذن ال LCS لهما يصبح الأطول بين المتسلسلتين LCS(X_n,Y_m-1)و LCS(X_n-1,Y_m) . لفهم هذة الخاصية بفرض ان المتسلسلتين كالاتي المتسلسله X: ABCDEFG المتسلسله Y: BCDGK ال LCS للمتسلسلتين اما ينتهي ب G أو لا

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

الحالة الثانية : عندما لا تحتوي ال LCS علي عنصر ال G و بهذا حذف ال G2 من المتسلسله x و بهذا تستطيع كتابه LCS(X_n,Y_m) = LCS(X_n-1, Y_m).

في أي حاله ,الLCS الذي نبحث عنه هو واحد من LCS(X_n, Y_m-1) أو LCS(X_n-1, Y_m) و بهذا يكون LCS(X,Y) الأطول بين المتسلسلات

تعريف الـ LCS

بفرض ان المتسلسلتين يتم تعريفهم كالاتي X = =x₁, x₂...x_m و Y = y₁, y₂...y_n . البادئات ل x هي X_{1, 2,...m} ; و البادئه y هي =Y_{1, 2,...n}., 2,...n .

بفرض ان LCS"X_i, Y_j تعبر عن مجموعه من أطول تسلسل مشنرك في البادئات Xi و Yj, مجموعه المتتاليات ممكن وصفها كالاتي

لإيجاد أطول تسلسل مشترك لل X_i و Y_j , قارن العناصر x_i و y_j , إذا تساوت العناصر، اذن تزداد المتسلسله( LCS(X_i-1, )Y_j-1) إذا لم تتساوي، يتم حفظ أطول متسلسه من (LCS(X_i-1,Y_j

مثال

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

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

(LCS(R₁, C₁ تعرف عن طريق مقارنه أول عنصر من كل متتاليه حيث G و A مختلفين لذلك، باستخدام الخاصية الثانية لإيجاد أطول متسلسله من (LCS(R₁, C₀ و (LCS(R₀, C₁ . رجوعا للجدول، كلا من المتسلسلات فارغين لذلك (LCS(R₁, C₁ أيضا فارغ كما هو موضح بالجدول . الاسهم تعبر عن اتجاه المتسلسله من الخليا العليا والخلبه علي اليسار .

(LCS(R₁, C₂ يمكن التعرف عليها عن طريق مقارنه ال G مع ال G . في حاله التشابه، يتم اضافه G للمتسلسله (LCS(R₀, C₁ التي هي (Ø) لتصبح (ØG) التي هي (G)

لـ (LCS(R₁, C₃ الـ G و ال C مختلفان وبالتالي تكون المتسلسله فارغه، الخلية علي اليسار تحتوي علي العنصر G باختيار أطول متسلسله من (LCS(R₁, C₃ يكون G . نشير الاسهم لليسار بما أنها المتسلسله الأطول بين المتسلسلتين .

(LCS(R₁, C₄ ، وبالمثل، هو (G). (LCS(R₁, C₅ ، وبالمثل، هو (G).

لـ (LCS(R₂, C₁ تتم مقارنه A مع ال A . عند التشابه، يتم اضافه A للخانه Ø لتصبح A

لـ (LCS(R₂, C₂ و C و A مختلفان والمتسلسله( LCS(R₁, C₂ تحتوي علي المتسلسلات A و G : حيث (LCS(R₁, C₂ هي G التي هي موجودة أيضا في (LCS(R₂, C₁ . و بهذا تكون النتيجة ان LCS(R2, C3) تحتوي علي A و G

لـ (LCS(R₂, C₄ تتم مقارنه A مع ال A . عند التشابه، يتم اضافه A للخانه الاعلي علي اليسار لتصبح GA

لـ (LCS(R₂, C₅ و C,A مختلفان، لذلك (LCS(R₂, C₅ تصبح أطول متسلسله A

لـ (LCS(R₃, C₁ و G ,C مختلفان . و كلا من ( LCS(R₃, C₁ و LCS(R2,C2) لهم عنصر واحد . وبهذا تكون النتيجة ان (LCS(R₂, C₂ تحتوي علي متسلسلتان جزئيتان A و G

لـ (LCS(R₃, C₃ , ال C و ال C متشابهان لذلك يتم اضافه C لـ (LCS(RLCS(R₂, C₂, الذي يحتوي على متسلسلتان جزئيتان A و G لتصبح النتيجة النهائيه AC و GC

لـ (LCS(R₃, C₄ و C,A مختلفان، وبدمج (LCS(R₃, C₃ الذي يحتوي على (AC) و (GC) و (LCS(R₂, C₄ الذي يحتوي على (GA) , نحصل علي نتيجه (AC), (GC), و (GA).

و اخيرا لـLCS(R₃,C₅) C و T لا يتشابهان وبهذا تكون النتيجة (LCS(R₃, C₅ تحتوي أيضا علي (AC), (GC), و (GA).

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

نهج ال Traceback

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

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