수학(mathematics)에서, 주어진 수열(sequence)의 부분수열은 남아있는 원소의 순서를 변경없이 일부 원소를 삭제하거나 전혀 삭제하지 않고 주어진 수열에서 파생될 수 있는 수열입니다. 예를 들어, 수열 \(\langle A,B,D \rangle\)는 원소 \(C,\) \(E,\) 및 \(F\)를 제거한 후 얻어진 \(\langle A,B,C,D,E,F \rangle\)의 부분수열입니다. 한 수열이 또 다른 수열의 부분수열인 것의 관계는 준순서(preorder)입니다.
부분수열은 원래 수열에서 연속적이지 않은 연속적인 원소를 포함할 수 있습니다. \(\langle A,B,C,D,E,F \rangle\)에서 \(\langle B,C,D \rangle\)와 같은 원래 수열에서 원소의 연속 실행으로 구성된 부분수열은 부분문자열(substring)입니다. 부분문자열은 부분수열의 세분화입니다.
단어 "apple"의 모든 부분수열의 목록은 "a", "ap", "al", "ae", "app", "apl", "ape", "ale", "appl", "appe", "aple", "apple", "p", "pp", "pl", "pe", "ppl", "ppe", "ple", "pple", "l", "le", "e", "" (빈 문자열)입니다.
Common subsequence
두 수열 \(X\)와 \(Y\)가 주어지면, 수열 \(Z\)는 만약 \(Z\)가 \(X\)와 \(Y\) 둘 다의 부분수열이면 \(X\)와 \(Y\)의 공통 부분수열이라고 말합니다. 예를 들어, 만약 다음이면
\(\quad X = \langle A,C,B,D,E,G,C,E,D,B,G \rangle \qquad \text{ and}\)
\(\quad Y = \langle B,E,G,J,C,F,E,K,B \rangle \qquad \text{ and}\)
\(\quad Z = \langle B,E,E \rangle.\)
\(Z\)는 \(X\)와 \(Y\)의 공통 부분수열이라고 말합니다.
이것은 가장 긴 공통 부분수열이 아닐 것인데, 왜냐하면 \(Z\)는 오직 길이 3을 가지고, 공통 부분수열 \(\langle B,E,E,B \rangle\)는 길이 4를 가지기 때문입니다. \(X\)와 \(Y\)의 가장 긴 공통 부분수열은 \(\langle B,E,G,C,E,B \rangle\)입니다.
Applications
부분수열은 컴퓨터 과학(computer science), 특히 생물정보학(bioinformatics)의 분야에서 응용을 가지며, 여기서 컴퓨터는 DNA, RNA, 및 단백질(protein) 수열을 비교, 분석, 및 저장하기 위해 사용됩니다.
37개 원소를 포함하는 두 개의 DNA 수열, 말하자면 다음을 취하십시오:
수열 1과 2의 가장 긴 공통 부분수열은 다음입니다:
이것은 가장 긴 공통 부분수열의 27개 원소를 초기 수열로 강조 표시함으로써 묘사될 수 있습니다:
이것을 보여주는 또 다른 방법은 두 수열을 배열, 즉, 가장 긴 공통 부분수열의 원소를 같은 열 (수직 막대로 표시됨)에 배치하고 발생된 빈 부분수열의 패딩을 위한 특수 문자 (여기서, 대시)를 도입하는 것입니다:
부분수열은 DNA 염기: 아데닌, 구아닌, 시토신, 및 티민을 사용하여 두 가닥의 DNA가 얼마나 유사한지를 결정하기 위해 사용됩니다.
Theorems
- 실수(real number)의 모든 무한 수열은 무한 단조(monotone) 부분수열을 가집니다 (이것은 볼차노–바이어슈트라스 정리의 증명에 사용된 보조 정리입니다).
- \(\mathbb{R}^n\)에서 모든 각 무한 경계진 수열(bounded sequence)은 수렴(convergent) 부분수열을 가집니다 (이것이 볼차노–바이어슈트라스 정리(Bolzano–Weierstrass theorem)입니다).
- 모든 정수(integer) \(r\)과 \(s\)에 대해, 길이 적어도 \((r - 1)(s - 1) + 1\)의 모든 각 유한 수열은 길이 \(r\)의 단조적으로 증가하는 부분수열 또는 길이 \(s\)의 단조적으로 감소하는 부분수열을 포함합니다 (이것은 에르되시–세케레스 정리(Erdős–Szekeres theorem)입니다.
See also
