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

비용과 시간이 너무 많이 든다.
이 때 [[shotgun_sequencing]] WtEn:shotgun_sequencing ? WpSp:shotgun_sequencing ? WpEn:shotgun_sequencing ? Google:shotgun+sequencing { https://everything2.com/title/shotgun+sequencing } 기술이 쓰였다.
이 문제는 [[문자열,string]] 토막들이 주어졌을 때, 이 모두를 포함하는 가장 짧은 하나의 문자열을 찾는 문제가 된다. 이 문제를 다르게 보면 '지도 위의 모든 도시를 한 번씩만 방문하는 여정 찾기([[Hamiltonian_path]], ''TSP'') 문제와 같다. 어떻게?

각 문자열 토막을 지도 위의 도시라고 생각하고,
끝이 겹쳐서 손잡고 늘어놓을 수 있는 두 문자열은 지도에서 직통 도로로 연결된 두 도시라고 생각하자. 
연결도로의 방향은 도착도시가 출발도시의 오른쪽에 연결될 수 있다는 뜻이다.
https://i.imgur.com/PsGp435l.jpg
[* SNU이광근 컴여세 p222-]