Dự Đoán Cấu Trúc Gen Trong Bộ Gen Eukaryote

Nghiên cứu luận án tiến sĩ về dự đoán cấu trúc gen trong bộ gen eukaryote, khám phá các phương pháp và ứng dụng trong sinh học phân tử.

• Tác giả: Jonathan Edward Allen
• Người hướng dẫn: Steven L. Salzberg
• Trường học: The Johns Hopkins University
• Chuyên ngành: Doctor of Philosophy
• Đề tài: Dự Đoán Cấu Trúc Gen Trong Bộ Gen Eukaryote
• Loại tài liệu: dissertation
• Năm xuất bản: 2006
• Địa điểm: Baltimore

Mục lục chi tiết

• Abstract
• Acknowledgements
• 1. CHƯƠNG 1: Introduction
• 1.1. Computational Framework for Gene Prediction
• 1.1.1. Generalized Hidden Markov Models
• 1.1.2. Statistical Sequence Modeling
• 1.1.3. Integration of Extrinsic Evidence
• 1.1.4. Using Multiple Genomic Sequences
• 2. CHƯƠNG 2: Linear Combiner
• 3. CHƯƠNG 3: Statistical Combiner
• 3.1. Gene Structure Prediction with a GHMM
• 3.2. Representing Gene Structure Evidence
• 3.3. Conditioned on Input Evidence
• 4. CHƯƠNG 4: Prediction of Alternatively Spliced Exons
• 4.1. Explicit Classification of Cassette Exons
• 4.2. Biological Model of Splicing
• 4.3. Implicit Prediction of Alternative Splicing
• 4.4. Computational Model for Alternative Splicing
• 4.5. A Generalized Hidden Markov Model
• 4.6. A Phylogenetic Generalized Hidden Markov Model
• 4.7. Recovering Exon Structure
• 5. CHƯƠNG 5: Automated Gene Structure Annotation
• 5.1. TIGR Annotation Pipeline
• 5.2. Gene Structure Annotation Applications
• 5.3. Gene Structure Comparison
• 5.4. Testing on the ENCODE Regions
• 5.5. Evaluation of Evidence Tracks
• 6. CHƯƠNG 6: Alternative Exon Prediction Performance
• 6.1. Sequence Conservation Patterns
• 7. CHƯƠNG 7: Conclusion
• Bibliography
• Vita

Tóm tắt

I. Tổng Quan Dự Đoán Cấu Trúc Gen Eukaryote Khái Niệm Tầm Quan Trọng

Dự đoán cấu trúc gen trong bộ gen eukaryote là một lĩnh vực quan trọng của tin sinh học và gen học. Nó liên quan đến việc xác định vị trí và cấu trúc của các gen trong bộ gen eukaryote, bao gồm các exon, intron, vùng promoter, và vùng mã hóa. Quá trình này rất phức tạp do sự hiện diện của intron và các yếu tố điều hòa phức tạp. Dự đoán gen chính xác là nền tảng cho nhiều nghiên cứu sinh học, từ hiểu chức năng gen đến phát triển các liệu pháp điều trị bệnh. Các phương pháp dự đoán gen sử dụng nhiều nguồn thông tin, bao gồm trình tự DNA, dữ liệu biểu hiện gen, và thông tin về các gen tương đồng từ các loài khác. Theo Allen (2006), việc tích hợp các nguồn thông tin khác nhau là chìa khóa để cải thiện độ chính xác của dự đoán gen.

1.1. Vai trò của dự đoán gen trong nghiên cứu bộ gen eukaryote

Dự đoán gen đóng vai trò then chốt trong việc giải mã bộ gen eukaryote. Nó cung cấp thông tin cơ bản về số lượng gen, vị trí của chúng, và cấu trúc của chúng. Thông tin này rất quan trọng cho việc nghiên cứu chức năng gen, gene ontology, pathway analysis, và gene regulation. Việc xác định chính xác các gen cũng là bước đầu tiên để hiểu về sự khác biệt di truyền giữa các cá thể và quần thể, cũng như để phát triển các công cụ chẩn đoán và điều trị bệnh. Các công cụ bioinformatics tools và genomic databases hỗ trợ đắc lực cho quá trình này.

1.2. Các thành phần chính của cấu trúc gen eukaryote cần dự đoán

Cấu trúc gen eukaryote bao gồm nhiều thành phần quan trọng cần được dự đoán chính xác. Các thành phần này bao gồm exon (vùng mã hóa), intron (vùng không mã hóa), vùng promoter (điều hòa biểu hiện gen), và các tín hiệu splicing. Việc xác định chính xác vị trí và ranh giới của các thành phần này là rất quan trọng để hiểu về cơ chế biểu hiện gen và chức năng của protein. Các thuật toán dự đoán gen thường sử dụng các mô hình thống kê và machine learning để nhận diện các đặc điểm đặc trưng của các thành phần này.

II. Thách Thức Trong Dự Đoán Gen Độ Chính Xác Tính Toàn Diện

Dự đoán cấu trúc gen trong bộ gen eukaryote đối mặt với nhiều thách thức đáng kể. Sự phức tạp của bộ gen eukaryote, bao gồm sự hiện diện của intron lớn và số lượng lớn các yếu tố điều hòa, làm cho việc dự đoán gen trở nên khó khăn. Độ chính xác của các phương pháp dự đoán gen hiện tại vẫn còn hạn chế, đặc biệt đối với các gen có cấu trúc phức tạp hoặc biểu hiện thấp. Một thách thức khác là việc tích hợp các nguồn thông tin khác nhau một cách hiệu quả. Theo Allen (2006), việc cải thiện gene prediction accuracy, gene prediction sensitivity, và gene prediction specificity là những mục tiêu quan trọng trong lĩnh vực này.

2.1. Các yếu tố ảnh hưởng đến độ chính xác của dự đoán gen

