تسلسل

في الرياضيات ، المتتالية الجزئية لمتتالية معينة هي متتالية يمكن اشتقاقها من المتتالية المعطاة بحذف بعض العناصر أو عدم حذف أي منها دون تغيير ترتيب العناصر المتبقية. على سبيل المثال، المتتالية${\displaystyle \langle A,B,D\rangle }$هو تسلسل فرعي من${\displaystyle \langle A,B,C,D,E,F\rangle }$تم الحصول عليها بعد إزالة العناصر${\displaystyle C,}$${\displaystyle E,}$و${\displaystyle F.}$إن العلاقة بين تسلسل ما وتسلسل فرعي لتسلسل آخر هي ترتيب جزئي .

يمكن أن تحتوي المتتاليات الفرعية على عناصر متتالية لم تكن متتالية في المتتالية الأصلية. المتتالية الفرعية التي تتكون من سلسلة متتالية من العناصر من المتتالية الأصلية، مثل${\displaystyle \langle B,C,D\rangle ,}$من${\displaystyle \langle A,B,C,D,E,F\rangle ,}$هي سلسلة فرعية . السلسلة الفرعية هي تحسين للسلسلة الفرعية.

ستكون قائمة جميع التسلسلات الفرعية للكلمة " apple " هي " a " و " ap " و " al " و " ae " و " app " و " apl " و " ape " و " ale " و " appl " و " appe " و " aple " و " apple " و " p " و " pp " و " pl " و " pe " و " ppl " و " ppe " و " ple " و " pple " و " l " و " le " و " e " و "" ( سلسلة فارغة ).

بفرض وجود متتابعتين${\displaystyle X}$و${\displaystyle Y,}$تسلسل${\displaystyle Z}$ويُقال إنها سلسلة فرعية شائعة من${\displaystyle X}$و${\displaystyle Y,}$لو${\displaystyle Z}$هو تسلسل فرعي لكليهما${\displaystyle X}$و${\displaystyle Y.}$ على سبيل المثال، إذا $${\displaystyle X=\langle A,C,B,D,E,G,C,E,D,B,G\rangle \qquad {\text{ and}}}$$$${\displaystyle Y=\langle B,E,G,J,C,F,E,K,B\rangle \qquad {\text{ and}}}$$$${\displaystyle Z=\langle B,E,E\rangle .}$$ ثم${\displaystyle Z}$ويُقال إنها سلسلة فرعية شائعة من${\displaystyle X}$و${\displaystyle Y.}$

لن تكون هذه أطول سلسلة فرعية مشتركة ، لأن${\displaystyle Z}$طولها 3 فقط، والتسلسل الفرعي المشترك${\displaystyle \langle B,E,E,B\rangle }$يبلغ طولها  4. أطول سلسلة فرعية مشتركة من${\displaystyle X}$و${\displaystyle Y}$يكون${\displaystyle \langle B,E,G,C,E,B\rangle .}$

تُستخدم التسلسلات الفرعية في علوم الحاسوب ، ^{[ 1 ]} وخاصة في مجال المعلوماتية الحيوية ، حيث تُستخدم أجهزة الكمبيوتر لمقارنة وتحليل وتخزين تسلسلات الحمض النووي DNA و RNA والبروتين .

لنأخذ سلسلتين من الحمض النووي تحتويان على 37 عنصرًا، على سبيل المثال:

التسلسل ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

التسلسل ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

أطول سلسلة فرعية مشتركة بين السلسلتين 1 و 2 هي:

LCS _{(SEQ 1 ,SEQ 2 )} = CGTTCGGCTATGCTTCTACTTATTCTA

ويمكن توضيح ذلك من خلال تسليط الضوء على العناصر الـ 27 لأطول تسلسل فرعي مشترك في التسلسلات الأولية:

التسلسل ₁ = A CG G T G TCG T GCTATGCT GA T G CT G ACTTAT A T G CTA

SEQ ₂ = CGTTCGGCTAT C G TA C G TTCTA TT CT A T G ATT T CTA A

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

التسلسل ₁ = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA-

        |  ||  |||  |||||  | | | | | || | || | |||​              

التسلسل ₂ = -C-GT-TCG-GCTATCGTACGT--T-CT-ATTCTATGAT-T-TCTAA

تُستخدم التسلسلات الفرعية لتحديد مدى تشابه سلسلتي الحمض النووي، باستخدام قواعد الحمض النووي: الأدينين ، والجوانين ، والسيتوزين ، والثايمين .

• كل متتالية لانهائية من الأعداد الحقيقية لها متتالية جزئية لانهائية رتيبة . (هذه لمة تُستخدم في برهان نظرية بولزانو-فايرشتراس ).
• كل متتالية محدودة لا نهائية في${\displaystyle \mathbb {R} ^{n}}$لها متتالية فرعية متقاربة . (هذه هي نظرية بولزانو-ويرستراس .)
• لجميع الأعداد الصحيحة${\displaystyle r}$و${\displaystyle s,}$كل متتالية محدودة طولها على الأقل${\displaystyle (r-1)(s-1)+1}$يحتوي على سلسلة فرعية متزايدة بشكل رتيب من الطول ${\displaystyle r}$أو سلسلة فرعية متناقصة بشكل رتيب من حيث الطول ${\displaystyle s}$. (هذه هي نظرية إردوس-سزكيريس ).
• فضاء متري${\displaystyle (X,d)}$تكون متراصة إذا كانت كل متتالية في${\displaystyle X}$لها متتالية جزئية متقاربة حدها في${\displaystyle X}$.

• الحد اللاحق
• حدد الأفضل وحدد الأدنى
• أطول متتالية فرعية متزايدة
• أطول سلسلة فرعية متناوبة
• أطول سلسلة فرعية مشتركة

تتضمن هذه المقالة مواد من subsequence على PlanetMath ، وهي مرخصة بموجب رخصة Creative Commons Attribution/Share-Alike .