생체고분자 서열의 모티프 발굴을 위한 확률 모델
Probabilistic Models for Motif Discovery in Biopolymer Sequences
- 주제(키워드) 모티프발굴 , 기계학습 , 확률그래프모델 , 생물정보학
- 발행기관 포항공과대학교 대학원
- 지도교수 최승진
- 발행년도 2010
- 학위수여년월 2010. 2
- 학위명 박사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 세부전공 기계학습
- 원문페이지 121
- 실제URI http://www.dcollection.net/handler/postech/000000538676
- 본문언어 한국어
- 저작권 포항공과대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
본 논문에서는 생체고분자 서열의 효과적인 모티프 발굴과 서열 분류를 위한 확률 모델을 제안한다. 서열 모티프는 DNA, RNA, 그리고 단백질과 같은 생체고분자 서열내의 특정 부위에 나타나는 서열 패턴으로 생물학적으로 중요한 기능을 가진다. 그러나 서열 모티프는 그 특성상 길이가 짧고 패턴상의 오류를 허용하므로 이를 정확히 찾는 것은 어려운 문제이다. 이러한 특성으로 게놈 수준에서 모티프를 예측할 때 큰 거짓 양성 및 거짓 음성율을 보인다. 또한 생물학 실험을 통하여 서열 모티프를 찾기 위한 서열 집합을 구성하므로 실험에 따른 불확실성을 고려하는 것도 어려운 문제이다. 이와 같은 문제점을 해결하기 위하여 본 논문에서는 확률 그래프 모델에 기반한 방법을 제안한다. 이를 통하여 모델의 통계적 구조를 시각화 함으로써 추론 및 학습 알고리즘을 보다 쉽게 개발할 수 있다. 본 논문은 먼저 식물 단백질의 엽록체 이동에 중요한 서열 모티프를 예측하는 문제를 고려한다. 베이지안 결정 이론 모델을 이용하여 음성 서열에 비해 양성 서열의 특정 그룹에 많이 나타나는 서열 부분을 찾는 교사 학습 알고리즘을 제안한다. 서열 정보를 교사 모델의 입력 특징 벡터로 사용하기 위하여 position specific local gapped alignment로 명명한 새로운 전역 정열 알고리즘을 개발한다. 서열 모티프가 실험으로 검증된 일곱 개의 엽록체 통과 펩타이드를 이용하여 제안한 교사 모델이 패턴 변이성이 큰 단백질 서열 모티프를 예측할 수 있음을 보인다. 또한 서열에서 추출한 특징 벡터를 SVM 분류기에 적용함으로써 엽록체 통과 펩타이드를 예측하는 분류 문제의 정확도를 향상시킬 수 있음을 보인다. 단백질의 서열 모티프와 함께 본 논문은 DNA 염기 서열의 모티프를 찾기 위한 다양한 모델을 제안한다. 먼저 양성 및 음성 서열로 이루어진 두 서열 집합을 고려하여 두 집합을 구별하는 서열 패턴을 찾는 구별 모티프 발굴을 위한 확률 모델을 제안한다. 생성 및 구별 모델의 장점을 취한 하이브리드 모델을 이용하여 부분적으로 양성/음성 클래스가 표지된 서열 데이터로부터 모델을 효과적으로 학습한다. 제안한 모델의 성능은 순수한 생성 및 구별 모델의 중간 지점에서 가장 좋음을 보이며 또한 반교사 학습은 클래스가 표지된 서열의 수가 작을 때 효과적임을 보인다. 지금까지 개발된 모티프 발굴을 위한 모델은 하나 또는 두 개의 서열 집합을 고려한다. 이를 확장하여 서열 집합의 수가 둘 이상일 때 서열 집합을 여러 개의 군집으로 분류하고 동시에 분류된 군집을 설명하는 서열 모티프를 발굴하는 유한 혼합 모델을 제안한다. 서열 집합의 군집화는 서열의 시그널과 노이즈 비율을 향상시키고 여러 개의 서열 모티프를 동시에 찾을 수 있음을 실험을 통하여 보인다. 또한 여러 개의 서열 집합을 구성하는 방법에 따라 다양한 모티프 발굴 문제에 적용 가능함을 보인다. 마지막으로 본 논문은 다양한 세포 반응에서 중요한 전사 인자인 STAT3의 결합 부위를 찾기 위한 방법을 제안한다. 감도를 향상시키고 거짓 양성율을 최소화하기 위하여 모티프에 기반한 비교 알고리즘인 STAT-Finder를 설명한다. 이를 STAT3의 결합 부위를 가진다고 알려진 유전자로 이루어진 데이터를 이용하여 STAT3와 관련된 다양한 모티프 모델을 결합한 것이 성능 향상의 가장 중요한 요인임을 보인다. 또한 STAT-Finder를 이용하여 새로운 STAT3 목표 유전자를 예측하고 이를 실험으로 검증한다.
more초록/요약
We develop probabilistic models which allow effective motif discovery and sequence classification in biopolymer sequences. Discovering sequence motifs is a difficult problem in practice because they are usually short and degenerate. Such difficulties lead to high false positive and negative rates in prediction especially on a genome-scale. It is also challenging to determine which sequences should be used to find sequence motifs due to uncertainties in compiling sequences from biological experiments. In this thesis, we present several models which take a probabilistic approach based on graphical models to surmount these difficulties. This approach allows us to visualize the statistical structure of the models, and to develop their associated inference and learning algorithms with ease. We start by considering the problem of predicting protein sequence motifs important for targeting to chloroplasts. Using Bayesian decision theoretic models, we provide a supervised approach to find a set of sequence segments that occur more frequently in a subgroup of positive sequences compared with the negative sequences. A novel global alignment algorithm, called position specific local gapped alignment, is employed to extract numerical features from a sequence, where the features are taken as an input vector in our supervised model. Using seven chloroplast transit peptides with experimentally verified sequence motifs, we demonstrate that the utility of the supervised model of discovering motifs with high sequence variability. Additionally, we show that an SVM-based classifier, relying on the extracted numerical features, leads to significant improvements in classification accuracy to predict chloroplast transit peptides. In the second half of this thesis, we develop methods for discovering sequence motifs in DNA sequences. We first provide a probabilistic model for discriminative motif discovery in which two sets (positive and negative sets) of sequences are considered to search only for patterns that differentiate the two sets. By building a hybrid generative/discriminative model, we better exploit partially labeled sequences. We demonstrate that the best performance is obtained between the purely-generative and the purely-discriminative, and the semi-supervised learning improves the performance when labeled sequences are limited. Turning to multiple sets of sequences, we propose a finite mixture model which simultaneously clusters multiple sets of sequences and finds motifs that relate the clusters. We show that clustering sets of sequences yields clusters of coherent motifs, improving signal-to-noise ratio of input target sequences and enabling us to identify multiple motifs. We then demonstrate that our model can handle various motif discovery problems, depending on how to construct multiple sets of sequences. Finally, we develop methods for searching binding sites of STAT3 which is an important transcription factor in diverse cellular responses. We describe our motif-based comparative algorithm, STAT-Finder, which is designed to predict functional binding sites of STAT3 with improved sensitivity and to minimize false positive prediction rates. Applying STAT-Finder into two reference sets containing promoter sequences of known STAT3 target genes, we show that simply combining similar position weight matrices related to STAT3 improves the performance of finding known binding sites of STAT3. We also demonstrate that our approach is able to detect novel binding sites of STAT3 which are confirmed through in vivo binding assays.
more목차
1 Introduction 1
1.1 Protein Targeting to Chloroplasts 2
1.2 Transcriptional Regulatory Networks 3
1.2.1 Pattern Detection 5
1.2.2 Pattern Matching 8
1.3 Thesis Organization and Overview of Methods and Contributions 8
1.3.1 Chapter 2: Background 9
1.3.2 Chapter 3: Supervised Learning for Discriminative Motif Discovery 9
1.3.3 Chapter 4: Semi-Supervised Learning for Discriminative Motif Discovery 10
1.3.4 Chapter 5: Unsupervised Learning for Motif Discovery 10
1.3.5 Chapter 6: Prediction of STAT3 TFBSs based on Multiple Motif Models 11
1.3.6 Chapter 7: Conclusions 12
2 Background 13
2.1 Graphical Models 13
2.1.1 Directed Graphical Models 14
2.2 Markov Chain Monte Carlo 17
2.2.1 Markov Chains 18
2.2.2 The Metropolis-Hastings Algorithm 20
2.2.3 Gibbs Sampling 21
3 Supervised Learning for Discriminative Motif Discovery 23
3.1 Position Specific Local Gapped Alignment 24
3.2 Bayesian Decision Theoretic Models for Discriminative Motif Discovery 26
3.3 Motif-Driven Features for Classification 27
3.4 Results 29
3.4.1 Data Sets and Evaluation Criteria 29
3.4.2 Prediction of Sequence Motifs in Plastid Transit Peptides 31
3.4.3 Prediction of Plastid Transit Peptides 33
3.5 Discussion 34
4 Semi-Supervised Learning for Discriminative Motif Discovery 36
4.1 Probabilistic Models for Motif Discovery 38
4.1.1 Notation 38
4.1.2 Generative Model 39
4.1.3 Learning: EM and Discriminative Training 42
4.2 Hybrid Models 43
4.2.1 Hybrid Generative/Discriminative Model 44
4.2.2 Learning 46
4.2.3 Extension to Double Stranded DNA Sequences 48
4.3 Related Work 48
4.4 Results 52
4.4.1 Data Sets and Evaluation Criteria 53
4.4.2 Comparison of alpha 53
4.4.3 Effect of using Unlabeled Sequences 54
4.4.4 Comparison with Other Methods 55
4.5 Discussion 56
5 Unsupervised Learning for Motif Discovery 57
5.1 Problem formulation 58
5.2 Mixture model for motif discovery 59
5.3 Inference by Gibbs sampling 62
5.4 Results 65
5.4.1 Data Sets and Evaluation Criteria 65
5.4.2 Filtering Out Noisy Sequences 66
5.4.3 Detecting Evolutionary Conserved Motifs 68
5.4.4 Clustering DNA Sequences based on Motifs 70
5.5 Discussion 70
6 Prediction of STAT3 TFBSs based on Multiple Motif Models 72
6.1 Overview of STAT-Finder 73
6.2 Prediction of putative STAT TFBSs: STAT-Scanner 74
6.3 Prediction of conserved STAT TFBSs: STAT-Finder 76
6.3.1 Comparative Motif-based Alignment 77
6.3.2 Generative Model for Multiple Motifs 78
6.4 Results 81
6.4.1 Data Sets 81
6.4.2 Validation of TFBS-Scanner 82
6.4.3 Validation of TFBS-Finder 84
6.4.4 Identication of novel STAT3 target genes 85
6.5 Discussion 89
7 Conclusions 93
7.1 Summary of Methods and Contributions 93
7.2 Suggestions for Future Research 95
A Appendix 97
A.1 Parameter Estimation for Semi-Supervised Learning for Discriminative Motif Discovery 97
A.1.1 Computing @L@^Dkl 99
A.1.2 Computing @L@^Gkl 100
A.1.3 Computing @L@^ 101
한글요약문 102
Bibliography 104