Nhiều yếu tố ảnh hưởng đến độ chính xác của dự đoán gen. Các yếu tố này bao gồm chất lượng của trình tự DNA, sự phức tạp của cấu trúc gen, sự đa dạng của các yếu tố điều hòa, và sự sẵn có của dữ liệu biểu hiện gen. Các phương pháp dự đoán gen khác nhau có độ nhạy và độ đặc hiệu khác nhau, và việc lựa chọn phương pháp phù hợp là rất quan trọng. Ngoài ra, việc sử dụng các genomic databases và bioinformatics tools có thể giúp cải thiện độ chính xác của dự đoán gen.

2.2. Vấn đề tích hợp dữ liệu từ nhiều nguồn khác nhau

Việc tích hợp dữ liệu từ nhiều nguồn khác nhau là một thách thức lớn trong dự đoán gen. Các nguồn dữ liệu này bao gồm trình tự DNA, dữ liệu biểu hiện gen (transcriptomics), dữ liệu protein (proteomics), và thông tin về các gen tương đồng từ các loài khác (comparative genomics). Việc tích hợp các nguồn dữ liệu này một cách hiệu quả đòi hỏi các phương pháp thống kê và machine learning phức tạp. Các phương pháp tích hợp dữ liệu cũng cần phải xử lý các vấn đề như sai lệch dữ liệu, nhiễu, và sự không tương thích giữa các nguồn dữ liệu.

III. Phương Pháp Ab Initio Dự Đoán Gen Dựa Trên Trình Tự DNA

Phương pháp ab initio trong dự đoán gen dựa trên việc phân tích trực tiếp trình tự DNA để xác định các đặc điểm đặc trưng của gen, như vùng promoter, các vị trí splicing, và các codon bắt đầu và kết thúc. Các phương pháp này sử dụng các mô hình thống kê và thuật toán dự đoán gen để nhận diện các đặc điểm này. Ab initio gene prediction không yêu cầu thông tin từ các nguồn bên ngoài, nhưng độ chính xác của chúng thường thấp hơn so với các phương pháp sử dụng thông tin bổ sung. Theo Allen (2006), các phương pháp ab initio thường được sử dụng như một bước ban đầu trong quá trình dự đoán gen.

3.1. Sử dụng Hidden Markov Model HMM trong dự đoán gen

Hidden Markov Model (HMM) là một công cụ mạnh mẽ được sử dụng rộng rãi trong dự đoán gen ab initio. HMM mô hình hóa cấu trúc gen như một chuỗi các trạng thái ẩn, mỗi trạng thái tương ứng với một thành phần của gen (ví dụ: exon, intron, vùng promoter). Các tham số của HMM được ước tính từ dữ liệu huấn luyện, và sau đó HMM được sử dụng để dự đoán cấu trúc gen của các trình tự DNA mới. Các biến thể của HMM, như Generalized Hidden Markov Model (GHMM), cũng được sử dụng để cải thiện độ chính xác của dự đoán gen.

3.2. Ưu điểm và hạn chế của phương pháp ab initio

Ưu điểm chính của phương pháp ab initio là chúng không yêu cầu thông tin từ các nguồn bên ngoài, điều này làm cho chúng hữu ích cho việc dự đoán gen trong các bộ gen eukaryote mới được giải trình tự. Tuy nhiên, hạn chế chính của chúng là độ chính xác thường thấp hơn so với các phương pháp sử dụng thông tin bổ sung. Điều này là do các phương pháp ab initio chỉ dựa trên thông tin trình tự DNA, và chúng có thể gặp khó khăn trong việc phân biệt giữa các gen thực và các trình tự tương tự nhưng không mã hóa.

IV. Evidence Based Prediction Tích Hợp Dữ Liệu Biểu Hiện Gen Protein

Phương pháp evidence-based gene prediction sử dụng thông tin từ các nguồn bên ngoài, như dữ liệu biểu hiện gen (transcriptomics) và dữ liệu protein (proteomics), để cải thiện độ chính xác của dự đoán gen. Các phương pháp này tích hợp thông tin từ các thí nghiệm thực tế để xác định vị trí và cấu trúc của các gen. Dữ liệu RNA-Seq, EST, và protein sequence alignment thường được sử dụng làm bằng chứng để hỗ trợ dự đoán gen. Theo Allen (2006), việc tích hợp các nguồn thông tin khác nhau là chìa khóa để cải thiện độ chính xác của dự đoán gen.

4.1. Sử dụng dữ liệu RNA Seq và EST để xác định vị trí exon

Dữ liệu RNA-Seq và EST cung cấp thông tin trực tiếp về các vùng của bộ gen eukaryote được phiên mã thành RNA. Thông tin này có thể được sử dụng để xác định vị trí của các exon và các vị trí splicing. Các phương pháp evidence-based gene prediction thường sử dụng các thuật toán alignment để ánh xạ các trình tự RNA-Seq và EST lên bộ gen eukaryote, và sau đó sử dụng thông tin này để xây dựng các mô hình gen.

4.2. Tích hợp thông tin protein sequence alignment vào dự đoán gen

Thông tin protein sequence alignment cũng có thể được sử dụng để cải thiện độ chính xác của dự đoán gen. Các phương pháp evidence-based gene prediction thường sử dụng các thuật toán alignment để so sánh các trình tự protein đã biết với bộ gen eukaryote, và sau đó sử dụng thông tin này để xác định vị trí của các gen mã hóa protein. Thông tin protein sequence alignment đặc biệt hữu ích cho việc dự đoán các gen có cấu trúc phức tạp hoặc biểu hiện thấp.

V. Comparative Genomics So Sánh Bộ Gen Để Dự Đoán Cấu Trúc Gen

Comparative genomics là một phương pháp dự đoán gen dựa trên việc so sánh bộ gen eukaryote của các loài khác nhau để xác định các vùng bảo tồn. Các vùng bảo tồn thường tương ứng với các gen hoặc các yếu tố điều hòa quan trọng. Các phương pháp comparative genomics sử dụng các thuật toán alignment để so sánh bộ gen eukaryote của các loài khác nhau, và sau đó sử dụng thông tin này để dự đoán cấu trúc gen. Theo Allen (2006), comparative genomics có thể giúp cải thiện độ chính xác của dự đoán gen, đặc biệt đối với các gen có cấu trúc phức tạp hoặc biểu hiện thấp.

