後続

数学において、与えられた数列の部分列とは、与えられた数列から、いくつかの要素を削除するか、要素をまったく削除せずに、残りの要素の順序を変更せずに派生できる数列のことです。たとえば、数列は、要素を削除した後に得られるの部分列であり、1 つの数列が別の数列の部分列であるという関係は、前順序です。 ${\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」、「」(空の文字列) になります。

2つのシーケンスとシーケンスが与えられ、がとの両方の部分列である場合、シーケンスはと の共通部分列であると言われます 。たとえば、の場合、 はとの共通部分列であると言われます。${\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.}$

これは最長共通部分列ではない。なぜならの長さは 3 のみで、共通部分列 の長さは 4 であるからである。との最長共通部分列は${\displaystyle Z}$${\displaystyle \langle B,E,E,B\rangle }$${\displaystyle X}$${\displaystyle Y}$${\displaystyle \langle B,E,G,C,E,B\rangle .}$

サブシーケンスはコンピュータサイエンスに応用されており^{[1] 、特に}バイオインフォマティクスの分野ではコンピュータを使用してDNA、RNA、タンパク質の配列を比較、分析、保存します。

たとえば、37 個の要素を含む DNA 配列を 2 つ取ります。

SEQ ₁ = 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

これを示す別の方法は、 2 つのシーケンスを揃えることです。つまり、最長共通サブシーケンスの要素を同じ列 (縦棒で示されます) に配置し、発生した空サブシーケンスを埋めるために特殊文字 (ここではダッシュ) を導入します。

配列₁ = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA-

        | || ||| ||||| | | | | || | || | || | |||

配列₂ = -C-GT-TCG-GCTATCGTACGT--T-CT-ATTCTATGAT-T-TCTAA

サブシーケンスは、DNA 塩基であるアデニン、グアニン、シトシン、チミンを使用して、2 本の DNA 鎖の類似性を判断するために使用されます。

• 実数の無限列には必ず無限単調部分列が存在する（これはボルツァーノ・ワイエルシュトラスの定理の証明に用いられる補題である）。
• のすべての無限有界列には収束する部分列が存在する(これがボルツァーノ・ワイエルシュトラスの定理である)。${\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}$

• 後続の極限 – ある部分列の極限
• 上限と下限 – シーケンスの境界Pages displaying short descriptions of redirect targets
• 最長増加部分列問題 – コンピュータサイエンスの問題Pages displaying short descriptions of redirect targets

この記事にはPlanetMathの subsequence の資料が組み込まれており、これはCreative Commons Attribution-Share-Alike Licenseに基づいてライセンスされています。