部分列

数学において、与えられた数列の部分列とは、与えられた数列から、残りの要素の順序を変えずに、いくつかの要素を削除するか、全く要素を削除しないことで得られる数列のことです。例えば、数列は要素を削除した後に得られる数列の部分列です。ある数列が別の数列の部分列であるという関係は、半順序です。 ${\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 個の要素を含む 2 つの DNA 配列を考えてみましょう。

SEQ ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

シーケンス 1 と 2 の最長共通部分シーケンスは次のとおりです。

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

これは、最初のシーケンスの最長共通部分列の 27 要素を強調表示することで説明できます。

SEQ ₁ = 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 つのシーケンスを揃えることです。つまり、最長共通サブシーケンスの要素を同じ列 (垂直バーで示されます) に配置し、発生した空サブシーケンスを埋めるために特殊文字 (ここではダッシュ) を導入します。

SEQ ₁ = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA-

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

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

注記

1. コンピュータサイエンスでは、文字列はシーケンスの同義語としてよく使われますが、部分文字列と部分シーケンスは同義語ではないことに注意することが重要です。部分文字列は文字列の連続した部分ですが、部分シーケンスは必ずしもそうではありません。つまり、文字列の部分文字列は常に文字列の部分シーケンスですが、文字列の部分シーケンスは必ずしも文字列の部分文字列ではないということです。Gusfield , Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology . USA: Cambridge University Press. p. 4. ISBN 0-521-58519-8。

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