BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

NINH QUANG TRUNG

THUẬT TOÁN XÁC ĐỊNH CHA CHUNG GẦN NHẤT CỦA
HAI NÚT TRONG CÂY ỨNG DỤNG PHÂN TÍCH ĐA DẠNG
LOÀI VI SINH VẬT
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên, năm 2014

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn/


ii
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

NINH QUANG TRUNG

CÁC PHƢƠNG PHÁP XÁC ĐỊNH CHA CHUNG GẦN
NHẤT CỦA HAI NÚT TRONG CÂY, ỨNG DỤNG PHÂN
TÍCH ĐA DẠNG LOÀI VI SINH VẬT

Xin cảm ơn các quý Thầy (Cô) công tác tại Trƣờng Đại học Công
nghệ thông tin và truyền thông – Đại học Thái Nguyên đã tạo điều kiện cho
tôi đƣợc tham gia và hoàn thành khóa học.
Tôi xin chân thành cảm ơn.
Học viên

Ninh Quang Trung


v
MỤC LỤC
LỜI CAM ĐOAN ......................................................................................... 1
LỜI CẢM ƠN .............................................................................................. iv
MỤC LỤC ..................................................................................................... v
DANH MỤC CÁC HÌNH ẢNH ................................................................. vii
DANH MỤC CÁC BẢNG BIỂU .............................................................. viii
DANH MỤC CÁC TỪ VIẾT TẮT-THUẬT NGỮ .................................... ix
MỞ ĐẦU ....................................................................................................... 1
CHƢƠNG I: LÝ THUYẾT ĐỒ THỊ VÀ CÂY ............................................ 6
1.1 Các khái niệm cơ bản về đồ thị ........................................................... 6
1.1.1 Định nghĩa đồ thị (Graph) ............................................................ 6
1.1.2 Các khái niệm............................................................................... 6
1.1.3 Các thuật toán tìm kiếm trên đồ thị .............................................. 8
1.1.4 Độ phức tạp tính toán của BFS và DFS ..................................... 15
1.2 Các khái niệm cơ bản về cây đồ thị .................................................. 15
1.2.1 Định nghĩa và các tính chất cơ bản: ............................................ 15
1.2.2 Một số khái niệm ........................................................................ 16
CHƢƠNG II: CÁC PHƢƠNG PHÁP XÁC ĐỊNH CHA CHUNG GẦN
NHẤT CỦA HAI NÚT TRONG CÂY....................................................... 17
2.1 Giới thiệu bài toán LCA .................................................................... 17

Hình 1.9 Cây đồ thị ..................................................................................... 16
Hình 2.1 Vị trí của các phần tử trong bài toán RQM .................................. 19
Hình 2.2 Ví dụ về bài toán RQM ................................................................ 21
Hình 2.3: Cấu trúc cây phân đoạn ............................................................... 23
Hình 2.4 Hình cây của thuật toán LCA ....................................................... 29
Hình 2.5 Phân chia đoạn trong bài toán LCA ............................................. 30
Hình 2.6 Chuyển từ bài toán LCA về bài toán RQM ................................. 35
Hình 2.8 Ví dụ đƣa vài toán từ RQM về bài toán LCA .............................. 37
Hình 2.9 Cây tiến hóa.................................................................................. 43
Hình 3.1 Quy trình phân tích và xử lý dữ liệu ............................................ 55
Hình 3.2 Chất lƣợng tính theo vị trí trình tự ............................................... 59
Hình 3.3 Chất lƣợng theo từng đoạn trình tự .............................................. 60
Hình 3.4 Cây phân loài................................................................................ 63
Hình 3.5 Biểu đồ thể hiện sự đa dạng sinh vật trong mẫu dữ liệu .............. 63
Hình 3.6 Số lƣợng các đoạn ORF có liên quan đến các quy trình chyển hóa
..................................................................................................................... 65


