부분 수열

1. 개요

부분 수열은 주어진 수열의 원소들을 원래 순서를 유지하면서 일부를 선택하여 얻는 수열이다. 수열 X와 Y가 주어졌을 때, Z가 X와 Y 모두의 부분 수열이면 Z는 X와 Y의 공통 부분 수열이다. 부분 수열은 순서론적, 해석학적 성질을 가지며, 모든 실수 수열은 단조 부분 수열을 갖는다. 부분 수열은 컴퓨터 과학, 특히 생물정보학에서 DNA, RNA, 단백질 서열 비교 및 분석에 활용된다. 또한 에르되스-세케레시 정리, 볼차노-바이어슈트라스 정리, 콤팩트 거리 공간 등과 관련이 있다.

2. 정의

집합 $X$ 위의 두 수열 $(x\_n)\_\{n\backslash in\backslash mathbb\; N\}$, $(y\_n)\_\{n\backslash in\backslash mathbb\; N\}$ ($x\_n,y\_n\backslash in\; X$)이 주어졌다고 하자. 만약 다음 두 조건을 만족시키는 함수 $n\_\backslash bullet\backslash colon\backslash mathbb\; N\backslash to\backslash mathbb\; N$이 존재한다면, 수열 $(y\_n)\_\{n\backslash in\backslash mathbb\; N\}$이 수열 $(x\_n)\_\{n\backslash in\backslash mathbb\; N\}$의 부분 수열이라고 한다.

* $n\_\backslash bullet$는 순증가 함수이다.
* 임의의 자연수 $k\backslash in\backslash mathbb\; N$에 대하여, $y\_k=x\_\{n\_k\}$

두 개의 수열 $X$와 $Y$가 주어졌을 때, 수열 $Z$가 $X$와 $Y$ 모두의 부분 수열이라면, $Z$는 $X$와 $Y$의 "공통 부분 수열"이라고 한다. 예를 들어 다음과 같다.

$$X\; =\; \backslash langle\; A,C,B,D,E,G,C,E,D,B,G\; \backslash rangle$$
$$Y\; =\; \backslash langle\; B,E,G,J,C,F,E,K,B\; \backslash rangle$$
$$Z\; =\; \backslash langle\; B,E,E\; \backslash rangle$$

$Z$는 $X$와 $Y$의 공통 부분 수열이지만, 최장 공통 부분 수열은 아니다. 왜냐하면 $Z$는 길이가 3이고, 공통 부분 수열 $\backslash langle\; B,E,E,B\; \backslash rangle$는 길이가 4이기 때문이다. $X$와 $Y$의 최장 공통 부분 수열은 $\backslash langle\; B,E,G,C,E,B\; \backslash rangle$이다.

2.1. 순증가 함수

부분 수열을 정의하는 데 사용되는 함수는 순증가 함수의 조건을 만족해야 한다. 즉, 임의의 자연수 $k\backslash in\backslash mathbb\; N$에 대하여

3. 성질

부분 수열은 원순서적 성질과 위상 공간에서의 수렴성과 관련된 해석학적 성질을 갖는다. 위상 공간에서 수열이 수렴하는 것과 모든 부분 수열이 수렴하는 것은 동치이다. 또한, 위상 공간에서 어떤 점으로 수열이 수렴하는 것과, 그 수열의 모든 부분 수열이 해당 점으로 수렴하는 것은 동치이다. 모든 실수 수열은 단조 부분 수열을 가지며, 모든 유계 실수 수열은 수렴 부분 수열을 갖는다 (볼차노-바이어슈트라스 정리).

3.1. 순서론적 성질

집합 $X$ 위의 수열들의 집합 $X^\{\backslash mathbb\; N\}$ 위에서, 부분 순서 관계는 원순서를 이룬다. 즉, 모든 수열은 자기 자신을 부분 수열로 가지며, 부분 수열의 부분 수열은 원래 수열의 부분 수열이다. 만약 $X$의 크기가 2 이상일 경우, 부분 순서 관계는 부분 순서가 아니며, 동치 관계도 아니다. 예를 들어, 서로 다른 두 실수 수열

(0, 1, 0, 1, ...)

(1, 0, 1, 0, ...)

은 서로의 부분 수열이다.

3.2. 해석학적 성질

위상 공간 $X$ 위의 수열에 대하여, 다음 두 조건은 서로 동치이다.

* 수렴한다.
* 모든 부분 수열이 수렴한다.

