A, C, G, T라는 네가지 염기들이 30억개가 줄지어 서있다. 수열,sequence.
30억자라면, 보통 크기의 책으로 만 권 정도 분량. (책 한 권이 300쪽, 쪽당 1000자 정도이면, 30만 자 정도로 계산)
이렇게 긴 염기서열이 사람마다 약간씩 다르고 일란성쌍둥이는 예외? 이 차이가 개인의 유전적 특징을 드러낸다.
염기서열의 어느 부분이 인간의 어떤 면에 영향을 주는지를 연구하기 위해 인간게놈프로젝트human_genome_project가 진행되었다.

비용과 시간이 너무 많이 든다.
이 때 shotgun sequencing기술이 쓰였다.
이 문제는 문자열 토막들이 주어졌을 때, 이 모두를 포함하는 가장 짧은 하나의 문자열을 찾는 문제가 된다. 이 문제를 다르게 보면 '지도 위의 모든 도시를 한 번씩만 방문하는 여정 찾기(hamiltonian_path, TSP) 문제와 같다. 어떻게?

각 문자열 토막을 지도 위의 도시라고 생각하고,
끝이 겹쳐서 손잡고 늘어놓을 수 있는 두 문자열은 지도에서 직통 도로로 연결된 두 도시라고 생각하자.
연결도로의 방향은 도착도시가 출발도시의 오른쪽에 연결될 수 있다는 뜻이다.

[1]