viii
DANH MỤC CÁC BẢNG BIỂU
Bảng 1.1 Bảng lập lịch duyệt các đỉnh trong cây ....................................... 14
Bảng 3.1 Kết quả lắp ráp trình tự ................................................................ 61
Bảng 3.2 Tổng quan kết quả dự đoán gen................................................... 61
Bảng 3.4 Đa dạng loài đã đƣợc đinh tên theo từng cấp độ khác nhau........ 64
Bảng 3.5 Kết quả phân loại theo cơ sở dữ liệu KEGG ............................... 64


ix
DANH MỤC CÁC TỪ VIẾT TẮT-THUẬT NGỮ
Cụm từ viết tắt Cụm từ chi tiết

Genome Analyzer

HGP

Human Genome Project

LCA

Lowest Common Ancestor

MEGAN

MetaGenomeANalyzer

MGA

MetaGeneAnnotator

NCBI

National Center for Biotechnology Information

NGS

Next Genration Sequencing

PCR

Polymerase chain reaction


Ngày nay thông tin về trình tự gen rất hữu ích trong những nghiên
cứu về sinh học phân tử và trong nhiều lĩnh vực ứng dụng nhƣ chuẩn đoán,
sinh học pháp y, hệ thống sinh học…Quá trình đọc trình tự hay giải trình tự


2
gen (DNA sequencing) là việc xác định thứ tự các nucleotide gắn kết với
nhau dọc theo chiều dài của gen (DNA) và trình tự gắn kết nhau của các
nucleotide đƣợc gọi là trình tự gen.
Từ những năm đầu của thập niên 70 của thế kỷ trƣớc, các nhà khoa
học đã thu đƣợc thành công đầu tiên về trình tự gen bằng phƣơng pháp thủ
công. Cho đến năm 1990, dự án giải mã toàn bộ hệ genome ngƣời (HGP)
đã đƣợc khởi động nhằm tìm hiểu cơ sở di truyền bệnh, kết quả của dự án
là một hệ genngƣời với độ chính xác cao. Ngày nay, các công ty thƣơng
mại đã cho ra đời các thế hệ máy đọc trình tự dựa trên nhiều công nghệ
mới. Các kỹ thuật đọc trình tự gen đã trở nên đơn giản và nhanh chóng hơn
nhiều nhờ sự ứng dụng huỳnh quang phân tích tự động [36]. Tuy nhiên tại
thời điểm đó, đọc trình tự DNA gặp phải vấn đề là các thiết bị chi phí quá
đắt đỏ và mất thời gian để đọc nguyên vẹn hệ gen. Chúng chỉ phù hợp cho
kiểm tra các gen riêng lẻ, một số xét nghiệm phân tử, di truyền dƣợc học,
bệnh về máu và vi sinh.
Với mong muốn hiểu chi tiết về gen, các nhà nghiên cứu luôn
mong muốn giải trình tự hoàn chỉnh các DNA hoặc gen của nhiều loài
trong cuộc sống. Thiết bị đọc trình tự thế hệ mới (Next Genration
Sequencing - NGS) là một bƣớc tiến vƣợt bậc về công nghệ đọc trình tự.
Từ khả năng đọc trình tự đoạn ngắn 1500bp (Sanger) hay 100 bp
(pyrosequencing), thiết bị đọc trình tự thế hệ mới cho phép đọc đƣợc từ
8Gb đến 600Gb, có nghĩa là cho phép đọc trình tự nguyên bộ gen với số
lần rất lớn từ 10 cho đến 500 lần. Vì thế, đọc trình tự thế hệ mới còn
đƣợc gọi là đọc trình tự bộ gen (whole genome sequencing). Đọc trình tự

gen vi sinh vật và chƣơng trình đánh giá mức độ đa dạng loài.