5.1. Xác định các vùng bảo tồn giữa các loài khác nhau

Việc xác định các vùng bảo tồn giữa các loài khác nhau là một bước quan trọng trong comparative genomics. Các vùng bảo tồn thường tương ứng với các gen hoặc các yếu tố điều hòa quan trọng. Các thuật toán alignment được sử dụng để so sánh bộ gen eukaryote của các loài khác nhau, và sau đó các vùng bảo tồn được xác định dựa trên mức độ tương đồng trình tự.

5.2. Sử dụng thông tin ortholog để cải thiện độ chính xác dự đoán

Thông tin về các ortholog (các gen tương đồng giữa các loài khác nhau) có thể được sử dụng để cải thiện độ chính xác của dự đoán gen. Nếu một gen đã được xác định trong một loài, thì có khả năng cao là gen ortholog cũng tồn tại trong các loài khác. Thông tin này có thể được sử dụng để hướng dẫn quá trình dự đoán gen và cải thiện độ chính xác của kết quả.

VI. Ứng Dụng Tương Lai Dự Đoán Gen Trong Nghiên Cứu Y Học

Dự đoán cấu trúc gen trong bộ gen eukaryote có nhiều ứng dụng quan trọng trong nghiên cứu và y học. Nó được sử dụng để hiểu chức năng gen, phát triển các liệu pháp điều trị bệnh, và nghiên cứu sự tiến hóa của bộ gen eukaryote. Trong tương lai, các phương pháp dự đoán gen sẽ tiếp tục được cải thiện nhờ sự phát triển của các công nghệ giải trình tự mới và các thuật toán machine learning tiên tiến. Theo Allen (2006), việc tích hợp các nguồn thông tin khác nhau một cách hiệu quả sẽ là chìa khóa để cải thiện độ chính xác của dự đoán gen trong tương lai.

6.1. Ứng dụng dự đoán gen trong nghiên cứu chức năng gen

Dự đoán gen là một bước quan trọng trong việc nghiên cứu chức năng gen. Việc xác định vị trí và cấu trúc của các gen cho phép các nhà khoa học nghiên cứu cơ chế biểu hiện gen, chức năng của protein, và vai trò của gen trong các quá trình sinh học khác nhau. Thông tin này có thể được sử dụng để hiểu về sự phát triển, sinh lý, và bệnh tật.

6.2. Triển vọng phát triển của các thuật toán dự đoán gen trong tương lai

Trong tương lai, các thuật toán dự đoán gen sẽ tiếp tục được cải thiện nhờ sự phát triển của các công nghệ giải trình tự mới và các thuật toán machine learning tiên tiến. Các phương pháp deep learning đang được sử dụng ngày càng nhiều trong dự đoán gen, và chúng hứa hẹn sẽ cải thiện đáng kể độ chính xác của kết quả. Ngoài ra, việc tích hợp các nguồn thông tin khác nhau một cách hiệu quả sẽ là chìa khóa để cải thiện độ chính xác của dự đoán gen trong tương lai.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ "Predicting Gene Structure in Eukaryotic Genomes" (Dự đoán cấu trúc gen trong hệ gen sinh vật nhân thực) do Jonathan Edward Allen thực hiện tại Đại học Johns Hopkins (The Johns Hopkins University), Baltimore, Maryland vào tháng 9 năm 2006, dưới sự hướng dẫn của Giáo sư Steven L. Salzberg và Giáo sư Jason M. Eisner. Luận án thuộc chuyên ngành Tin sinh học và Khoa học máy tính ứng dụng trong hệ gen học (Bioinformatics / Computational Biology).

Tính cấp thiết và khoảng trống nghiên cứu

Việc xác định toàn bộ tập hợp protein của sinh vật nhân thực là bước cơ bản để tìm hiểu cơ chế tiến hóa và chức năng tế bào. Tuy nhiên, do đặc điểm sinh lý phức tạp của tế bào nhân thực, việc quan sát trực tiếp protein và gen nguồn trong phòng thí nghiệm gặp nhiều rào cản kỹ thuật và chi phí. Trình tự ADN cung cấp bộ dữ liệu thô chứa mã chỉ dẫn tạo ra protein, do đó các hệ thống dự đoán gen bằng tính toán đóng vai trò then chốt trong việc tổng hợp danh mục protein phỏng đoán cho các hệ gen đã được giải trình tự.

Khoảng trống nghiên cứu được tác giả xác định gồm hai vấn đề chính:

1. Độ chính xác của các chương trình dự đoán đơn lẻ (ab initio hoặc dựa trên tương đồng) còn nhiều hạn chế và có sự bất đồng lớn giữa các kết quả đầu ra; việc tích hợp nhiều nguồn bằng chứng ngoại sinh dị thể (heterogeneous extrinsic evidence) cùng các chương trình dự đoán gen độc lập vào một mô hình suy luận thống nhất chưa đạt được hiệu quả tối ưu mà không làm bùng nổ số lượng tham số.
2. Việc mô hình hóa cấu trúc ghép nối thay thế (alternative splicing) để nhận diện các đồng dạng (isoforms) protein chồng lấn nhau trong cùng một vùng mã hóa vẫn chưa được giải quyết triệt để trong các khung mô hình toán học giải trình tự đa loài.

Mục tiêu và câu hỏi nghiên cứu

Mục tiêu tổng quát của luận án là xây dựng và kiểm chứng các thuật toán kết hợp đa nguồn dữ liệu nhằm tăng độ chính xác của dự đoán cấu trúc gen đơn đồng dạng (single isoform) và mở rộng mô hình để dự đoán các exon ghép nối thay thế (overlapping alternatively spliced exons).

