과학 기술의 발달로 인류는 유전체의 정보를 염기서열 단위까지 좁혀서 생명체의 비밀을 밝혀내고 있다. 생명체에서 나오고 있는 데이터는 인류 역사상 가장 큰 규모의 데이터 크기를 자랑하고 있으며, 점점 더 커지고 다양해지는 데이터에 걸맞춰 좀 더 향상된 성능의 분석 소프트웨어를 요구하고 있다. 생물정보학 알고리듬은 이런 고성능 소프트웨어의 기반이 되는 지식이다. 이 책은 자칫 어려워 보일 수 있는 알고리듬이 어떻게 생물학적 데이터에 적용되는지 우리에게 친숙한 이야기로 풀어서 설명한다. 생물정보학 알고리듬에 익숙하지 않은 독자들과 깊이 있는 학습을 원하는 모든 분들에게 추천한다.
카네기 멜론 대학교 컴퓨터 공학부 컴퓨터 생물학과의 교육부장으로 온라인 교육의 미래와 오프라인 교육을 개선할 수 있는 방법에 관심이 많다. 2014년 캘리포니아 대학교 샌디에이고에서 수학 박사 학위를 받았으며 이후 컴퓨터 과학 및 공학부에서 박사후 연구원으로 재직했다. 2012년 니콜라이 뱌히(Nikolay Vyahhi)와 로잘린드(Rosalind)를 공동 설립했다. 은퇴한 테니스 선수로 언젠가 프로 골프 선수가 되는 꿈을 꾸고 있다.
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 반복문____재귀 프로그래밍____배열
