생물정보학 알고리듬 3/e

1장. DNA 복제는 유전체의 어디서부터 시작되는가?

__1,000마일의 여행
__복제 기점의 숨겨진 메시지
____DnaA 상자
____황금벌레의 숨겨진 메시지
____단어 세기
____빈번한 단어 문제
____Vibrio cholerae의 빈번한 단어
__더욱 놀라운 숨겨진 메시지
__숨겨진 메시지의 범람
____여러 유전체에서 숨겨진 메시지 찾기
____군집 찾기 문제
__DNA를 복제하는 가장 간단한 방법
__복제의 비대칭성
__정방향 및 역방향 반가닥의 독특한 통계
____숨어 있는 생물학적 현상 또는 통계적 우연?
____탈아민화
____비대칭 다이어그램
__다른 메시지보다 이해하기 어려운 일부 숨겨진 메시지
__대장균에서 DnaA 상자를 찾는 마지막 시도
__에필로그: ori 예측의 복잡성
__열린 문제
____박테리아 유전체의 다중 복제 기점
____고세균에서 복제 기점 찾기
____효모에서 복제 기점 찾기
____문자열에서 패턴 확률 계산
__충전소
____빈도 배열
____패턴과 숫자를 서로 변환하기
____정렬을 사용해 빈번한 단어 찾기
____군집 찾기 문제 해결
____미스매치를 포함한 자주 나오는 단어 문제 해결
____문자열 이웃 생성
____정렬로 미스매치를 포함한 빈번한 단어 찾기
__돌아가기
____Big - O 표기법
____문자열에서 패턴의 확률
____생물학에서 가장 아름다운 실험
____DNA 가닥의 방향성
____하노이 타워
____겹치는 단어 역설
__참고 문헌

2장. 분자 시계 역할을 하는 DNA 패턴은 무엇일까?

__우리는 시계 유전자를 갖고 있을까?
__생각보다 쉽지 않은 모티프 찾기
____저녁 요소 찾기
____모티프와 숨바꼭질
____모티프 검색: 무차별 대입 알고리듬
__모티프에 점수 매기기
____모티프에서 프로필 행렬과 컨센서스 문자열
____더 적절한 모티프 점수 계산 함수
____엔트로피와 모티프 로고
__모티프 찾기에서 중앙 문자열 찾기까지
____모티프 찾기 문제
____모티프 찾기 문제의 재구성
____중앙 문자열 문제
____모티프 찾기 문제를 다시 만든 이유
__탐욕 모티프 검색
____주사위를 굴리고자 프로필 행렬 사용하기
____탐욕 모티프 검색 분석
__모티프 검색과 올리버 크롬웰
____내일 해가 뜨지 않을 확률은 얼마인가?
____라플라스의 승계 법칙
____탐욕 모티프 검색의 발전
____무작위 모티프 검색
__주사위로 모티프 찾기
____무작위 모티프 검색이 작동하는 이유
__무작위 알고리듬은 어떻게 잘 작동하는가?
__깁스 샘플링
__깁스 샘플링의 작동
__에필로그: 결핵균은 어떻게 항생제를 피하려고 동면할까?
__충전소
____중앙 문자열 해결
__돌아가기
____유전자 발현
____DNA 어레이
____뷔퐁의 바늘
____모티프 찾기의 복잡성
____상대적 엔트로피
__참고 문헌

3장. 유전체는 어떻게 조립하는가?

