Wisdoms131 GenomeMapper 그래프 구조 본 내용은 내 동료 Jorg의 diploma thesis의 내용 중 일부를 번역한 것이다. 그래프 구조 이전에 설명했듯이, 지놈 서열은 블록들에 저장된다. 여러 개의 블록으로 분기해 확장되어나가는 서열들을 검색하기 위해서, 연결되어 있는 블록들에 대한 연결 정보를 가지고 있어야 한다. 이런 목적으로, 각 블록 테이블 요소는 양 인접한 블록들의 블록 수를 저장한다. 그런 까닭에, 이 구조는 그래프로 해석될 수 있다. 각 블록은 정점(vertex)으로, 그리고 그 연결은 에지(edge)로 해석된다. 지놈은 이제 염기 문자열들을 포함하고 있을 뿐 아니라, 서로 연결된 블록의 문자열들을 포함하고 있다(그림 2.3 (A)). 그림 2.3. 블록들을 포함하는 그래프 구조로 각 블록은 최대 256개의 염기를 저장한다.. 2012. 11. 29. GenomeMapper 색인 생성 본 문서는 내 동료 Jorg의 diploma thesis의 내용 중 일부를 번역한 것이다. 색인 구조 생성(mkindex) 이 프로그램은 각 지놈 혹은 조합된 지놈에 대해서 오직 한 번만 수행되어야 한다. 이것은 해시 색인을 생성하여 씨드의 발생과 위치의 빠른 룩업을 가능하게 하고, 참조 서열에 대해 계통([생물]strains)의 다른점들과 관련이 있는 모든 서열 정보를 포함하는 시퀀스 그래프를 생성한다. 입력으로 프로그램은 단지 FASTA 포맷으로 된 참조 서열 하나 혹은 다수의 다른 계통 서열들을 받을 수 있다. 각 계통들은 하나의 분리된 입력 파일 안에 있어야 한다. 이 프로그램은 모든 변이에 대해서 염색체, 서열의 위치, 그리고 계통적 다형성(삽입이 삭제와 SNP보다 더 선호된다)에 따라 오름차순.. 2012. 11. 29. GenomeMapper 개념 본 내용은 내 동료인 Jorg의 diploma thesis의 일부를 번역한 것이다. 개념 GenomeMapper는 프로그래밍 언어 C를 이용하여 구현되었다. 포인터 연산과 수동 메모리 관리가 이점이며, 다른 프로그래밍 언어에 비해서 실행 시간을 줄여준다. Read란, 예를 들어 fasta 포맷으로 된 염기 서열 데이터 파일을 보면 시퀀싱 머신에서 한 싸이클 당 읽어들인 염기 서열들이 한 줄마다 있게 된다. 즉 이 한 줄에 담긴 염기 서열을 read 라고 부른다. GenomeMapper는 약간씩 다른 지놈들에 있는 수백만의 리드들의 위치를 검출하기 위해 개발되었다. 리드들은 알려지지 않은 지놈으로부터 왔기 때문에, 대부분의 리드들은 원래의 염기 서열에 있어야 하는 영역을 찾지 못할 것이다. 그런 까닭에, .. 2012. 11. 29. Shift-And 문자열 검색 본 문서는 Algorithms on Strings Trees and Sequences의 내용을 일부 번역한 것이다. Shift-And 문자열 검색 R. Baeza-Yates와 G. Gonnet 씨는 상대적으로 짧은 패턴(예를 들어, 전형적인 영어 단어의 길이)의 완전 일치 검색을 매우 효율적으로 해결하는 비트 기반의 방법을 고안하였다. 그들은 이 방법을 Shift-Or 방식이라고 불렀지만, 이것은 Shift-And라고 부르는 것이 더 적절할 것 같다. 패턴 P가 n의 길이를 가지고 있고, 참조 문자열 T가 m의 길이를 가지고 있다고 하자. 정의 M은 (n)X(m+1)의 행렬이고, 행 순서 i는 1부터 n의 길이를 가지고, 열 순서 j는 1부터 m까지라고 하자. 한 요소 M(i, j)는 P의 첫 i번째 문.. 2012. 11. 28. 이전 1 ··· 28 29 30 31 32 33 다음
