أطول تسلسل مشترك (رياضيات)
مسألة أطول تسلسل مشترك هي مشكلة إيجاد أطول تتابع مشترك لكل المتتاليات في مجموعة من المتسلسلات ( متسلسلتين فقط في كثير من الأحيان) إنها تختلف عن مشكلة أخرى في إيجاد سلاسل فرعية، على عكس المتسلسلة الفرعية، المتسلسلات الجزئية لا تتطلب شغل مراتب متتالية داخل المتسلسلة الأصلية. مشكلة أطول تسلسل مشترك تعتبر مشكلة علوم حاسب كلاسيكية، ولها تطبيقات في المعلوماتية الحيوية. كما أنها تستخدم على نطاق واسع من قبل أنظمة التحكم مثل GIT للتوفيق بين العديد من التغيرات علي مجموعة من الملفات.
للحالة العامة من أي عدد من تسلسل المدخلات, المشكلة هي NP-hard عندما يكون عدد المتسلسلات ثابت, المشكلة تكون قابلة للحل في وقت كثير الحدود عن طريق البرمجة الديناميكية.
بفرض ان هناك عدد متسلسلات formula_1 بطولformula_2 . البحث الخاطئ يقوم باختيار كل formula_3 متتالية من المتتاليات لتحديد ما إذا كانت أيضا هي المتتالية الجزئية للمتتاليات الأخرى. كل جزء من المتتالية يمكن اختيارة في الوقت, لذلك يمكن وصف الوقت لهذة الخوارزمية كالاتي :
formula_4
في هذة الحالة المتتاليتين "n" و "m", الوقت المستهلك للبرمجة الديناميكيه يكون O("n" × "m")
لكل رقم من المتتابعة, البرمجة الديناميكية تعطي حل في
هذة الطرق اقل تعقيدا, التي غالبا تعتمد علي طول ال LSC , حجم الحروف أو كلاهما 
لاحظ ان ال LSC ليست فريدة , علي سبيل المثال ال LSC للحروف ‘ABC ‘ و ‘ACB ‘ هي نفسها ‘AB’ و ‘AC‘, في الواقع غالبا ما يتم تعريف المشكلة LSC علي ان تكون إيجاد جميع المتتاليات المشتركة ذات أكبر طول.
هذه المشكلة لها أكبر قدر من التعقيد حيث كان عدد المتسلسلات رقم أسي.
مشاكل الLSC لها كيان امثل : المشكلة ممكن تقسيمها الي مشاكل اصغر وابسط حيث يمكن تقسيمها الي مشاكل اصغر و هكذا. في النهاية الحل يصبح صغير جدا. مشاكل الLSC لها أيضا مشاكل ثانوية متداخلة.
الحل لاعلي مرحله من المشاكل الثانية غالبا يعيد استخدام المشاكل الثانويه للمرحله الأقل . المشاكل ذات هاتان الخاصيتان " الكبان الامثل و المشاكل الثانويه المتداخله " يمكن أن تصاغ عن طريق تقنيه حل المشكلات تسمي البرمجه الديناميكبه . حيث أنها تقوم بحفظ الحل بدلا من حسابه مرارا و تكرارا . الخطوات تتطلب memorization لحفظ الحلول لكل مرحله من المشاكل الثانويه في الجدول , و بهذا تكون الحلول متوفرة للمراحل المتقدمه من المشاكل الثانويه .
المشاكل الثانويه تصبح ابسط كلما أصبحت المتسلسله أقصر . المتتاليات القصيرة تم وصفها باستخدام مصطلح " البادئه " . بدايه المتسلسله هي عبارة عن متسلسله بدون نهايه . بفرض ان s هي المتسلسله ( AGCA) ثم نعتبر (AG ) واحدة من بادئات ال S . البادئات ترمز لاسم المتسلسله متبوعه بشرح يشير الي عدد حروف البادئه . البادئه (ِAG) تعبر عن ال S2 . بما أنها تحتوي علي أول عنصرين من S . البادئات الممكن لل S هي
بفرض ان متسلسلتين ينتهون عند نفس العنصر . لإيجاد LSC للمتتاليه يجب تقصيرها بأزاله آخر عنصر , ثم إيجاد LSC المتتاليه الجديدة بعد التقصير ثم الحاق العنصر الذي تم ازالته مجددا للمتسلسله . علي سبيل المثال , هناك متتاليتين لهما نفس العنصر الاخير (ATANA) و (BANANA) . قم بأزاله آخر عنصر و استمر بإعادة الخطوات حتي تصل لمرحله يصبح التسلسل الذي تم حذفه هو (ANA) . و بهذا تصبح المتسلسله الجديدة هي (AT ) و (BAN) . ال LCS لاخر متسلسلتين (A ) , و الحاقها للعناصر التي تمت ازالتها لتكون (AANA) و هكذا تكون ال LCS للمتسلسله الاصليه.
في العموم , للمتسلسلتين "X", "Y" بطول "n" , "m" بالاشارة للعنصر "x" ل "x" و "y" ل "y"
و البادئات "X" ل "X" و "Y" ل 'Y"
و بهذا
بفرض ان المتسلسلتين x و y لا تنتهي بنفس العنصر , اذن ال LCS لهما يصبح الأطول بين المتسلسلتين LCS(X,Y)و LCS(X,Y) . لفهم هذة الخاصيه بفرض ان المتسلسلتين كالاتي 
المتسلسله X: ABCDEFG
المتسلسله Y: BCDGK
ال LCS للمتسلسلتين اما ينتهي ب G أو لا
في الحاله الأولي : ال LCS ينتهي ب G
و بهذا لا تنتهي ب K و بهذا لا يضر عند ازاله العنصر K من المتسلسله y لو كانت ال K في ال LCS و بهذا تكون LCS(X,Y) = LCS(X, Y).
الحاله الثانية :
عندما لا تحتوي ال LCS علي عنصر ال G و بهذا حذف ال G2 من المتسلسله x و بهذا تستطيع كتابه LCS(X,Y) = LCS(X, Y).
في أي حاله ,الLCS الذي نبحث عنه هو واحد من LCS(X, Y) أو LCS(X, Y) و بهذا يكون LCS(X,Y) الأطول بين المتسلسلات
بفرض ان المتسلسلتين يتم تعريفهم كالاتي "X" = ="x", "x"..."x" و "Y" = "y", "y"..."y" . البادئات ل x هي "X" ; و البادئه y هي ="Y"., 2...n .
لإيجاد أطول تسلسل مشترك لل "X" و "Y" , قارن العناصر "x" و "y" , إذا تساوت العناصر , اذن تزداد المتسلسله( "LCS"("X", )"Y") إذا لم تتساوي , يتم حفظ أطول متسلسه من ("LCS"("X","Y"
اطول تسلسل مشترك ل (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 و ال 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(R"LCS"("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). و أيضا الجدول يوضح أطول متسلسله مشتركه لكل زوج من البادئات
حساب ال LCS من صف في الجدول لا يتطلب سوي التوصل لحلول نفس الصف و الصفوف السابقه . المتسلسله الطويله يمكن أن تصبح أكبر متطلبه مساحه تخزين أكبر . مساحه التخزين من الممكن حفظها عن طريق طول المتسلسله و اتجاه الاسهم كما هو موضح بالجدول
المتسلسله الجزئيه الفعليه تم استخلاصها في خطوات Traceback التي تتبع الاسهم , ابتداء من آخر خليه بالحدول . عندما يقل طول المتسلسله يجب أن تكون لها عنصر مشترك . العديد من المسارات تصبح متاحه في الخليه التي يتوفر فيها سهمين . الجدول النهائي يوضح ما تم شرحه و الأرقام الملونه بالخليه تعبر عن طول المتسلسله
لـ formula_7 و formula_8 , طول أقصر متسلسله جزئيه مشتركه مرتبط ب طول ال LCS
و المسافه في حاله الحذف أو الاضافه أو عندما تكون تكلفه التبديل ضعف تكلفه الحذف أو الاضافه كالتالي
في الكود التالي المتسلسلات هي codice_1 و codice_2 و يتم حساب الـ بين codice_3 و codice_4 لكل codice_5 و codice_6 و تقوم بحفظها في 
codice_7 . و يحتوي codice_8 علي طول الـ LCS
الكود التالي به تنخفض الاختيارات عند حساب جدول C , إذا كان آخر عنصر من البادئات متساوي , يجب أن تكون في الـ LCS بالاحتفاظ بـ X و Y
اذا كان اختيار X و Y سوف يعطينا نتيجه طويله , فقم بقراءة نتائج المتسلسلات الجزئيه . لاحظ ان هذة الداله ليست كثيرة الحدود
لاحظ انك سوف تجد اجابات مختلفه في كل مرة تقوم بتغير ≥ و  و ≤
بفرض ان X هي XMJYAUZ و Y هي MZJAWXU. أطول متسلسله جزئيه مشتركه بين X و Y هي MJAU . الجدول C الموضح بالاسفل يبين لنا طول أطول متسلسله جزئيه مشتركه بين البادئات . صفوف الـ i و اعمدة j تظهر طول الـ LCS 
الارقام الملونه تظهر مسار الداله من الاسفل الي الاعلي . عند تساوي ال x و y يكونا جزء من ال LCS و تتحرك للاعلي بأتجاه اليسار و في حاله عدم التساوي يكون المسار للاعلي او لليسار معتمدة علي الخليه ذات اعلي رقم
يمكن اجراء بعض التحسينات علي الخوارزميه المذكورة اعلاه لتسريعها
المصفوفه C في الخوارزميه تنمو تربيعيا بالتناسب مع طول المتتاليات للمصفوفتين ذات ال 100 عنصر , مصفوفه 10.000 عنصر مطلوبه و مطلوب حدوث 10.000 مقارنه
في أفضل سيناريو، وتسلسل بدون أي تغييرات، وهذا من شأنه ان يقضي تماما على الحاجة إلى المصفوفة C. في السيناريو الأسوأ، أي تغيير على البنود الأولى والأخيرة في تسلسل، لا يتم تنفيذ سوى اثنين من المقارنات إضافية.
معظم الوقت المستغرق من قبل خوارزمية بسيطه يمر في أداء المقارنات بين العناصر في متواليات. لمتواليات نصية مثل شفرة المصدر، وكنت ترغب في عرض خطوط باعتبارها عناصر تسلسل بدلا من أحرف واحدة. هذا يمكن أن يعني مقارنات سلاسل طويلة نسبيا لكل خطوة في الخوارزمية. ويمكن إجراء اثنين من التحسينات التي يمكن أن تساعد على تقليل الوقت المستهلك في هذه المقارنات.
إذا كنت بحاجة لطول LCS، يمكن تقليل المصفوفة ل formula_11 مصفوفة بكل سهولة، أو ل formula_12 حيث أن البرمجة الديناميكية يحتاج فقط الأعمدة الحالية والسابقة للمصفوفة. خوارزمية هرشبيرغ تسمح للبناء التسلسل الأمثل نفسها في نفس الوقت من الدرجة الثانية .
بدءا (Chvátal & Sankoff (1975 عدد من الباحثين التحقيق في سلوك أطول مدة subsequence مشتركه عندما يتم رسم اثنين من سلاسل معينة بشكل عشوائي من نفس الأبجدية. عندما يكون حجم الأبجدية هو ثابت، والطول المتوقع للLCS يتناسب مع طول السلسلتين، وثوابت التناسب (اعتمادا على حجم الأبجدية) والمعروفة باسم الثوابت Chvátal-Sankoff