Approximate Pattern Matching

Approximate Pattern Matching

패천이 정확하게 일치하지 않더라도 유사한 부분 문자열을 찾는 과정

 

Exhaustive search 적용 방법

여기서 k 는 mismatch를 얼마나 허용할건지에 대한 변수이다.

시간복잡도: O(nm)

 

Dynamic Programming을 적용한 방법

같으면 +0, 다르면 +1

		A	G	C	C	T	T	G	A	T
	0	0	0	0	0	0	0	0	0	0
G	0	1	0	1	1	1	1	0	1	1
C	0	1	2	0	1	2	2	2	1	2
A	0	0	2	3	1	2	3	3	2	2
T	0	1	1	3	4	1	2	4	4	2

가장 아래 값이 K이하인 경우 accept