__폭발하는 신문들
__문자열 재구축 문제
____유전체 조립은 당신 생각보다 더 어렵다
____문자열을 k-mer로부터 재구성하기
____반복 서열은 유전체 조립을 어렵게 한다
__겹침 그래프에서의 움직임과 같은 문자열 재구축
____문자열에서 그래프로
____유전체가 사라진다
____그래프 표현법 두 가지
____해밀턴 경로와 범용 문자열
__문자열 재구축을 위한 또 다른 그래프
____노드 접착 및 드 브루인 그래프
__드 브루인 그래프에서 움직이기
____오일러 경로
____드 브루인 그래프를 구축하는 또 다른 방법
____k-mer 구성으로부터 드 브루인 그래프 구축하기
____드 브루인 그래프 대 겹침 그래프
__쾨니히스버그의 7개의 다리
__오일러 정리
__오일러 정리에서부터 오일러 순환 경로를 찾는 알고리듬까지
____오일러 순환 경로 구축하기
____오일러 순환 경로에서 오일러 경로로
____범용 문자열 구축하기
__리드 쌍으로부터 유전체 조립하기
____리드에서 리드 쌍으로
____리드쌍을 가상의 긴 리드로 바꾸는 방법
____구성에서 쌍체 구성으로
____쌍을 이루는 드 브루인 그래프
____쌍을 이루는 드 브루인 그래프의 함정
__에필로그: 유전체 조립이 실제 시퀀싱 데이터를 마주하다
____리드들을 k-mer들로 쪼개기
____유전체를 컨티그들로 쪼개기
____오류가 많은 리드들을 조립하기
____드 브루인 그래프에서 에지의 다양성 추론하기
__충전소
____인접 행렬을 접착하는 효과
____모든 오일러 순환 경로 만들기
____쌍을 이루는 드 브루인 그래프의 경로를 따라서 문자열 구축하기
____그래프의 최대 비분기 경로
__돌아가기
____DNA 시퀀싱 기술의 짧은 역사
____인간 유전체의 반복 서열
____그래프
____이코시안 게임
____다루기 쉬운 문제와 다루기 어려운 문제
____오일러에서 해밀턴 그리고 드 브루인으로
____칼리닌그라드의 일곱 다리
____이중 가닥 DNA를 조립할 때의 함정
____BEST 정리
__참고 문헌

4장. 항생제의 서열은 어떻게 알아낼까?

__항생제의 발견
__박테리아는 어떻게 항생제를 만드는가?
____유전체가 펩티드를 암호화하는 방법
____바실루스 브레비스 유전체의 어떤 부분이 티로시딘을 암호화하는가?
____선형에서 고리형 펩티드로
__분자생물학 중심 원리 회피
__항생제를 작게 조각 내 서열 해독
____질량 분석법 소개
____고리형 펩티드 시퀀싱 문제
__고리형 펩티드 시퀀싱의 브루트 포스 알고리듬
__분기 한정법 알고리듬을 고리형 펩티드 시퀀싱에 적용
__골프를 만난 질량 분석법
____이론에서부터 실제 스펙트럼으로
____오류가 있는 스펙트럼에 고리형 펩티드 시퀀싱 적용
__20에서 100개 이상의 아미노산
__스펙트럼 컨볼루션으로 문제 해결
__에필로그: 가상의 스펙트럼에서 실제 스펙트럼으로
__열린 문제
____순환 도로와 유료 도로 문제
____영장류에서 고리형 펩티드 시퀀싱
__충전소
____펩티드의 이론 스펙트럼 생성
____CYCLOPEPTIDESEQUENCING은 얼마나 빠를까?
____펩티드 Leaderboard 자르기
__돌아가기
____가우스와 리센코주의
____코돈의 발견
____쿼럼 센싱
____분자 질량
____셀레노시스테인과 피롤리신
____유료 도로 문제의 의사 다항식 알고리듬
____분할 유전자
__참고 문헌

5장. DNA 서열들을 비교하려면 어떻게 해야 할까?

