생물정보학 알고리듬 (2022년도 대한민국학술원 선정 교육부 우수학술도서 | 3 판)

필립 콤포

Phillip Compeau
카네기 멜론 대학교 컴퓨터 공학부 컴퓨터 생물학과의 교육부장으로 온라인 교육의 미래와 오프라인 교육을 개선할 수 있는 방법에 관심이 많다. 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장. 인간 유전체에도 연약한 영역이 있을까?
__쥐와 남자
____사람과 쥐의 유전체는 얼마나 다를까?
____합성 블록
____반전
____재배열 핫스팟
__염색체 진화의 무작위 절단 모델
__반전을 통한 나열
__반전 나열을 위한 탐욕적 발견법
__절단점
____절단점이란 무엇인가?
____절단점 개수 세기
____절단점을 제거하는 반전 나열
__종양 유전체를 재배열하기