위상 공간 $X$ 위의 수열 $(x\_n)\_\{n\backslash in\backslash mathbb\; N\}\backslash subseteq\; X$ 및 점 $x\backslash in\; X$에 대해서도, 다음 두 조건이 서로 동치이다.
* $(x\_n)\_\{n\backslash in\backslash mathbb\; N\}$은 $x$로 수렴한다.
* $(x\_n)\_\{n\backslash in\backslash mathbb\; N\}$의 모든 부분 수열 $(x\_\{n\_k\})\_\{k\backslash in\backslash mathbb\; N\}$은 $x$로 수렴하는 부분 수열 $(x\_\{n\_\{k\_j\}\})\_\{j\backslash in\backslash mathbb\; N\}$을 갖는다.

3.2.1. 실수 수열의 성질

모든 실수 수열은 단조 부분 수열을 가지며, 모든 유계 실수 수열은 수렴 부분 수열을 갖는다(볼차노-바이어슈트라스 정리).

* 모든 무한 실수 수열은 무한 단조 부분 수열을 갖는다(이는 볼차노-바이어슈트라스 정리 증명에 사용되는 보조 정리이다).
* $\backslash R^n$의 모든 무한 유계 수열은 수렴하는 부분 수열을 갖는다(이는 볼차노-바이어슈트라스 정리이다).
* 모든 정수 $r$과 $s$에 대해, 길이가 최소 $(r\; -\; 1)(s\; -\; 1)\; +\; 1$인 모든 유한 수열은 길이 $r$인 단조 증가 부분 수열 또는 길이 $s$인 단조 감소 부분 수열을 포함한다(이는 에르되스-세케레시 정리이다).

4. 예시

음이 아닌 정수의 열 (0, 1, 2, 3, ...)은 음이 아닌 짝수의 열 (0, 2, 4, ...)을 부분 수열로 갖는다.

5. 응용

부분 수열은 컴퓨터 과학, 특히 생물정보학에서 DNA, RNA, 단백질 서열 분석 등에 활용된다.

5.1. 생물정보학에서의 활용

부분 수열은 컴퓨터 과학, 특히 컴퓨터를 사용하여 DNA, RNA, 단백질 서열을 비교, 분석 및 저장하는 생물정보학 분야에서 활용된다.

부분 수열은 아데닌, 구아닌, 시토신, 티민 DNA 염기를 사용하여 두 가닥의 DNA가 얼마나 유사한지를 결정하는 데 사용된다.

예를 들어, 37개의 요소를 포함하는 두 개의 DNA 서열이 있다고 가정해 보자.

:SEQ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
:SEQ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

서열 1과 2의 최장 공통 부분 수열은 다음과 같다.

:LCS_(SEQ1,SEQ2) = CGTTCGGCTATGCTTCTACTTATTCTA

이는 최장 공통 부분 수열의 27개 요소를 원래 서열에서 강조 표시하여 설명할 수 있다.

:SEQ₁ = ACG^영어GT^영어GTCG^영어TGCTATGCT^영어GAT^영어GCT^영어GACTTAT^영어AT^영어GCTA^영어
:SEQ₂ = CGTTCGGCTAT^영어CG^영어TAC^영어GTTCTA^영어TTCT^영어AT^영어GATT^영어TCTA^영어A

이를 보여주는 또 다른 방법은 두 서열을 정렬하는 것이다. 즉, 최장 공통 부분 수열의 요소를 동일한 열에 배치하고 (세로 막대로 표시) 발생한 빈 부분 수열의 패딩을 위해 특수 문자 (여기서는 대시)를 도입하는 것이다.
:SEQ₁ = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA-
:        | || ||| ||||| |  | |  | || |  || | || |  |||
:SEQ₂ = -C-GT-TCG-GCTATCGTACGT--T-CT-ATTCTATGAT-T-TCTAA

6. 정리

모든 무한 실수 수열은 무한 단조 부분 수열을 갖는다. 이는 볼차노-바이어슈트라스 정리 증명에 사용되는 보조 정리이다.

6.1. 에르되스-세케레시 정리

모든 정수 $r$과 $s$에 대해, 길이가 최소 $(r\; -\; 1)(s\; -\; 1)\; +\; 1$인 모든 유한 수열은 길이 $r$인 단조 증가 부분 수열 또는 길이 $s$인 단조 감소 부분 수열을 포함한다. 이는 에르되스-세케레시 정리이다.

6.2. 볼차노-바이어슈트라스 정리

볼차노-바이어슈트라스 정리에 따르면, $\backslash mathbb\{R\}^n$의 모든 유계 수열은 수렴하는 부분 수열을 갖는다.

6.3. 콤팩트 거리 공간

거리 공간 $(X,d)$에서, $X$의 모든 수열이 $X$에 속하는 극한을 갖는 수렴하는 부분 수열을 가지면 콤팩트하다.