__비리보솜 코드 해독하기
____RNA 넥타이 클럽
____단백질 비교에서 비리보솜 코드까지
____종양 유전자와 성장 인자의 공통점은 무엇일까?
__서열 정렬에 대한 소개
____서열 정렬은 게임과 같다
____문자열 정렬과 최장 공통 하위문자열
__맨해튼 관광객 문제
____최적의 관광 코스는 무엇일까?
____임의의 방향성 그래프에서 관광하기
__서열 정렬은 맨해튼 관광객 문제가 위장하고 있는 것일 뿐이다
__동적 프로그래밍 소개: 변화 문제
____탐욕스럽게 거스름돈 받기
____재귀적으로 돈 거슬러 주기
____동적 프로그래밍을 사용한 거스름돈 계산
__다시 맨해튼 관광객 문제로
__맨해튼 문제에서 임의의 방향성 비순환 그래프로
____서열 정렬은 유사 - 맨해튼 그래프를 구축하는 것과 같다
____임의의 DAG에 동적 프로그래밍 적용하기
____위상학적 순서대로 나열하기
__정렬 그래프 역추적하기
__정렬 점수
____LCS 점수 모델의 문제는 뭘까?
____점수 행렬
__전역 정렬에서 지역 정렬까지
____전역 정렬
____전역 정렬의 한계
____정렬 그래프에서 공짜 택시 타기
__서열 정렬의 다양한 모습
____수정 거리
____적합 정렬
____겹침 정렬
__서열 정렬에서 삽입과 삭제에 대한 페널티를 주는 방법
____어파인 갭 페널티
____맨해튼을 3개의 층으로 구축하기
__공간 효율적인 서열 정렬
____선형적 메모리를 사용해 정렬 점수 계산하기
____중간 노드 문제
____놀랍도록 빠르고 메모리 효율적인 정렬 알고리듬
____중간 에지 문제
__에필로그: 다중 서열 정렬
____3차원 맨해튼 구축하기
____탐욕 다중 정렬 알고리듬
__돌아가기
____개똥벌레와 비리보솜 코드
____도시를 만들지 않고 LCS 찾기
____위상학적 나열 만들기
____PAM 점수 행렬
____분할 및 정복 알고리듬
____다중 정렬에 점수 매기기
__참고 문헌

6장. 인간 유전체에도 연약한 영역이 있을까?

__쥐와 남자
____사람과 쥐의 유전체는 얼마나 다를까?
____합성 블록
____반전
____재배열 핫스팟
__염색체 진화의 무작위 절단 모델
__반전을 통한 나열
__반전 나열을 위한 탐욕적 발견법
__절단점
____절단점이란 무엇인가?
____절단점 개수 세기
____절단점을 제거하는 반전 나열
__종양 유전체를 재배열하기
__단일 염색체에서 다중 염색체로
____전좌, 결합, 분열
____유전체에서 그래프로
____2 -절단
__절단점 그래프
__2-절단 거리 계산하기
__인간 유전체의 재배열 핫스팟
____무작위 절단 모델과 2-절단 거리 이론의 만남
____취약 절단 모델
__에필로그: 합성 블록 구축하기
____유전체 점 도표
____공유하고 있는 k - mer들 찾기
____공유 k - mer로부터 합성 블록 구축하기
____합성 블록을 그래프의 연결된 요소들로 생각하기
__미해결 문제: 재배열이 박테리아 진화의 비밀을 밝힐 수 있을까?
__충전소
____유전체에서 절단점 그래프 만들기
____2-절단 문제 해결하기
__돌아가기
____X 염색체의 유전자는 왜 잘 보존돼 있는 걸까?
____유전체 재배열의 발견
____지수 분포
____빌 게이츠와 데이비드 X. 코헨의 팬케이크 뒤집기
____반전을 사용해 선형 순열 나열하기
__참고 문헌

7장. 어떤 동물이 우리에게 SARS를 옮겼을까?

__가장 빠른 전염병
____메트로폴 호텔에서 생긴 문제
____SARS의 진화
__거리 행렬을 진화 트리로 바꾸기
____코로나 바이러스 유전체에서 거리 행렬 만들기
____진화 트리를 그래프로 나타내기
____거리 기반 계통 발생 구축
__거리 기반 계통 발생 구축을 위한 알고리듬을 향해
____이웃하고 있는 잎 탐색하기
____가지의 길이 계산하기
__가산적 계통 발생
____트리의 가지 다듬기
____가지 붙이기
____거리 기반 계통 발생을 구축하기 위한 알고리듬
____코로나 바이러스의 진화 트리 구축하기
__최소 제곱을 사용해 거리의 근사값에 기반한 계통 발생을 구축하는 방법
__초거리 진화 트리
__이웃-연결 알고리듬
____거리 행렬을 이웃 - 연결 행렬로 바꾸는 방법
____이웃-연결 알고리듬으로 코로나 바이러스 분석하기
____트리 구축에 있어서 거리 기반 접근 방법의 한계점
__특성-기반 트리 재구축
____특성표
____해부학적 특성에서 유전적 특성으로
____곤충의 날개는 얼마나 많은 진화에 의해 만들어졌을까?
__최소 단순성 문제
__최대 단순성 문제
__에필로그: 진화 트리로 범죄에 맞서다
__돌아가기
____HIV는 언제 유인원에서 인간으로 전파된 걸까?
____거리 행렬에 적합한 트리 찾기
____네 점 조건
____SARS를 옮긴 것은 박쥐일까?
____이웃-연결 알고리듬이 어떻게 이웃하는 잎을 찾는 것일까?
____이웃-연결 알고리듬에서 가지의 길이 계산하기
____자이언트 판다: 곰일까 라쿤일까?
____인간은 어디에서 왔을까?
__참고 문헌