Luận án triển khai ba mục tiêu và câu hỏi nghiên cứu cụ thể:

1. Thiết lập mô hình suy luận tuần tự kết hợp bộ phân loại (classifier stacking with sequential inference) thông qua Bộ kết hợp tuyến tính (Linear Combiner) và Bộ kết hợp thống kê (Statistical Combiner - JIGSAW) để tổng hợp các bộ dự đoán gen và căn chỉnh chuỗi.
2. Xây dựng mô hình Markov ẩn tổng quát phát sinh loài (Phylogenetic Generalized Hidden Markov Model - phylo-GHMM) mang tên ExAlt để phân loại và dự đoán các dạng exon ghép nối thay thế dựa trên bảo tồn trình tự giữa các loài.
3. Đánh giá thực nghiệm hiệu năng của các thuật toán trên các hệ gen sinh vật nhân thực mô hình và ứng dụng vào các hệ thống chú giải tự động quy mô lớn.

Đối tượng và phạm vi nghiên cứu

• Đối tượng nghiên cứu: Cấu trúc gen mã hóa protein (protein-coding genes) ở sinh vật nhân thực, bao gồm các tín hiệu biên (start codon, stop codon, donor site GT, acceptor site AG), các khoảng exon (initial, internal, terminal, single), intron (ở các pha đọc mã 0, 1, 2), vùng không dịch mã (5' UTR, 3' UTR) và các dạng ghép nối thay thế.
• Phạm vi không gian và dữ liệu: Dữ liệu hệ gen và biểu hiện gen từ thực vật (Arabidopsis thaliana, Oryza sativa), động vật có vú (Homo sapiens bao gồm vùng ENCODE và thử nghiệm EGASP) và côn trùng (các loài ruồi giấm Drosophila melanogaster, Drosophila erecta và các loài liên quan).
• Phạm vi thời gian: Toàn bộ tư liệu, công cụ và dữ liệu thực nghiệm được tổng hợp và xử lý trong giai đoạn 1996–2006.

---

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu trước

Tác giả đã hệ thống hóa các hướng phát triển chính của bài toán tìm gen tính toán:

1. Mô hình máy tự động hữu hạn (FSA) và HMM cổ điển: Các công trình nền tảng sử dụng cú pháp sinh học để gán nhãn trình tự ADN, tiêu biểu là HMMgene (Krogh, 2000) và VEIL (Henderson et al., 1997), áp dụng thuật toán Viterbi tìm phân tích chuỗi (sequence parse) có xác suất cực đại.
2. Mô hình Markov ẩn tổng quát (GHMM / Semi-HMM): Khắc phục giả định phân phối hình học của độ dài exon bằng cách mô hình hóa phân phối độ dài tường minh. Tiêu biểu là Genscan (Burge & Karlin, 1997), Genie (Kulp et al., 1996), GeneMark.hmm (Lukashin & Borodovsky, 1998), GlimmerM (Pertea et al., 2001), GlimmerHMM và GeneZilla (Majoros et al., 2004), SNAP (Korf, 2004), Fgenesh (Salamov & Solovyev, 2000), Augustus (Stanke & Waack, 2003).
3. Mô hình tích hợp dữ liệu ngoại sinh và so sánh hai hệ gen: Sử dụng pair-HMM hoặc pair-GHMM để căn chỉnh đồng thời hai chuỗi hệ gen và dự đoán gen: Doublescan (Meyer & Durbin, 2002), Projector (Meyer & Durbin, 2004), SLAM (Alexandersson et al., 2003), TWAIN (Majoros et al., 2005), Twinscan (Korf et al., 2001), SGP-1 (Guigó et al., 2003), SGP-2 (Parra et al., 2003), GeneWise (Birney et al., 2004), GenomeScan (Yeh et al., 2001).
4. Mô hình phân tích phát sinh loài trên nhiều hệ gen: Sử dụng mô hình tiến hóa ADN kết hợp HMM hoặc GHMM: Evogene (Pedersen et al., 2006), Exoniphy (Siepel & Haussler, 2004), Shadower (McAuliffe et al., 2004), N-SCAN (Gross & Brent, 2006).
5. Các hệ thống kết hợp dự đoán (Combiners) và đường dẫn chú giải (Annotation Pipelines):
   • Phương pháp dựa trên luật: GeneComber (Karplus et al., 2003; Murakami & Takagi, 1998) kết hợp Genscan và HMMgene.
   • Mô hình đồ thị xác suất: DIGIT (Yada et al., 2003) giả định các công cụ độc lập; mô hình của Pavlovic et al. (2002) xử lý phụ thuộc đồng thời nhưng bị bùng nổ $2^n$ tham số theo số lượng $n$ công cụ.
   • Khung linh hoạt: GAZE (Howe et al., 2002), EuGene (Schiex et al., 2001).
   • Đường dẫn công nghiệp: Ensembl (Curwen et al., 2004), NCBI Pipeline, OTTO (Celera; Venter et al., 2001), TIGR Pipeline (Haas et al., 2003).

Khoảng trống luận án lựa chọn giải quyết

Các bộ kết hợp trước đây hoặc giả định sai lầm về sự độc lập giữa các công cụ (DIGIT), hoặc gặp phải giới hạn toán học khi số tham số tăng theo hàm mũ (Pavlovic et al.), hoặc chỉ dựa trên các luật lọc cứng (GeneComber). Luận án của Jonathan Edward Allen giải quyết khoảng trống này bằng cách:

• Ứng dụng kỹ thuật xếp chồng bộ phân loại (classifier stacking) kết hợp cây quyết định (decision trees) để huấn luyện trọng số cho từng loại đặc trưng gen cục bộ, cho phép mô hình hóa sự phụ thuộc giữa các công cụ mà không làm tăng số lượng tham số theo hàm mũ.
• Mở rộng GHMM thành phylo-GHMM để nhận diện đồng thời ba dạng ghép nối thay thế (Intron Retention, Cassette Exon, Multiple Splice sites) kết hợp thông tin khoảng cách phát sinh loài.

