أطول تسلسل مشترك (رياضيات)
حل المتتاليتين > مثال

أطول تسلسل مشترك ل (C = (AGCAT, و (R = (GAC يمكن إيجادها لان داله ال LCS تستخدم عناصر صفريه، يكون من المناسب تعريف البادئه التي قيمتها صفر بـ C0 = Ø ; و R0 = Ø جميع البادئات يتم وضعها في جدول كالتالي:
|  | 0 | A | G | C | A | T |
| --- | --- | --- | --- | --- | --- | --- |
0: Ø
| G | Ø |  |  |  |  |  |
| A | Ø |  |  |  |  |  |
| C | Ø |  |  |  |  |  |
: 
هذا الجدول يستخدم لتخزين المتسلسله LCS لكل خطوة من الحسابات. العمود الثاني والصف الثاني بهم Ø لان عند وجود عنصر فارغ يتم مقارنته بعنصر آخر غير فارغ، يكون وبهذا يكون أطول تسلسل مشترك فارغ
(LCS(R1, C1 تعرف عن طريق مقارنه أول عنصر من كل متتاليه حيث G و A مختلفين لذلك، باستخدام الخاصية الثانية لإيجاد أطول متسلسله من (LCS(R1, C0 و (LCS(R0, C1 . رجوعا للجدول، كلا من المتسلسلات فارغين لذلك (LCS(R1, C1 أيضا فارغ كما هو موضح بالجدول. الاسهم تعبر عن اتجاه المتسلسله من الخليا العليا والخلبه علي اليسار.
(LCS(R1, C2 يمكن التعرف عليها عن طريق مقارنه ال G مع ال G . في حاله التشابه، يتم اضافه G للمتسلسله 
(LCS(R0, C1 التي هي (Ø) لتصبح (ØG) التي هي (G)
لـ (LCS(R1, C3 الـ G وال C مختلفان وبالتالي تكون المتسلسله فارغه، الخلية علي اليسار تحتوي علي العنصر G باختيار أطول متسلسله من (LCS(R1, C3 يكون G . نشير الاسهم لليسار بما أنها المتسلسله الأطول بين المتسلسلتين.
(LCS(R1, C4 ، وبالمثل، هو (G).
(LCS(R1, C5 ، وبالمثل، هو (G).
|  | Ø | A | G | C | A | T |
| --- | --- | --- | --- | --- | --- | --- |
Ø: Ø
| G | Ø |  {\overset {\ \ \uparrow }{\leftarrow }}Ø |  {\overset {\nwarrow }{\ }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |
| A | Ø |  |  |  |  |  |
| C | Ø |  |  |  |  |  |
: 
لـ (LCS(R2, C1 تتم مقارنه A مع ال A . عند التشابه، يتم اضافه A للخانه Ø لتصبح A
لـ (LCS(R2, C2 و C و A مختلفان والمتسلسله (LCS(R1, C2 تحتوي علي المتسلسلات A و G : حيث (LCS(R1, C2 هي G التي هي موجودة أيضا في (LCS(R2, C1 . وبهذا تكون النتيجة ان LCS(R2, C3) تحتوي علي A و G
لـ (LCS(R2, C4 تتم مقارنه A مع ال A . عند التشابه، يتم اضافه A للخانه الاعلي علي اليسار لتصبح GA
لـ (LCS(R2, C5 و C,A مختلفان، لذلك (LCS(R2, C5 تصبح أطول متسلسله A
|  | Ø | A | G | C | A | T |
| --- | --- | --- | --- | --- | --- | --- |
Ø: Ø
| G | Ø |  {\overset {\ \ \uparrow }{\leftarrow }}Ø |  {\overset {\nwarrow }{\ }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |
| A | Ø |  {\overset {\nwarrow }{\ }}(A) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\nwarrow }{\ }}(GA) |  {\overset {\ }{\leftarrow }}(GA) |
| C | Ø |  |  |  |  |  |
: 
لـ (LCS(R3, C1 و G ,C مختلفان. وكلا من (LCS(R3, C1 و LCS(R2,C2) لهم عنصر واحد. وبهذا تكون النتيجة ان (LCS(R2, C2 تحتوي علي متسلسلتان جزئيتان A و G
لـ (LCS(R3, C3 , ال C وال C متشابهان لذلك يتم اضافه C لـ (LCS(RLCS(R2, C2, الذي يحتوي على متسلسلتان جزئيتان A و G لتصبح النتيجة النهائيه AC و GC
لـ (LCS(R3, C4 و C,A مختلفان، وبدمج (LCS(R3, C3 الذي يحتوي على (AC) و (GC) و (LCS(R2, C4 الذي يحتوي على (GA), نحصل علي نتيجه (AC), (GC), و (GA).
و اخيرا لـLCS(R3,C5) C و T لا يتشابهان وبهذا تكون النتيجة (LCS(R3, C5 تحتوي أيضا علي (AC), (GC), و (GA).
|  | Ø | A | G | C | A | T |
| --- | --- | --- | --- | --- | --- | --- |
Ø: Ø
| G | Ø |  {\overset {\ \ \uparrow }{\leftarrow }}Ø |  {\overset {\nwarrow }{\ }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |
| A | Ø |  {\overset {\nwarrow }{\ }}(A) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\nwarrow }{\ }}(GA) |  {\overset {\ }{\leftarrow }}(GA) |
| C | Ø |  {\overset {\ \uparrow }{\ }}(A) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\nwarrow }{\ }}(AC) & (GC) |  {\overset {\ \ \uparrow }{\leftarrow }}(AC) & (GC) & (GA) |  {\overset {\ \ \uparrow }{\leftarrow }}(AC) & (GC) & (GA) |
: 
النتيجة الأخيرة ان آخر خليه في الجدول تحتوي علي جميع أطول متسلسلات جزئيه مشتركه لـ (AGCAT) و (GAC) الا وهي (AC), (GC), و (GA). وأيضا الجدول يوضح أطول متسلسله مشتركه لكل زوج من البادئات