8장. 효모는 어떻게 와인 제조사가 됐을까?

__와인 제조의 진화적 역사
____우린 언제부터 알코올에 중독돼 온 걸까?
____이중영양적 전환
__이중영양적 전환에 관련된 유전자 탐색하기
____다른 운명을 맞이하게 된 두 가지 진화 가설
____효모 유전자 중 어떤 것들이 이중영양적 전환을 이끌어 내는가?
__클러스터링 개론
____유전자 발현량 분석
____효모 유전자 클러스터링
__좋은 클러스터링 원칙
__클러스터링을 최적화 문제로 바라보기
__최장 최초 횡단
__k-Means 클러스터링
____제곱 왜곡 오차
____k-means 클러스터링과 무게 중심
__로이드 알고리듬
____중심적에서 클러스터로 그리고 다시 반대로
____로이드 알고리듬 초기화하기
____k-means++ 초기화
__이중영양적 전환에 관련된 유전자들을 클러스터링하기
__k-Means 클러스터링의 한계점
__동전 던지기에서 k-Means 클러스터링으로
____편향된 정도를 알 수 없는 동전 던지기
____계산 문제는 어디 있는가?
____동전 던지기에서 로이드 알고리듬으로
____클러스터링으로 돌아와서
__동전 던지기에서 소프트 결정 내리기
____기대값 극대화: E-step
____기대값 극대화: M-step
____기대값 극대화 알고리듬
__소프트 k-Means 클러스터링
____클러스터링에 기대값 극대화 알고리듬 적용하기
____중심점에서 소프트 클러스터로 가기
____소프트 클러스터에서 중심점으로 가기
__계층 클러스터링
____거리 기반 클러스터링에 대한 소개
____트리에서 클러스터 추론하기
____계층 클러스터링을 사용해 이중영양적 전환 분석하기
__에필로그: 암 샘플 클러스터링하기
__돌아가기
____전장 유전체 복제일까 아니면 연속적인 단일 유전자 복제일까?
____유전자 발현량 측정하기
____마이크로어레이
____무게 중심 이론의 증명
____발현량 행렬을 거리/유사도 행렬로 바꾸는 방법
____클러스터링과 손상된 클리크들
__참고 문헌

9장. 질병을 일으키는 돌연변이는 어떻게 찾는 걸까?

__오도 증후군의 원인은 무엇일까?
__다중 패턴 매칭에 대한 소개
__패턴들을 트라이로 만들기
____트라이 구축하기
____트라이를 다중 패턴 매칭 문제에 적용하기
__유전체 전처리로 대신하기
____접미사 트라이에 대한 소개
____패턴 매칭에 접미사 트라이 사용하기
__접미사 트리
__접미사 배열
____접미사 배열 구축하기
____접미사 배열을 사용한 패턴 매칭
__버로우즈-휠러 변형
____유전체 압축
__버로우즈-휠러 변환 구축하기
____반복 서열에서 런으로
____버로우즈-휠러 변환을 거꾸로 되돌리는 방법
____버로우즈 - 휠러 변환을 되돌리려는 첫 번째 시도
____처음 - 끝 특성
____처음 - 끝 특성을 사용해 버로우즈 - 휠러 변환 되돌리기
__버로우즈-휠러 변환을 사용한 패턴 매칭
____버로우즈 - 휠러를 사용한 첫 번째 패턴 매칭 시도
____패턴의 끝에서부터 뒤로 가기
____끝 -처음 연결
__버로우즈-휠러 패턴 매칭의 속도 높이기
____끝-처음 연결을 횟수 배열로 바꾸기
____버로우즈-휠러 행렬에서 첫 번째 열을 제거하는 방법
__일치하는 패턴들의 위치는 어디인가?
__과학 역사의 한 페이지를 장식한 버로우즈와 휠러
__에필로그: 미스매치를 허용하는 리드 매핑
____대략적인 패턴 매칭에서 정확한 패턴 매칭으로 나아가는 방법
____BLAST: 서열을 데이터베이스에 대조하기
____버로우즈- 휠러 변환을 사용한 대략적인 패턴 매칭
__충전소
____접미사 트리 구축하기
____최장 공유 하위 문자열 문제의 해결 방법
____부분 접미사 배열 구축하기
__돌아가기
____표준 인간 유전체
____인간 유전체에서의 재배열, 삽입, 삭제
____아호-코라식 알고리듬
____접미사 트리에서 접미사 배열 만들기
____접미사 배열에서 접미사 트리까지
____이진 탐색
__참고 문헌