4
Nội dung chính của luận văn đƣợc chia làm 3 chƣơng.
- Chƣơng I: Lý thuyết đồ thị và cây: Trình bày các khái niệm cơ bản
nhất về lý thuyết đồ thị và cây ứng dụng trong việc giải quyết một số bài
toán trong lý thuyết đồ thị .
- Chƣơng II: Các phƣơng pháp xác định cha chung gần nhất của hai
nút trong cây: Trình bày mối liên hệ giữa các bài toán xác định hai nút
trong cây và các phƣơng pháp giải bài toán.
- Chƣơng III: Kết quả cài đặt và đánh giá: Trình bày quy trình và
các yêu cầu cần thiết của các chƣơng trình đƣợc sử dụng thí nghiệm.
1. Đối tượng và phạm vi nghiên cứu:
- Nghiên cứu lý thuyết đồ thị và cây.
- Nghiên cứu các thuật toán xác định cha chung gần nhất của hai nút
trong cây ứng dụng trong phân tích đa dạng loài vi sinh sử dụng công nghệ
đọc trình tự thế hệ mới.
- Nghiên cứu quy trình phân tích dữ liệu trình tự hệ gen vi sinh vật
và đánh giá đa dạng loài..
2. Hướng nghiên cứu của đề tài
1. Nghiên cứu về lý thuyết đồ thị.
2. Nghiên cứu thuật toán xác định cha chung gần nhất của hai nút trong
cây Lowest Common Ancestor (LCA) ứng dụng trong phân tích đa
dạng loài vi sinh sử dụng công nghệ đọc trình tự thế hệ mới.
3. Nghiên cứu phƣơng pháp phân tích dữ liệu trình tự hệ gen vi sinh vật
và đánh giá đa dạng loài.


5


Hình 1.1: Ví dụ về mô hình đồ thị
1.1.2 Các khái niệm
Nhƣ trên định nghĩa đồ thị G = (V, E) là một cấu trúc rời rạc, tức là
các tập V và E hoặc là tập hữu hạn, hoặc là tập đếm đƣợc, có nghĩa là ta có
thể đánh số thứ tự 1, 2, 3... cho các phần tử của tậpV và E. Hơn nữa, đứng
trên phƣơng diện ngƣời lập trình cho máy tính thì ta chỉ quan tâm đến
cácđồ thị hữu hạn (V và E là tập hữu hạn) mà thôi, chính vì vậy từ đây về
sau, nếu không chú thích gì thêm thì khi nói tới đồ thị, ta hiểu rằng đó là
đồ thị hữu hạn.
Có thể phân loại đồ thị theo đặc tính và số lƣợng của tập các cạnh E:
Chođồ thị G = (V, E). Ta có một số khái niệm sau:
- Đơn đồ thị: G đƣợc gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có


7

nhiều nhấtlà 1 cạnh trong E nối từ u tới v.
- Đa đồ thị: G đƣợc gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể
có nhiều hơn 1 cạnh trong E nối từ u tới v.
- Đồ thị vô hƣớng: G đƣợc gọi là đồ thị vô hƣớng nếu các cạnh trong
E là không định hƣớng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh
nối hai đỉnh v, u. Hay nói cách khác, tập E gồm các cặp (u, v) không tính
thứ tự (u, v)

(v, u)

- Đồ thị có hƣớng: G đƣợc gọi là đồ thị có hƣớng nếu các cạnh trong
E là có định hƣớng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhƣng chƣa
chắc đã có cạnh nốitừ đỉnh v tới đỉnh u. Hay nói cách khác, tập E gồm

Với một đỉnh v trong đồ thị, ta định nghĩa bậc (degree) của v,
ký hiệu deg(v) là số cạnh liên thuộc với v. Dễ thấy rằng trên đơn đồ thị thì


8
số cạnh liên thuộc với v cũng là số đỉnh kề với v.
Đối với đồ thị có hƣớng G = (V, E). Xét một cung e

E, nếu e=(u,v)

thìta nói u nối tới v và v nối từ u, cung e là đi ra khỏi đỉnh u và đi vào đỉnh
v.Đỉnh u khi đó đƣợc gọi là đỉnh đầu, đỉnh v đƣợc gọi là đỉnh cuối của cung e.
Với mỗi đỉnh v trong đồ thị có hƣớng, ta định nghĩa: Bán bậc ra của
v kýhiệu deg+(v) là số cung đi ra khỏi nó; bán bậc vào ký hiệu deg-(v) là số
cung đi vàođỉnh đó.
- Đƣờng đi: Một đƣờng đi độ dài k từ đỉnh u đến đỉnh v là dãy
(u=x0, x1,..., xk = v) thoả mãn (xi, xi+1)

