DNA 분석은 일반인들도 많이 들어본 적이 있는 분야죠. 친자 확인이라거나 과학수사라던지.. 하지만 아직도 인간의 유전자를 통째로 ATGC..와 같은 형태로 읽어내는 방법은 없습니다. 그래서 적당히 우리가 읽어낼 수 있는 수준으로 쪼갭니다. 이 쪼갠 DNA를 박테리아에 집어넣어서 배양을 통해 늘린 후, 이걸 분석한 후에 연결하면 완성!

.
.
.

으로 끝나면 아마 이 글을 쓰지 않았겠죠. 다음과 같은 문제가 있습니다.
1. 자른 부분이 어딘지 모른다.
잘 잘라서 DNA를 읽어낸 것까지는 좋은데 이게 어디부터 어디까지인지는 모릅니다.
2. 겹치는 부분이 너무 많다.
자른 다음에 배양을 했기 때문에 읽어낸 부분들에서 겹치는 부분이 생기게 됩니다.

하지만, 다행히 우리는 이 어려운 퍼즐의 정답지는 아니지만 참고서는 가지고 있습니다. 예전에 분석한 다른 사람들의 DNA가 있죠(Reference Sequence). 인간이라는 종의 DNA는 거의 유사하기 때문에 다른 사람의 DNA 가져다가 겹치는 부분에 맞추면 됩니다. 물론 다른 사람의 DNA이기 때문에 완전히 딱 맞지는 않습니다.

이 부분에서 이 문제는 컴퓨터공학의 일로 넘어가게 됩니다.
Reference Sequence를 텍스트로, 잘라낸 DNA를 패턴으로 보면, 텍스트에서 패턴을 찾는 문제가 되죠. 하지만, 앞에서 적었듯이 완전히 일치하지 않기 때문에 오차를 허용하는 패턴매칭 문제가 됩니다.

오차로 볼수 있는건 다음과 같습니다.
1. DNA 문자 일부가 바뀜
2. DNA 문자 일부가 빠짐
3. DNA 문자 일부가 추가됨
4. DNA 문자 일부의 순서가 바뀜

허용하는 오차의 범위가 커질수록 계산량은 무지막지하게 커지기 때문에, 계산용 그래픽 카드를 달고 몇 시간씩 돌려도 70~80% 정도 밖에 DNA조각을 배치를 못합니다. 속도와 배치율을 높이기 위해서 아직도 연구가 되고 있는 분야입니다.