---

Cơ sở lý thuyết và phương pháp nghiên cứu

Cơ sở lý thuyết và các khái niệm cốt lõi

1. Cú pháp cấu trúc gen và Máy tự động hữu hạn ($M_{FSA}$): Được biểu diễn bằng bộ 5 phần tử $M_{FSA} = (Q, q_0, q_A, \Sigma, \delta)$, trong đó $Q$ là tập trạng thái, $q_0$ là trạng thái khởi đầu, $q_A$ là trạng thái chấp nhận, $\Sigma = {A, C, G, T}$ là bảng chữ cái nucleotit, và $\delta: Q \times {\Sigma \cup {$}} \rightarrow Q$ là hàm chuyển trạng thái.
2. Mô hình Markov ẩn tổng quát ($M_{gh}$): Được biểu diễn bằng bộ 7 phần tử $M_{gh} = (Q, q_0, q_A, \Sigma, T, O, L)$, với $T$ là tập xác suất chuyển trạng thái $P(q|q')$, $O$ là tập phân phối phát xạ chuỗi con $P_O(y|q)$, $L$ là phân phối độ dài tường minh $P_L(l(y)|q)$. Xác suất của một phân tích chuỗi $\phi$ có dạng: $$P(S, \phi) = \prod_{i=1}^M P_O(y_i|q_i) \times P_T(q_i|q_{i-1}) \times P_{L_{q_i}}(l(y_i))$$
3. Mô hình hóa chuỗi thống kê (Statistical Sequence Modeling):
   • Cảm biến nội dung (Content sensors): Sử dụng Mô hình Markov nội suy (Interpolated Markov Models - IMM) bậc 0 đến 8 kết hợp kiểm định $\chi^2$ với hàm trọng số $w(S, m, k)$ để bù trừ dữ liệu huấn luyện nhỏ: $$IMM^r(S,m,k) = w(S,m-1,k) \times P_r(S[m]|S[m-1,\dots,m-k]) + (1 - w(S,m-1,k)) \times IMM^r_{k-1}(S,m,k-1)$$
   • Cảm biến tín hiệu (Signal sensors): Ma trận mảng trọng số (Weight Array Models - WAM) bậc 1 và Cây phân rã phụ thuộc cực đại (Maximal Dependence Decomposition - MDD) cho các vị trí nhận diện cắt nối (splice sites).

Phương pháp nghiên cứu thực tế

Luận án áp dụng phương pháp định lượng và kỹ thuật mô hình hóa thuật toán tính toán:

1. Bộ kết hợp tuyến tính (Linear Combiner): Chia chuỗi hệ gen thành các khoảng $I_{j,k}$ dựa trên các biên tín hiệu dự đoán; tính điểm cho các mô hình gen ứng viên bằng tổng tuyến tính các trọng số của từng nguồn bằng chứng.
2. Bộ kết hợp thống kê (Statistical Combiner - JIGSAW): Trích xuất 6 loại vector đặc trưng: điểm khởi đầu dịch mã (start - sta), điểm dừng (stop - stp), vùng mã hóa (coding - cod), intron (inr), vị trí cho (donor - don), vị trí nhận (acceptor - acc). Huấn luyện cây quyết định riêng cho từng loại đặc trưng để ước lượng xác suất hậu nghiệm cục bộ, sau đó sử dụng thuật toán quy hoạch động tìm phân tích chuỗi tối ưu.
3. Mô hình ExAlt (Exon Alternative Splicing): Tích hợp cây phát sinh loài với độ dài nhánh $\lambda_i$ vào GHMM để tính toán mức độ bảo tồn cặp bazơ và tỉ lệ bảo tồn exon/intron giữa các loài Drosophila.

Nguồn tư liệu và bộ dữ liệu thực nghiệm

• Dữ liệu hệ gen chuẩn: 1.783 gen của Arabidopsis thaliana (từ dự án TIGR); dữ liệu hệ gen lúa Oryza sativa; dữ liệu 44 vùng ENCODE ở người (thử nghiệm EGASP).
• Dữ liệu biểu hiện và tương đồng: GenBank cDNA/ESTs, RefSeq, Swiss-Prot, TIGR Gene Index, UniGene.
• Dữ liệu so sánh loài: Trình tự Drosophila melanogaster, Drosophila erecta, Drosophila yakuba, Drosophila ananassae, Drosophila pseudoobscura.

---

Nội dung chính theo từng chương

Chương 1: Giới thiệu (Introduction)

Chương 1 thiết lập các khái niệm sinh học phân tử cơ bản của cấu trúc gen nhân thực (promoter, 5' UTR, start codon, exon, intron, donor/acceptor sites, stop codon, polyA signal, 3' UTR) và hệ thống hóa bài toán dự đoán gen dưới dạng phân loại có cấu trúc (structured classification). Tác giả tổng quan quá trình phát triển thuật toán từ FSA, HMM bậc 1, GHMM với phân phối độ dài tường minh, các kỹ thuật cảm biến nội dung (IMM, WAM, MDD) đến các phương pháp căn chỉnh hệ gen kép (pair-GHMM) và đa hệ gen.

Chương 2: Bộ kết hợp tuyến tính (Linear Combiner)

Chương 2 trình bày thuật toán Bộ kết hợp tuyến tính nhằm tích hợp kết quả của nhiều bộ dự đoán gen và các căn chỉnh tương đồng. Tác giả chỉ ra hiện tượng đa dạng hóa dự đoán đúng trên tập 1.783 gen của Arabidopsis thaliana:

Chương trình	Số gen dự đoán đúng hoàn toàn	Tỷ lệ (%)
GeneMark.hmm (GM)	799	44,8%
Genscan+ (GS)	689	38,6%
GlimmerM (GA)	667	37,4%
Đồng thuận cả 3 chương trình	178	10,0%
Bộ chọn lý tưởng (Oracle Combiner)	1.205	67,6%

Khoảng cách từ 44,8% lên 67,6% là cơ sở thực nghiệm để xây dựng thuật toán phân chia chuỗi $S$ thành các đoạn $I_{j,k}$ và gán nhãn đồng thời hai mạch dương ("+") và âm ("-") thông qua quy hoạch động trên các khoảng cửa sổ trượt $S_0, S_1, S_2, S_3$ độ dài $K$.

Chương 3: Bộ kết hợp thống kê (Statistical Combiner)

Chương 3 phát triển hệ thống JIGSAW dựa trên phương pháp xếp chồng bộ phân loại. Thay vì ước lượng xác suất đồng thời phức tạp, chuỗi $S$ được phân đoạn thành các vector đặc trưng ứng với 6 loại tín hiệu và khoảng cách gen. Các cây quyết định độc lập được xây dựng cho từng loại tín hiệu để phân loại độ tin cậy của các căn chỉnh cDNA, EST và dự đoán từ các công cụ khác nhau. JIGSAW kết hợp các xác suất này vào thuật toán quy hoạch động tương tự Viterbi trên đồ thị trạng thái hai mạch để đưa ra mô hình gen tối ưu toàn cục.

Chương 4: Dự đoán các exon ghép nối thay thế (Prediction of Alternatively Spliced Exons)

Chương 4 mở rộng khung lý thuyết sang bài toán dự đoán các biến thể ghép nối thay thế. Tác giả phân loại ba cơ chế ghép nối chính:

1. Giữ lại intron (Intron Retention - IR).
2. Exon dạng hộp/nhảy exon (Cassette Exon - CE).
3. Đa vị trí cắt nối (Multiple Splice sites - MS) bao gồm vị trí donor hoặc acceptor thay thế.

Chương này xây dựng mô hình ExAlt dựa trên phylo-GHMM. Mô hình tích hợp các trạng thái mã hóa protein ở ba pha đọc mã (phase 0, 1, 2) cho cả exon cấu thành (constitutive) và exon thay thế (alternative), đồng thời kết hợp ma trận tiến hóa trình tự trên cây phát sinh loài để lượng hóa mức độ bảo tồn của các cặp dinucleotit splice site.

Chương 5: Chú giải cấu trúc gen tự động (Automated Gene Structure Annotation)

Chương 5 trình bày việc áp dụng JIGSAW vào quy trình chú giải tự động tại Viện Nghiên cứu Hệ gen (The Institute for Genomic Research - TIGR), đánh giá trên hệ gen Arabidopsis thaliana, Oryza sativa và dữ liệu ENCODE/EGASP ở người.

Bảng tổng hợp hiệu năng trên tập kiểm tra 1.783 gen Arabidopsis thaliana (Trích xuất từ Bảng 5.1 và 5.4 của luận án):

Bộ dự đoán / Kết hợp	Gen đúng hoàn toàn (Correct Gene)	Gen bị bỏ sót (Missed Gene)	Exon đúng (Correct Exons / 7.510)	Exon bị bỏ sót (ME)	Độ nhạy Nucleotit (Nucl Sn %)
GlimmerM (GA)	667	78	5.346	506	94,8%
Genscan+ (GS)	689	67	5.464	473	95,7%
GeneMark.hmm (GM)	799	57	5.764	412	96,6%
Twinscan (TS)	884	44	6.012	342	97,1%
Linear Combiner 1 (LC1 - 3 GPs)	895	36	6.077	302	97,4%
Linear Combiner 2 (LC2 - 3 GPs + Align)	981	29	6.321	245	98,0%
Statistical Combiner (SC-3)	992	27	6.368	231	98,2%
Statistical Combiner (SC-5 / JIGSAW)	1.082	18	6.612	172	98,8%

Kết quả đánh giá trên 44 vùng ENCODE tại thử nghiệm EGASP ở người cho thấy JIGSAW đạt F-score cao ở cả cấp độ nucleotit, exon và toàn bộ cấu trúc gen khi so sánh với các công cụ dự đoán độc lập và phương pháp chú giải thủ công.

Chương 6: Hiệu năng dự đoán exon thay thế (Alternative Exon Prediction Performance)

Chương 6 kiểm chứng mô hình ExAlt trên hệ gen Drosophila melanogaster cùng các loài thông tin (D. erecta, D. yakuba, D. ananassae, D. pseudoobscura). Các phát hiện chính gồm:

• Mức độ bảo tồn trình tự của các exon cấu thành cao hơn đáng kể so với các exon ghép nối thay thế.
• Tỉ lệ bảo tồn của các dinucleotit vị trí cho (donor GT) và vị trí nhận (acceptor AG) ở các vị trí ghép nối thay thế thấp hơn các vị trí cấu thành, nhưng cao hơn rõ rệt so với các vị trí splice site giả (pseudo sites).
• Việc tích hợp thông tin tiến hóa từ các loài liên hợp giúp ExAlt tăng độ đặc hiệu (specificity) trong việc phân biệt các exon thay thế thật với các đoạn bảo tồn không chức năng.

Chương 7: Kết luận (Conclusion)

Chương 7 tổng kết toàn bộ các kết quả đạt được của luận án, khẳng định tính hiệu quả của việc kết hợp đa nguồn bằng chứng thống kê và mô hình tiến hóa, đồng thời phác thảo các hướng mở rộng thuật toán trong tương lai.

---

Kết quả và những đóng góp mới

Đóng góp về mặt lý luận và phương pháp học

1. Ứng dụng thành công kỹ thuật xếp chồng bộ phân loại (classifier stacking) với suy luận tuần tự vào bài toán tìm gen: Luận án là công trình đầu tiên thiết lập khung toán học kết hợp đầu ra của các bộ dự đoán gen và các căn chỉnh sinh học mà không đòi hỏi giả định độc lập có điều kiện, đồng thời giải quyết triệt để vấn đề bùng nổ hàm mũ của không gian tham số.
2. Xây dựng mô hình Markov ẩn tổng quát phát sinh loài (phylo-GHMM) cho bài toán ghép nối thay thế: Phát triển thành công thuật toán ExAlt tích hợp độ dài nhánh tiến hóa và mô hình thay thế nucleotit để phân loại tường minh ba dạng biến thể cắt nối (IR, CE, MS).

Đóng góp về mặt thực tiễn

1. Phần mềm JIGSAW: Cung cấp một công cụ mã nguồn mở có khả năng tích hợp linh hoạt mọi nguồn dữ liệu căn chỉnh (EST, cDNA, protein, Blast matches) và các bộ tìm gen sẵn có, đạt độ chính xác tương đương hoặc vượt qua các chuyên gia chú giải thủ công trên các hệ gen phức tạp (Arabidopsis, Lúa, Người).
2. Triển khai vào đường dẫn chú giải TIGR: Thuật toán được tích hợp trực tiếp vào hệ thống đường dẫn chú giải tự động của Viện Nghiên cứu Hệ gen (TIGR), phục vụ việc công bố dữ liệu chú giải cho cộng đồng khoa học quốc tế.

Kiến nghị và giải pháp đề xuất

• Khuyến nghị các dự án giải trình tự hệ gen không nên phụ thuộc vào một công cụ dự đoán ab initio đơn lẻ mà cần áp dụng cơ chế kết hợp đa nguồn dữ liệu dựa trên cây quyết định.
• Tận dụng tối đa dữ liệu bảo tồn trình tự giữa các loài thân thuộc có khoảng cách tiến hóa phù hợp để tinh chỉnh biên giới exon và phát hiện các dạng ghép nối thay thế hiếm gặp.

---

Hạn chế và hướng nghiên cứu tiếp

Hạn chế được ghi nhận trong văn bản

• Luận án tập trung chuyên biệt vào gen mã hóa protein, chưa mở rộng trực tiếp sang các lớp ARN không mã hóa (non-protein coding RNA như microRNA, snoRNA).
• Chi phí tính toán của mô hình căn chỉnh đồng thời và phân tích chuỗi phụ thuộc vào độ dài chuỗi đầu vào; đối với các đoạn ADN dài hàng triệu bazơ, hệ thống phải sử dụng kỹ thuật phân đoạn cửa sổ trượt có giới hạn chiều dài.
• Hiệu năng của ExAlt phụ thuộc vào chất lượng của cây phát sinh loài và độ tin cậy của các căn chỉnh đa chuỗi giữa loài mục tiêu và các loài thông tin (informant species).

Hướng nghiên cứu tiếp

• Mở rộng khung mô hình để nhận diện các hiện tượng ghép nối phức tạp hơn như ghép nối chuyển đoạn (trans-splicing) trên các sinh vật như Caenorhabditis elegans.
• Tích hợp thêm các dữ liệu biểu hiện thông lượng cao thế hệ mới (CAGE, SAGE, mảng vi dòng exon) vào không gian vector đặc trưng của JIGSAW.
• Tối ưu hóa thuật toán suy luận trên phylo-GHMM để xử lý đồng thời hàng chục hệ gen hoàn chỉnh mà không cần bước lọc căn chỉnh sơ bộ.

---

Giá trị tham khảo

Luận án là tài liệu tham khảo có giá trị chuyên môn cao cho:

1. Nghiên cứu sinh và nhà nghiên cứu Tin sinh học: Cung cấp tài liệu chi tiết về mặt toán học cho các mô hình HMM, GHMM, IMM, WAM, MDD và phylo-GHMM (đặc biệt là Chương 1, Chương 3 và Chương 4).
2. Kỹ sư phát triển thuật toán và Khoa học dữ liệu: Tham khảo phương pháp thiết kế bộ phân loại xếp chồng (classifier stacking) kết hợp quy hoạch động để giải quyết các bài toán gán nhãn chuỗi có cấu trúc phức tạp (Chương 2 và Chương 3).
3. Các nhóm dự án chú giải hệ gen (Genome Annotation Teams): Tham khảo quy trình thiết lập đường dẫn tự động tích hợp dữ liệu ngoại sinh và chuẩn đánh giá thực nghiệm EGASP trên các hệ gen nhân thực lớn (Chương 5).

---

Câu hỏi thường gặp

1. Tại sao việc kết hợp nhiều công cụ dự đoán gen lại mang lại độ chính xác cao hơn từng công cụ đơn lẻ?

Theo kết quả thực nghiệm tại Chương 2 trên 1.783 gen của Arabidopsis thaliana, các công cụ đơn lẻ như GeneMark.hmm, Genscan+ và GlimmerM chỉ đạt tỷ lệ dự đoán đúng từ 37,4% đến 44,8%, và chỉ có 10% số gen được cả ba công cụ cùng dự đoán đúng. Mỗi công cụ có một tập hợp gen dự đoán đúng riêng biệt do sự khác biệt về tập dữ liệu huấn luyện và mô hình chuỗi (ví dụ GlimmerM dùng IMM, Genscan dùng MDD). Một bộ chọn lý tưởng (oracle) có thể đạt độ chính xác tới 67,6%. Thuật toán kết hợp (như JIGSAW) tận dụng sự bổ khuyết này để chọn ra các đoạn exon chính xác nhất từ từng công cụ.

2. JIGSAW giải quyết nhược điểm bùng nổ tham số của mô hình Markov liên hợp như thế nào?

Mô hình Markov liên hợp truyền thống (như của Pavlovic et al.) yêu cầu $2^n$ tham số cho $n$ công cụ dự đoán để mô hình hóa mọi trạng thái phối hợp. JIGSAW giải quyết vấn đề này bằng cách trích xuất 6 loại vector đặc trưng cục bộ (start, stop, coding, intron, donor, acceptor) và huấn luyện các cây quyết định độc lập trên từng loại đặc trưng. Cây quyết định tự động chọn lọc các biến phụ thuộc mạnh nhất mà không cần tính toán toàn bộ không gian trạng thái liên hợp, giữ cho số lượng tham số tăng tuyến tính theo kích thước cây.

3. ExAlt dự đoán những dạng ghép nối thay thế nào và sử dụng nguyên lý gì?

ExAlt dự đoán ba dạng ghép nối thay thế: Giữ lại intron (Intron Retention - IR), Exon dạng hộp (Cassette Exon - CE), và Đa vị trí cắt nối (Multiple Splice sites - MS). ExAlt sử dụng mô hình phylo-GHMM kết hợp phân phối độ dài exon/intron với ma trận thay thế bazơ trên cây phát sinh loài, dựa trên nguyên lý exon cấu thành có mức độ bảo tồn trình tự và bảo tồn dinucleotit vị trí cắt nối (GT/AG) cao hơn so với exon ghép nối thay thế.

4. Hiệu năng của Statistical Combiner (JIGSAW) vượt trội ra sao so với các công cụ đơn lẻ trên tập dữ liệu Arabidopsis thaliana?

Trên tập kiểm tra 1.783 gen với 7.510 exon, công cụ đơn lẻ tốt nhất (GeneMark.hmm) dự đoán đúng 799 gen hoàn toàn, 5.764 exon, bỏ sót 57 gen và 412 exon. Mô hình JIGSAW (SC-5 kết hợp 5 bộ dự đoán cùng dữ liệu căn chỉnh) đã nâng số gen đúng hoàn toàn lên 1.082 gen (tăng 283 gen), số exon đúng lên 6.612 exon, giảm số gen bị bỏ sót xuống còn 18 gen và số exon bị bỏ sót xuống còn 172 exon, đạt độ nhạy nucleotit 98,8%.

---

Kết luận

Luận án tiến sĩ của Jonathan Edward Allen đã giải quyết thành công bài toán nâng cao độ chính xác dự đoán cấu trúc gen nhân thực bằng cách kết hợp đa nguồn dữ liệu ngoại sinh và mô hình hóa tiến hóa sinh học. Tác giả đã đóng góp hai khung thuật toán quan trọng: mô hình JIGSAW ứng dụng kỹ thuật xếp chồng bộ phân loại với suy luận tuần tự cho cấu trúc gen đơn đồng dạng, và mô hình ExAlt ứng dụng phylo-GHMM cho cấu trúc exon ghép nối thay thế. Các kết quả thực nghiệm trên hệ gen Arabidopsis thaliana, lúa, người và ruồi giấm chứng minh tính ưu việt của phương pháp tiếp cận thống kê kết hợp, cung cấp giải pháp công nghệ hiệu quả cho các dự án chú giải hệ gen tự động quy mô lớn.

Trích đoạn nội dung tài liệu

PREDICTING GENE STRUCTURE IN EUKARYOTIC GENOMES by Jonathan Edward Allen A dissertation submitted to The Johns Hopkins University in conformity with the requirements for the degree of Doctor of Philosophy. Baltimore, Maryland September, 2006 © Jonathan Edward Allen 2006 All rights reserved UMI Number: 3240661 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.

Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3240661 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.

ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 Abstract Obtaining the complete set of proteins for each eukaryotic organism is an important step in the quest to understand how life evolves and functions. The complex physiology of eu- karyotic cells, however, makes direct observation of proteins and their parent genes difficult to achieve. An organism’s genome provides the raw data that contains the set of instructions for generating the complete set of proteins, providing the potential to obtain a complete list of proteins without having to rely exclusively on direct observations in the cell.

Computa- tional gene prediction systems, therefore, play an important role in compiling sets of putative proteins for each sequenced genome. This dissertation addresses the problem of computational gene prediction in eukaryotic genomes, presenting a framework for predicting precise single isoform protein coding genes in long contiguous stretches of DNA. The framework is extended to predict overlapping alterna- tively spliced exons in known protein coding regions. A main contribution of this work is to apply classifier stacking with sequential inference, for the first time, to the gene finding prob- lem and to develop a phylogenetic generalized hidden Markov model for the alternative splice site prediction problem.

First a linear weighting scheme is developed, which is extended to _ a statistical prediction model. The statistical model is then transformed to a new sequential inference model to predict alternatively spliced exons. il Prediction accuracy of the single isoform gene prediction methods are tested on three eukaryotic genomes: Arabidopsis thaliana, Oryza sativa and human. Applicatio n of the gene prediction methods are examined in other eukaryotic genomes.

The alternative ly spliced exon prediction model is tested in four Drosophila species under a variety of input conditions. Incorporating multiple sources of gene structure evidence is shown to substantially im- proveme single isoform gene prediction accuracy with performance beginning to rival the accuracy of expert human annotators. Results from the alternative exon prediction experi- ments demonstrate the potential to reliably predict new alternatively spliced forms of known genes. The use of cross-species sequence conservation information is shown to enhance the precision of alternatively spliced exon prediction.

Salzberg Readers: Steven L. Salzberg and Jason M. Eisner ili Acknowledgements I would like to thank my adviser Steven L. Salzberg, for his guidance, patience and support and for giving me the freedom to pursue challenging research problems.

Salzberg has made many helpful suggestions, which improved the quality of my work over the last several years. Thank you to J ason Eisner for informing me of important related work in machine learning and natural language processing. I would also like to thank other members of Dr. Salzberg’s group including Mihaela Pertea and William H.

Majoros with whom I had many enlightening discussions on gene finding work. I also benefited from the many useful discus- sions on bioinformatics topics with other members of the group including Pawel Gajer, Maria D. Delcher and Mihai Pop. Thanks to many people at.

The Institute for Genomic Research which were very helpful in providing useful data to work on including Brian Haas, Bernard Suh, Chunhui Yu, Sam Angioli, Ahwui Wang, Robin Buell, Malcolm Gardner, Jane Carlton, Elodie Ghedon and Brendon Loftus.