E (là 1 cạnh của đồ thị) với

i:(0 ≤ i ≤ k).Đỉnhu gọi là đỉnh xuất phát, v gọi là đỉnh kết thúc của đƣờng
đi. Đƣờng đi không cócạnh nào đi qua hơn 1 lần gọi là đƣờng đi đơn.
- Chu trình: Đƣờng đi có đỉnh xuất phát trùng với đỉnh kết thúc gọi
là chu trình. Tƣơng tự ta có khái niệm chu trình đơn.
1.1.3 Các thuật toán tìm kiếm trên đồ thị
a. Thuật toán tìm kiếm theo chiều sâu DFS (Depth – First – Search)
Là một thuật toán duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị.
Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi nhƣ gốc) và
phát triển xa nhất có thể theo mỗi nhánh.
Thông thƣờng, DFS là một dạng tìm kiếm thông tin không đầy

các đỉnh xuất hiện theo thứ tự của lần duyệt đến sau cùng khi thực hiện giải


10

thuật. Một lần duyệt hậu thứ tự một cây biểu thức sẽ cho ra một ký pháp
hậu tố.
 Duyệt đảo hậu thứ tự (reverse postordering): Kết quả của cách duyệt
này là sự đảo ngƣợc lại thứ tự trong kết quả duyệt hậu thứ tự. Thông
thƣờng, khi duyệt cây, cách này cho ra cùng kết quả với duyệt tiền thứ tự,
nhƣng xét tổng quát, khi duyệt một đồ thị, tiền thứ tự và đảo hậu thứ tự cho
ra kết quả khác nhau. Với các đồ thị có hƣớng và không có vòng, cách
duyệt đảo hậu thứ tự cho ra một trât tự tô-pô của đồ thị đó.
Thuật toán tìm kiếm theo chiều sâu của đồ thị vô hướng:
- Ý tƣởng thuật toán:DFS trênđồ thị vô hƣớng cũng giống nhƣ khám
phá mê cung với một cuộn chỉ và một thùng sơn đỏ để đánh dấu, tránh bị
lạc. Trong đó mỗi đỉnh s trong đồ thị tƣợng trƣng cho một cửa trong mê cung.
Ta bắt đầu từ đỉnh s, buộc đầu cuộn chỉ vào s và đánh đấu đỉnh
này này "đã thăm". Sau đó ta đánh dấu s là đỉnh hiện hành u.
 Bây giờ, nếu ta đi theo cạnh (u,v) bất kỳ.
 Nếu cạnh (u,v) dẫn chúng ta đến đỉnh "đã thăm" v, ta quay trở về u.
 Nếu đỉnh v là đỉnh mới, ta di chuyển đến v và lăn cuộn chỉ theo.
Đánh dấuv là "đã thăm". Đặt v thành đỉnh hiện hành và lặp lại các bƣớc.
 Cuối cùng, ta có thể đi đến một đỉnh mà tại đó tất cả các cạnh kề
với nó đều dẫn chúng ta đến các đỉnh "đã thăm". Khi đó, ta sẽ quay lui
bằng cách cuộn ngƣợc cuộn chỉ và quay lại cho đến khi trở lại
một đỉnh với một đỉnh còn chƣa đƣợc khám phá. Lại tiếp tục quy trình
khám phá nhƣ trên.
 Khi chúng ta trở về s và không còn cạnh nào kề với nó chƣa bị khám
phá là lúc DFS dừng.


đỉnhsaukhiđãthămx1 sẽlà:(x2, x3..., xp, u1, u2, ..., uq).

Hình 1.7 Duyệt các đỉnh trong cây
Giảsửtacómộtdanhsáchchứanhữngđỉnhđang"chờ"thăm.Tạimỗibƣớc,tat
hămmộtđỉnhđầu
danhsáchvàchonhữngđỉnhchƣa"xếphàng"kềvớinóxếphàngthêmvàocuốidanhsá
ch.Chínhvìnguyêntắcđónêndanhsáchchứanhữngđỉnhđangchờsẽđƣợctổchứcdƣ
ớidạnghàngđợi(Queue).
Ta sẽ dựng giải thuật như sau:
Bƣớc 1: Khởi tạo:
- Các đỉnh đều ở trạng thái chƣa đánh dấu, ngoại trừ đỉnh xuất phát S là
đã đánh dấu.
- Mộthàngđợi(Queue),banđầuchỉcómộtphầntửlàS.Hàngđợidùngđểchứacác
đỉnhsẽ đƣợc duyệt theo thứ tự ƣu tiên chiều rộng.


