부분 수열

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 순증가 함수
3. 성질
- 3.1. 순서론적 성질
- 3.2. 해석학적 성질
  - 3.2.1. 실수 수열의 성질
4. 예시
5. 응용
- 5.1. 생물정보학에서의 활용
6. 정리
참조

1. 개요

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

2. 정의

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

$n_\bullet$ 는 순증가 함수이다.
임의의 자연수 $k\in\mathbb N$ 에 대하여, $y_k=x_{n_k}$

두 개의 수열

X

와

Y

가 주어졌을 때, 수열

Z

가

X

와

Y

모두의 부분 수열이라면,

Z

는

X

와

Y

의 "공통 부분 수열"이라고 한다. 예를 들어 다음과 같다.

X = \langle A,C,B,D,E,G,C,E,D,B,G \rangle

Y = \langle B,E,G,J,C,F,E,K,B \rangle

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

이다.

2. 1. 순증가 함수

부분 수열을 정의하는 데 사용되는 함수는 순증가 함수의 조건을 만족해야 한다. 즉, 임의의 자연수

k\in\mathbb N

에 대하여

n_k 이다.

3. 성질

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

3. 1. 순서론적 성질

집합

X

위의 수열들의 집합

X^{\mathbb N}

위에서, 부분 순서 관계는 원순서를 이룬다.^[2] 즉, 모든 수열은 자기 자신을 부분 수열로 가지며, 부분 수열의 부분 수열은 원래 수열의 부분 수열이다. 만약

X

의 크기가 2 이상일 경우, 부분 순서 관계는 부분 순서가 아니며, 동치 관계도 아니다.^[2] 예를 들어, 서로 다른 두 실수 수열

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

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

은 서로의 부분 수열이다.

3. 2. 해석학적 성질

위상 공간

X

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

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

위상 공간

X

위의 수열

(x_n)_{n\in\mathbb N}\subseteq X

및 점

x\in X

에 대해서도, 다음 두 조건이 서로 동치이다.

$(x_n)_{n\in\mathbb N}$ 은 $x$ 로 수렴한다.
$(x_n)_{n\in\mathbb N}$ 의 모든 부분 수열 $(x_{n_k})_{k\in\mathbb N}$ 은 $x$ 로 수렴하는 부분 수열 $(x_{n_{k_j}})_{j\in\mathbb N}$ 을 갖는다.^[3]

3. 2. 1. 실수 수열의 성질

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

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

4. 예시

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

5. 응용

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

5. 1. 생물정보학에서의 활용

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

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

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

:SEQ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

:SEQ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

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

:LCS_{(SEQ₁,SEQ₂)} = '''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. 볼차노-바이어슈트라스 정리

볼차노-바이어슈트라스 정리에 따르면,

\mathbb{R}^n

의 모든 유계 수열은 수렴하는 부분 수열을 갖는다.^[3]

6. 3. 콤팩트 거리 공간

거리 공간

(X,d)

에서,

X

의 모든 수열이

X

에 속하는 극한을 갖는 수렴하는 부분 수열을 가지면 콤팩트하다.^[3]

참조

_[1] 서적 Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology Cambridge University Press
_[2] 서적
_[3] 서적

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com