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

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

التعقيد

للحالة العامة من أي عدد من تسلسل المدخلات، المشكلة هي NP-hard عندما يكون عدد المتسلسلات ثابت، المشكلة تكون قابلة للحل في وقت كثير الحدود عن طريق البرمجة الديناميكية. بفرض ان هناك عدد متسلسلات $N$ بطول$n_{1},...,n_{N}$ . البحث الخاطئ يقوم باختيار كل $2^{n_{1}}$ متتالية من المتتاليات لتحديد ما إذا كانت أيضا هي المتتالية الجزئية للمتتاليات الأخرى. كل جزء من المتتالية يمكن اختيارة في الوقت، لذلك يمكن وصف الوقت لهذة الخوارزمية كالاتي:

$O\left(2^{n_{1}}\sum _{i>1}n_{i}\right).$

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

لكل رقم من المتتابعة، البرمجة الديناميكية تعطي حل في:$O\left(N\prod _{i=1}^{N}n_{i}\right).$

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

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

مشاكل ال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'Xi, Yj تعبر عن مجموعه من أطول تسلسل مشنرك في البادئات Xi و Yj, مجموعه المتتاليات ممكن وصفها كالاتي:$LCS\left(X_{i},Y_{j}\right)={\begin{cases}\emptyset &{\mbox{ if }}\ i=0{\mbox{ or }}j=0\\{\textrm {}}LCS\left(X_{i-1},Y_{j-1}\right)\frown x_{i}&{\mbox{ if }}x_{i}=y_{j}\\{\mbox{longest}}\left(LCS\left(X_{i},Y_{j-1}\right),LCS\left(X_{i-1},Y_{j}\right)\right)&{\mbox{ if }}x_{i}\neq y_{j}\\\end{cases}}$

لإيجاد أطول تسلسل مشترك لل 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 Strings

	0	A	G	C	A	T
0	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø
A	Ø
C	Ø

هذا الجدول يستخدم لتخزين المتسلسله 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).

"G" Row Completed

	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\overset {\ \ \uparrow }{\leftarrow }}$Ø	${\overset {\nwarrow }{\ }}$(G)	${\overset {\ }{\leftarrow }}$(G)	${\overset {\ }{\leftarrow }}$(G)	${\overset {\ }{\leftarrow }}$(G)
A	Ø
C	Ø

لـ (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

"G" & "A" Rows Completed

	Ø	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(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).

Completed LCS Table

	Ø	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). وأيضا الجدول يوضح أطول متسلسله مشتركه لكل زوج من البادئات

نهج ال Traceback

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

Storing length, rather than sequences

	Ø	A	G	C	A	T
Ø	0	0	0	0	0	0
G	0	${\overset {\ \ \uparrow }{\leftarrow }}$0	${\overset {\nwarrow }{\ }}$1	${\overset {\ }{\leftarrow }}$1	${\overset {\ }{\leftarrow }}$1	${\overset {\ }{\leftarrow }}$1
A	0	${\overset {\nwarrow }{\ }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\nwarrow }{\ }}$2	${\overset {\ }{\leftarrow }}$2
C	0	${\overset {\ \uparrow }{\ }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\nwarrow }{\ }}$2	${\overset {\ \ \uparrow }{\leftarrow }}$2	${\overset {\ \ \uparrow }{\leftarrow }}$2

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

Traceback example

	Ø	A	G	C	A	T
Ø	0	0	0	0	0	0
G	0	${\overset {\ \ \uparrow }{\leftarrow }}$0	${\overset {\nwarrow }{\ }}$1	${\overset {\ }{\leftarrow }}$1	${\overset {\ }{\leftarrow }}$1	${\overset {\ }{\leftarrow }}$1
A	0	${\overset {\nwarrow }{\ }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\nwarrow }{\ }}$2	${\overset {\ }{\leftarrow }}$2
C	0	${\overset {\ \uparrow }{\ }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\nwarrow }{\ }}$2	${\overset {\ \ \uparrow }{\leftarrow }}$2	${\overset {\ \ \uparrow }{\leftarrow }}$2

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

لـ $X_{1\dots m}$ و $Y_{1\dots n}$ , طول أقصر متسلسله جزئيه مشتركه مرتبط ب طول ال LCS

$\left|SCS(X,Y)\right|=n+m-\left|LCS(X,Y)\right|.$

و المسافة في حاله الحذف أو الاضافه أو عندما تكون تكلفه التبديل ضعف تكلفه الحذف أو الاضافه كالتالي:$d'(X,Y)=n+m-2\cdot \left|LCS(X,Y)\right|.$

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

حساب طول الـ LCS

في الكود التالي المتسلسلات هي X[1..m] و Y[1..n] ويتم حساب الـ بين X[1..i] و Y[1..j] لكل 1 ≤ i ≤ m و 1 ≤ j ≤ n وتقوم بحفظها في 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
else
C[i,j] := max(C[i,j-1], C[i-1,j])
return C[m,n]

قراءة 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]
return backtrack(C, X, Y, i-1, j-1) + X[i]
else
if C[i,j-1] > C[i-1,j]
return backtrack(C, X, Y, i, j-1)
else
return backtrack(C, X, Y, i-1, j)

قراءة جميع 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 {""}
else if X[i] = Y[j]
return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
else
R := {}
if C[i,j-1] ≥ C[i-1,j]
R := R ∪ backtrackAll(C, X, Y, i, j-1)
if C[i-1,j] ≥ C[i,j-1]
 R := R ∪ backtrackAll(C, X, Y, i-1, j)
 return R

طباعه الفرق

لاحظ انك سوف تجد اجابات مختلفه في كل مرة تقوم بتغير ≥ و <, بـ > و ≤

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)
 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)
 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]
else
 print ""

مثال

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

		0	1	2	3	4	5	6	7
		Ø	M	Z	J	A	W	X	U
0	Ø	0	0	0	0	0	0	0	0
1	X	0	0	0	0	0	0	1	1
2	M	0	1	1	1	1	1	1	1
3	J	0	1	1	2	2	2	2	2
4	Y	0	1	1	2	2	2	2	2
5	A	0	1	1	2	3	3	3	3
6	U	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4

نمذجه الكود

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

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

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

function LCS(X[1..m], Y[1..n])
 start := 1
 m_end := m
 n_end := n
 trim off the matching items at the beginning
 while start ≤ m_end and start ≤ n_end and X[start] = Y[start]
  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
  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
  for j := start..n_end
    the algorithm continues as before ...

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

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

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

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

إذا كنت بحاجة لطول LCS، يمكن تقليل المصفوفة ل $2\times \min(n,m)$ مصفوفة بكل سهولة، أو ل $\min(m,n)+1$ حيث أن البرمجة الديناميكية يحتاج فقط الأعمدة الحالية والسابقة للمصفوفة. خوارزمية هرشبيرغ تسمح للبناء التسلسل الأمثل نفسها في نفس الوقت من الدرجة الثانية.

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

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

انظر أيضا

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