14
Bƣớc 2: Lặp các bƣớc sau đến khi hàng đợi rỗng:
- Lấy u khỏi hàng đợi, thông báo thăm u (Bắt đầu việc duyệt đỉnh u).
- Xét tất cả những đỉnh v kề với u mà chƣa đƣợc đánh dấu, với mỗi đỉnh v đó:
1. Đánh dấu v.
2. Ghi nhận vết đƣờng đi từ u tới v (Có thể làm chung với việc đánh
dấu).
3. Đẩy v vào hàng đợi (v sẽ chờ đƣợc duyệt tại những bƣớc sau).
Bƣớc 3: Truy vết tìm đƣờng đi:
Ví dụ: Xét đồ thị dƣới đây, Đỉnh xuất phát S = 1.

Hình 1.8 Ví dụ thuật toán tìm kiếm theo chiều sâu
Cơ sở của thuật toán tìm kiếm theo chiều rộng là lập lịch duyệt


(2,3)

(1)

1

(2,3)

2

(3)

4

(3,4)

(3,4)

3

(4)

5

(4,5)


15


ítcạnh nhất)
1.1.4Độ phức tạp tính toán của BFS và DFS
Quátrìnhtìmkiếmtrênđồthịbắtđầutừmộtđỉnhcóthểthămtấtcảcácđỉnhcònlại
,khiđócách biểu diễn đồ thị có ảnh hƣởng lớn tới chi phí về thời gian thực
hiện giải thuật:
- Trong trƣờng hợp ta biểu diễn đồ thị bằng danh sách kề, cả hai thuật
toán BFS vàDFSđềucóđộ phức tạp tính toán là O(n + m) = O(max(n,
m)).Đây là cách cài đặt tốt nhất.
- Nếu ta biểu diễn đồ thị bằng ma trận kề nhƣ ở trên thì độ phức tạp
tính toán trong trƣờng hợp này là O(n + n2) = O(n2).
- Nếu ta biểu diễn đồ thị bằng danh sách cạnh, thao tác duyệt
những đỉnh kề với đỉnh u sẽ dẫn tới việc phải duyệt qua toàn bộ danh sách
cạnh, đây là cài đặt tồi nhất, nó có độ phức tạp tính toán là O(n.m).
1.2 Các khái niệm cơ bản về cây đồ thị
1.2.1 Định nghĩa và các tính chất cơ bản:
Cây là một đồthịmà trong đó hai đỉnh bất kì đều đƣợc nối với nhau
bằng đúng một đƣờng đi. Nói cách khác một đồ thị vô hƣớng liên thông
không chứa chu trình là một cây.
Rừng là hợp (disjoint union) của các cây.


16

Ví dụ:

c
b

m


v. Khi đó, u đƣợc gọi là cha của v; v là con của u.

- Các đỉnh có cùng cha đƣợc gọi là anh em.
- Tổ tiên của một đỉnh khác gốc là các đỉnh trên đƣờng đi từ gốc đến
đỉnh đó.
- Con cháu của v là các đỉnh có v là tổ tiên.
- Các đỉnh của cây không có con đƣợc gọi là lá.
- Các đỉnh có con đƣợc gọi là đỉnh trong.
- Trong một cây, cho a là một đỉnh. Cây con với gốc a là đồ thì con
của cây đang xét, bao gồm a và các con cháu của nó cùng tất cả
các cạnh liên thuộc với các con cháu của a.
- Mức của một đỉnh v trong một cây có gốc T là khoảng cách từ
gốc đến v.
- Mức lớn nhất của một đỉnh bất kỳ trong cây gọi là chiều cao của cây.