10장. 생물학자들은 왜 아직까지 HIV 백신을 개발하지 못했는가?

__HIV 형질 분류하기
____HIV는 어떻게 인간의 면역 체계를 피하는 걸까?
____서열 정렬의 한계점
__야쿠자와 도박하기
__딜러의 소매에 숨어 있는 2개의 동전
__CG-아일랜드 찾기
__은닉 마코프 모델
____동전 던지기에서 은닉 마코프 모델까지
____HMM 도표
____카지노 문제를 수식으로 재구성하기
__복호화 문제
____비터비 그래프
____비터비 알고리듬
____비터비 알고리듬은 얼마나 빠를까?
__특정 HMM에서 가장 그럴듯한 결과물 찾기
__서열 정렬을 위한 프로필 HMM
____HMM과 서열 정렬은 어떤 관련이 있는가?
____프로필 HMM 구축하기
____프로필 HMM에서의 전이 확률과 방출 확률
__프로필 HMM을 사용해 단백질 분류하기
____프로필 HMM에 단백질 정렬하기
____유사 횟수의 귀환
____골치 아픈 침묵 상태 문제
____프로필 HMM은 실제로 유용한가?
__HMM의 매개변수 배워 보기
____감춰진 경로를 알고 있을 때 HMM 매개변수 추정하기
____비터비 학습
__매개변수 추정을 위한 소프트 결정
____소프트 복호화 문제
____순방향 - 역방향 알고리듬
__바움-웰치 학습
__HMM의 다양한 모습
__에필로그: 자연은 발명가가 아니라 수선가다
__돌아가기
____붉은 여왕 효과
____당화
____DNA 메틸화
____조건부 확률
__참고 문헌

11장. 티라노사우르스는 단지 큰 닭일까?

__고생물학과 계산의 만남
__이 샘플에는 어떤 단백질들이 있을까?
__이상적 스펙트럼 해석
__이상 스펙트럼에서 실제 스펙트럼으로
__펩티드 시퀀싱
____스펙트럼에 맞는 펩티드 점수
____접미사 펩티드는 어디에 있는가?
____펩티드 시퀀싱 알고리듬
__펩티드 식별
____펩티드 식별 문제
____미지의 티렉스 단백질체에서 펩티드 식별
____펩티드-스펙트럼 일치 찾기
__펩티드 식별과 무한 원숭이 정리
____거짓 발견 비율
____원숭이와 타자기
____펩티드 스펙트럼 일치의 통계적 의의
__스펙트럼 사전
__티렉스 펩티드: 오염 물질일까 아니면 고대 단백질의 보물 창고일까?
____헤모글로빈 수수께끼
____공룡 DNA 논란
__에필로그: 변형되지 않은 펩티드에서 변형된 펩티드로
____번역 후 변형
____변형 탐색을 정렬 문제로
____스펙트럼 정렬을 위한 맨해튼 그리드 생성
____스펙트럼 정렬 알고리듬
__돌아가기
____유전자 예측
____그래프에서 모든 경로 찾기
____반대칭 경로 문제
____스펙트럼을 스펙트럼 벡터로 변환
____무한 원숭이 정리
____스펙트럼 사전의 펩티드 확률 공간
____육상 공룡은 정말 새의 조상일까?
____가장 가능성 높은 펩티드 벡터 문제 해결하기
____스펙트럼을 스펙트럼 벡터로 변환하기 위한 매개변수 선택
__참고 문헌

부록. 의사 코드 소개

__의사 코드란?
__의사 코드의 기본
____if 조건문
____for 반복문
____while 반복문
____재귀 프로그래밍
____배열