MỞ ĐẦU 
1. Lý do chọn đề tài 
Việc phân tích dữ liệu biểu hiện gien, mà cụ thể là phân nhóm các gien
có sự biểu hiện giống nhau trong từng thời điểm thành các nhóm (cluster)
được thực hiện bởi các thuật toán phân cụm (clustering methods). Các thuật
toán này thường tìm cách nhóm các gien có sự biểu hiện phụ thuộc nhau trên
toàn bộ các điều kiện thí nghiệm. 
nghiệm. Tuy nhiên, trên thực tế các gien thường chỉ
thể hiện phụ thuộc với nhau trên một số điều kiện nào đó và độc lập với nhau
trong điều kiện khác. Điều này dẫn đến một hạn chế rất lớn của các thuật toán
clustering là không thể tìm ra được các gien chỉ thể hiện giống nhau trên một
số điều kiện thí nghiệm. Để khắc phục hạn chế này, người ta đã đề xuất một
 phương pháp phân cụm mới có tên là biclustering (hoặc co
co-clustering).
-clustering). Các
thuật toán biclustering sẽ tìm cách phân cụm đồng thời trên các hàng (gien) và
và
cột (condition) của ma trận dữ liệu biểu hiện gien nhằm tìm ra các ma trận
con thoả mãn một số tiêu chí đặt ra, từ đó có thể giúp chúng ta hiểu thêm các
tiến trình sinh học giữa các gien trong các cá thể. Nhưng gần như tất cả các
 phương pháp tiếp cận đến nay là heuristic và không đảm bbảo
ảo để tìm giải pháp
tối ưu.
Trong trường hợp dữ liệu biểu hiện gien
gien   theo chuỗi thời gian,
gian, thì các
mẫu sinh học thường được đo theo một thời điểm 
điểm  nhất định nhằm quan sát
các tiến trình sinh học xảy ra trong các cá thể. Vì vậy, việc tìm ra các mẫu có

thể hiện giống nhau trong một khoảng thời gian 
gian   liên tục 
tục  nào đó,
đó, có thể hình
dung như chúng vừa hoàn thành 1 tiến trình sinh học, hoặc một giai đoạn
chức năng sinh học nào đó. 
đó. Việc phân tích trên dữ liệu 
liệu thể hiện gien cho phép
hiểu được cơ chế điều khiển gien và tương tác giữa chúng, các tri thức này có
thể được sử dụng trong nghiên cứu chế tạo thuốc, phát hiện khối u, ... và các

1


 

nghiên cứu lâm sàng. 
sàng.  Các mẫu dữ liệu này có thể coi như là một bicluster 
gồm các hàng và các cột liên tục 
tục trong ma trận. 
trận. 
Với trường hợp 
hợp  dữ liệu biểu hiện gien theo chuỗi thời gian,
gian, người ta đã
đề xuất các thuật toán hiệu quả với thời gian chạy là tuyến tính, hoặc một hàm
đa thức để tìm ra các bicluster tốt. Các thuật toán này không khai phá trực tiếp
dữ liệu gốc, mà sẽ chuẩn hóa sang một dạng dữ liệu mới, sau đó xây dựng các 
các  
cây hậu
hậu   tố để tìm kiếm. Mỗi cây hậu 

hậu  tố sẽ biểu diễn một ma trận dữ liệu, và
việc tìm các bicluster được coi như tìm một xâu con chung lớn nhất của một
tập các xâu dựa vào cây hậu 
hậu  tố.
Trong luận văn này, chúng tôi đặt mục tiêu nghiên cứu và ứng dụng các
thuật toán này trong việc khai phá các bicluster trong dữ liệu biểu hiện gien
theo chuỗi thời gian 
gian dựa trên cây hậu tố.
tố.
2. Mục đích nghiên cứu  
- Nghiên cứu các thuật toán biclustering
biclustering cho trường hợp dữ liệu
liệu biểu
hiện gien theo 
theo chuỗi
chuỗi  thời gian (nội dung chính) 
chính) 
toán   bic
 biclus
luster
tering
ing vào các tập dữ liệ
liệuu biể
biểuu
- Áp dụng một số thuật toán 
hiện gien theo chuỗi thời gian cụ thể, phân tích và đánh giá các biclusters
thu được. 
được. 
3. Đối tượng nghiên cứu 
Các lý

lý thuyết
thuyết cơ
cơ bản
bản về
về phân
cây hậu
tố.dữ
tố. 
  liệu và dữ liệu biểu hiện gien
-- Các
cụm
theo chuỗi thời gian. 
gian. 
4. Giả thuyết khoa học 
- Việc sử dụng các thuật toán biclustering sẽ cho phép tìm ra được các
gien thể hiện giống nhau trên một khoảng 
khoảng   điều kiện, từ đó có thể tìm ra các
gien liên quan đến một số tiến trình sinh học cụ thể. 
thể. 
5. Nhiệm vụ nghiên cứu  
- Tìm hiểu một số thuật toán biclustering hiệu quả
2


 

- Cài đặt một số thuật toán và
v à thử nghiệm với dữ liệu thực tế 
tế  
- Phân tích

tích các ưu nhược 
nhược điểm và cải tiến các thuật toán nếu có thể được. 
được. 
6. Phạm vi nghiên cứu 
- Các thuật toán phân cụm dữ liệu và dữ liệu biểu hiện gien theo chuỗi
thời gian của một số loài. 
loài. 
7. Phương pháp nghiên cứu 
thuyết 
- Phương pháp đọc tài liệu, phân tích, tổng hợp lý thuyết 
- Phương pháp xây dựng giả thuyết 
thuyết 
- Phương pháp quan sát, thực nghiệm và đối chứng. 
chứng. 

3


 

NỘI DUNG
Chương I. GIỚI THIỆU 
th eo chuỗi thời gian 
1.1. Dữ liệu biểu hiện gien theo
Dữ liệu biểu 
biểu hiện gien có thể biểu diễn dưới dạng ma trận trong đó mỗi
hàng tương ứng với một gien và mỗi cột tương ứng với một thời điểm hay
một điều kiện thí nghiệm. Mỗi ô của ma trận chứa mức độ 
độ   thể hiện của gien
trong điều kiện tương ứng. Tuỳ theo độ phức tạp của bộ gien, ma trận có thể

có từ vài nghìn tới vài chục nghìn 
nghìn dòng và từ vài cột cho tới vài trăm cột. 
cột. 
Khi chúng ta  phân tích dữ liệu
liệu   biểu hiện gien theo chuỗi thời gian,
chúng ta cần tìm các mẫu (bicluster) dữ liệu gồm các dòng có thể không cần
liên tục, nhưng các cột liên tục (theo thời gian).
gian) . Điều đó dẫn đến 
đến giảm bớt độ 
độ 
 phức tạp và biến đổi
đổi   của thuật toán biclustering so với trường hợp tìm các
 bicluster thông thường
thường.. Chúng ta quan tâm đến quá trình sinh học diễn ra
trong suốt tiến 
tiến  trình từ khi
khi bắt
 bắt đầu đến khi kết thúc 
thúc  để biết được sự biến đổi
của một gien hoặc một nhóm gien sau một tiến trình sinh học nào đó .  Như
vậy, trong trường hợp này một bicluster là một tập con các dòng (gien) và một
tập con liên tục các cột (điều kiện).
kiện) .  Như hình 1.1 minh họa 3 quá trình sinh
học  (P1, P2 và P3) của các tập gien khác nhau được miêu tả bằng 3 biclusters
học
b iclusters
với các cột liên tục.
tục.
Mục đích cuối cùng của các thuật toán 
toán  biclustering trong trường hợp

này là tìm
tìm ra một tập con các biclusters  Bk  = (I kk  ,  J kk )    với các cột liền kề, mà
mỗi bicluster  B
 Bk  có thể hiện các tính chất
chất   đặc trưng riêng 
riêng  trong mỗi quá trình
sinh học nhất định.
định.

4


 

Time
G
e
n
e
s

 Hình 1.1 Quá trình sinh học và biclusters với các cột liền kề  

1.2. Các kiểu thuật toán Biclustering 
Mặc dù nhiều thuật toán đã được 
được   đề xuất để giải quyết các vấn đề
chung của biclustering
biclustering [10], [23] như phân lớp và dự đoán, khai phá chuỗi
theo thời gian, phân cụm... 
cụm...   và đã biết đến tầm quan trọng của 

của   việc phát hiện
các mẫu cục bộ,
bộ, nhưng chỉ có một vài đề xuất gần đây đã giải quyết vấn đề
này trong trường hợp cụ thể của 
của  dữ liệu biểu hiện gien theo 
theo   chuỗi thời gian.
gian.
 Những phương pháp tiếp cận 
cận đó
đó  thuộc
thuộc  một trong hai nhóm các thuật toán sau:
1. Tìm kiếm tham lam lặp đi lặp lại (Greedy iterative search): như
thuật toán CC-TSB[30].
2. Liệt kê đầy đủ (Exhaustive enumeration): như các thuật toán qClustering [12], q-Subsequences [27], ts-Clustering [28], CCC-Biclustering
[17] và e-CCC-Biclustering [18].
 Những phương pháp này làm việc với một 
một  ma trận 
trận  biểu
 biểu   hiện gien,
nhằm
hằm   tìm kiếm các biclusters bằng
biclusters  bằng cách 
cách  xác định tập con các gien và tập con
các điều kiện (thời điểm)
điểm) trong khoảng thời gian 
gian  liên tục.
tục. Thuật toán CCCBiclustering [17] và e-CCC-Biclustering [18] thuộc nhóm thuật toán liệt kê
đầy đủ, sẽ được trình bày trong luận 
luận  văn và mô tả 
tả  chi tiết ở   chương 3, cả

c ả hai
th
thuật
uật toán 
toán giải quyết bài toán 
toán theo hướng dựa vào 
vào ma trận biểu hiện gien
gien theo
chuỗi thời gian, để tìm các biclusters với mẫu biểu hiện 
hiện hoàn hảo và 
và mẫu biểu
hiện  xấp xỉ.
hiện
xỉ. 
5


 

Dưới đây chúng tôi xin trình bày tóm tắt ý tưởng của các thuật toán
 biclustering đã được một số tác giả đề xuất, để giải quyết bài toán tìm các
 biclusters trong dữ liệu biểu
biểu hiện gien theo
theo  chuỗi
chuỗi  thời gian. 
gian. 

1.2.1. Thuật toán CC-TSB
Zhang [30]
[30] đề xuất thuật toán CC-TSB (Time-Series Biclustering),

trong đó có cải tiến 
tiến  các thuật toán heuristic của Cheng and Church [4],
[4], bằng
cách thêm hoặc xoá 
xoá  một phần cột tiếp giáp 
giáp  của bicluster đã
đã   xây dựng, 
dựng,  do đó
 bicluster kết quả chỉ có các cột liền
liền kề nnhau.
hau.
toán CC-TSB có hai thủ tục chính là: thủ tục xóa và thủ tục chèn
Thuật toán
lặp đi lặp lại.
lại. Kết quả 
quả thu được của thuật toán là một ma trận con, miêu tả một
 bicluster. Đầu 
Đầu tiên thuật toán 
toán thực hiện, các ma trận con được xem như là toàn
 bộ ma trận biểu 
 bộ 
biểu hiện gien. Sau
Sau đó loại bỏ dần các hàng (gien)
(gien) và các cột (thời
điểm) từ ma trận con, với mục đích 
đích  giảm thiểu 
thiểu  bình phương trung bình dư
dư
lượng (MSR)
(MSR) [4]

[4] của ma trận con 
con  kết quả. Một hàng được lấy ra từ ma trận
con nếu có thể hiện khác với những hàng còn lại 
lại trong ma trận, được đo bởi tỷ 
tỷ 
lệ MSR. Nếu tỷ lệ này lớn hơn một ngưỡng thực nghiệm
nghiệ m , hàng đó sẽ bị 
bị loại
 bỏ. Cột (thời điểm
đ iểm)) được loại bỏ khỏi 
khỏi ma trận con 
con cũng được thực hiện 
hiện tương
tự
tự  như đối với hàng. Để đảm bảo 
bảo các thời điểm trong một bicluster luôn luôn
liên tục, thì chỉ có cột đầu tiên và cột cuối cùng trong ma trận con 
con   có thể bị
xóa. Quá trình xóa kết thúc khi MSR của bicluster  có kết quả thấp hơn giới
hạn . Thao tác chèn cũng được thực hiện 
hiện  tương tự cho các cột
cột,, ngược
ngược lại với
thao tác xóa thao tác chèn thêm: nếu MSR  của
của  một hàng nào đó trong 
trong ma trận
con nhỏ hơn 
hơn , gien
gien tương ứng với hàng đó sẽ được chèn vào bicluster. Thỏa
mãn với yêu 

yêu  cầu tiếp giáp trong các cột, chỉ có vùng lân cận 
cận   của ma trận con
mới  được xem xét để chèn. 
mới
chèn. 

6


 

1.2.2. Thuật toán q-Clustering
 Như trong các thuật toán biclustering đđãã đề xuất
xuất,, Ji and Tan [12] quan
tâm đến việc tìm kiếm biclusters với các cột liên tục, 
tục, được xác định bằng 
bằng một
một  
mẫu  biểu
mẫu 
biểu hiện là tập các ký hiệu liền kề 
kề  trong bảng chữ cái cho trước. 
trước.  Thuật
toán có ba giai đoạn, được mô tả 
tả như sau: 
sau: 
Giai đoạn 1: Chuyển ma trận.
trận. Ma trận biểu hiện gien gốc 
gốc được chuyển 
chuyển 


thành một ma trận "dốc
dốc",
", bằng
 bằng cách sử dụng bảng ba ký tự 
tự ∑={-1,0, 1}. 
Giai đoạn 2:
2: Sinh tập
tập  q-clusters sử dụng các hàng trong ma trận 
trận “dộc
dộc””,

mỗi  chuỗi
mỗi 
chuỗi   trình tự gồm các giá trị -1, 0 và 1. Mỗi
Mỗi   q-cluster   chứa một tập các
gien cùng mẫu
mẫu   biểu
biểu hiện trong
trong   q  thời điểm liên tục.
tục. Để
Để   tìm kiếm các gien có
cùng chuỗi 
chuỗi  trình tự 
tự  với
với   chiều dài (q - 1), trong đó q  là một tham số. Mỗi 
Mỗi   qcluster  có một
một định danh duy nhất, gọi là q-clusterID. Các q-cluster   được tạo

ra như sau: mỗi hàng (gi

(gien) trong ma trận "dốc
dốc",
", sử dụng 
dụng một khung 
khung trượt có
độ dài (q - 1) để kiểm tra.
tra. Khi kiểm tra một chuỗi con (q - 1) được xác định là
q-clusterID thì cặp (GeneID, st ) được đưa vào nhóm q-cluster   tương ứng,
ứng, trong

đó GeneID là tên của gien
gien và st  là vị trí 
trí điểm bắt đầu của khung trượt (q -1).
Để xác định chất lượng của bicluster
bicluster,, ta sử dụng giá trị  MSR, do đó 
đó nếu
nếu  
 MSR  nhỏ hơn giá trị do người 
người   dùng quy định 
định  thì những bicluster chất lượng

tốt sẽ 
sẽ được giữ lại,
lại, và phần
và phần khác có thể được loại bỏ. 
bỏ.  
Giai đoạn 3:
3: Đưa ra các bicluster từ q-clusters và sắp xếp theo vị trí st ,
tất cả các cặp
cặp ( GeneID, st ) có cùng vị trí được 

được nhóm lại với nhau và xác định
bicluster trong mỗi
mỗi   q-cluster   với tất cả các gien cùng 
cùng   vị trí 
trí  bắt
bắt đầu 
đầu   cùng mẫu
với q điều kiện.
kiện. Các bicluster có giá trị MSR nhỏ hơn giá trị người dùng định
nghĩa sẽ có chất lượng tốt hơn. 
hơn. 

1.2.3. Thuật toán q-Subsequences
Zeng and Liu [27]
[27] đề xuất cách tiếp cận biclustering cho việc phân tích
khoảng thời gian trong cụm dữ liệu biểu 
biểu   hiện gien
gien,, kết hợp phương pháp của
7


 

q-Clustering  và một số 
số  ý tưởng của thuật toán 
toán   CCC-Biclustering. Thực chất

cách tiếp cận là q-Clustering dựa trên cây hậu tố.
tố . Tuy nhiên, lại không xét tới
tới  

các mối quan hệ 
hệ  tác động bên ngoài và các mẫu
mẫu xấp 
xấp  xỉ
xỉ.. Đầu tiên 
tiên  ma trận 
trận  dữ
liệu biểu hiện gien được 
được  chuyển đổi 
đổi như trong 
trong kỹ thuật q-Clustering. Sau đó
xây dựng một cây hậu tố 
tố   tổng quát cho tập các chuỗi xác định 
định  mẫu cho mỗi
gien trong chuỗi
chuỗi   thời gian 
gian  của ma trận biểu hiện.
hiện. Mục tiêu để tìm các
biclusters với các cột liền kề nhau mà mẫu 
mẫu  biểu
biểu hiện có chiều dài q và trong
khoảng thời gian 
gian hoạt động của gien.
gien . Để làm được điều này sau khi xây dựng
dự ng
cây hậu tố 
tố ban
cho tập các chuỗi,
chuỗi,  tất cả các nút có độ sâu lớn hơn q bị
 bị xóa 

xóa 
 ban đầu cho 
 bỏ.. Các thông tin
 bỏ
tin trong mỗi nút lá (chứa số 
số  lần xuất hiện của 
của  q-subsequence)
được  phân
được
 phân tích và sử dụng để xác định các bicluster trong khoảng thời gian và
q thời điểm. Nút lá được chia thành ba loại. Một loại nút lá, được gọi là nút lá
không hoạt động, đại diện cho một q-subsequence mà không xuất hiện trong

 bất kỳ
kỳ   chuỗi phân tích nào
nào.. Một loại 
loại  nút lá, được gọi là nút 
nút  hoạt động, đại
diện cho một q-subsequence  xuất hiện chỉ một lần trong chuỗi phân tích, hai
loại nút lá và tương ứng 
ứng với
với  q-subsequences như vậy không đưa ra phân tích.
Loại nút lá cuối cùng 
cùng   tương ứng với q-subsequences  xuất hiện 
hiện  ít nhất hai lần
trong cùng một gien hoặc ít nhất hai gien, những
những nút này tương ứng với các
 biclusters trong khoảng thời gian phân tích
tích..


1.2.4. Thuật toán ts-Clustering
Yin [28] đề xuất tìm cụm liên kết trong
trong biểu
 biểu hiện gien theo chuỗi thời
gian gọi là ts-Clusters, cho phép những biểu hiện gien
gien trong cụm được gắn
kết trên các tập con khác nhau 
nhau  của các điều kiện, và mức độ biểu hiện tương
đối được 
được  ưu tiên 
tiên  thực hiện,
hiện, có thể hạn chế được tác động gây nhiễu.
nhiễu. Trong
cáchh thiết lập này, các cặp gien quy định trong nhóm có các mẫu
các
mẫu  liên kết 
kết hoặc
hoặc  
thời gian chuyển mẫu liên kết.
kết. Đây
Đây   là một thuật toán phân cụm 
cụm   dựa trên cây
cơ sở để 
để phát
 phát hiện ra các ts-Clusters.
8


 


Mô hình ts-Cluster   khai thác thời gian chuyển 
chuyển   mẫu như sau: giả sử 
sử  tập
m gien G = {g1 , g1 ,. . . , gm }, tập n thời điểm với khoảng thời gian nhất  định
định,, T 
= {t 1 , t 2 , . . . , t n }, và ma trận  D= G x T trong đó d i,j
i,j là các giá trị biểu hiện của

gien i tại thời điểm j. Những
 Những  giá trị khuyết 
khuyết thiếu trong ma trận được “lấp đầy” 
đầy”  
 bởi một số ngẫu nhiên. S
Sau
au đó, xác định Y = < t ii11 , t ii22 ,. . . , t ilil > theo một trình
tự thời gian nếu  và chỉ nếu t ii11 < t ii22 < ... < t ilil  và chiều dài của Y  là |Y | = l.
Chuỗi thờ i gian Y là L-segment  nếu chiều dài của |Y | là (L + 1).
Xét hai chuỗi
chuỗi  thời gian L-segment là Y P = <t ii11 , t ii22 ,. . . , t ilil>, và Y q = đó  t iill < t  jl, mối
giữa  thời gian chuyển 
chuyển  Y P và Y q  nếu
t  j2 ,. . . , t  jl>  mà ở đó 
mối quan hệ giữa 
và chỉ nếu 
nếu  jjk  = ik  + t ’’  , với mọi k   [1, l] , trong đó t ’ 
’ là một hằng số là khoảng
thời gian giữa 
giữa  Y q  và Y P (Y q  cũng giống như Y P khi t’ = 0   và đó là khoảng thời
hệ giữa

giữa  
gian chuyển 
chuyển  bằng
bằng 0).
0). Khi Y q và Y  p giống nhau ta xét đến các mối quan hệ 
chuỗi thời gian và khoảng thời gian trong các trường hợp sau:
-  Nếu dựa vào một gien  x  và một l-segment <t  ,i t  j> có 3 cách chuyển
đổi là, d  xi và d  xj giá trị biểu hiện của gien  x tại thời điểm t i và t  j , và tham số 
số  
(>0) là một 
một ngưỡng điều chỉnh.
chỉnh.
(1) Điều chỉnh lên,
lên, có nghĩa là O x(t  ,i t  j) =   , nếu d  xj - d  xi >   
(2) Không điều chỉnh,
chỉnh, có nghĩa là O x(t  ,i t  j) =   , nếu d  xj - d  xi≥   
(3) Điều chỉnh xuống,
xuống, có nghĩa là O x(t  ,i t  j) =   , nếu d  xj - d  xi < -  
- Nếu dựa vào 2 gien  x, y và (n-1)-segment Y = <t ii11 , t ii22 , ... , t iinn >, x và  y 
là giống nhau nếu Ox(t  ,t 
(i
(  i1 , i2 ,..., in) và t  là
i  j )= O y(t ((j+
j+t) ,t (k+
(k+t)) trong đó: j,k  
khoảng cách thời gian giữa hai sự kiện.
kiện. 
Dựa vào
vào các định nghĩa: chuỗi thời gian; 
gian; L-segment 

 L-segment ; tính O và xác định
như ở trên, một ts-Cluster được xác định như sau: C   U ir 1   X iY i  {cxy},  X i là
một   tập các gien (Xi   G) và Y i là tập thời điểm (Y
một
(Yi   T), thì  X i x Y i  là một
ma trận con đặc biệt của D = G x T . C là một
một ts-Cluster  nếu và chỉ nếu:
nếu: 

9


 

(1)  Y 
Y i ,Y  j ,1   i, j   r, |Y i| = |Y  j |,
(2)  Y 
Y i ,Y  j ,1   i, j   r , quan hệ thời gian chuyển giữa Y i và Y  j 
(3)  g x  X i ,  g y  X  j , 1   i, j   r  giả
 giả sử  t là khoảng thời gian Y i đến
i  j )= O y(t (i+t) ,t (j+t)).
Y  j ,  t 
t ,i  t  j  Y i điều kiện O x(t  ,t 
Khi β  được xác 
xác  định
định   là tập 
tập  tất cả ts-Cluster   thỏa mãn 
mãn  các điều kiện giàng

 buộc, khi C    β 

β  gọi là ts-Cluster  cực đại 
đại nếu và chỉ nếu không có cụm C’    β 
β  
mà C’
C’ chứa C.
C.
Vấn đề được giải quyết bằng 
bằng   thuật toán ts-Clustering là: tìm tất cả tsđại, một ngưỡng 
ngưỡng  cực đại 
đại  được
được   người dùng 
dùng  quy định, tính lượng
Cluster   cực đại,
thời điểm/lượng gien tối thiểu.
thiểu.
Thuật toán ts-C
-Clustering
lustering có hai bước chính:
chính : Trước tiên 
tiên  xây dựng một 
một 
cây TS-Tree
-Tree ban
 ban đầu ("Construct Initial TS-Tree"),
"), ở đó các thông tin chuyển
đổi  từ
đổi
từ  ts-Clusters ban
 ban đầu của tất cả ll-segments được xác định. Chỉ điều chỉnh 
chỉnh 

giá trị theo hai nhánh 
nhánh lên hoặc xuống.
xuống. Bước
Bước thứ hai phát triển 
triển cây ban đầu 
đầu để
tìm tất cả ts-Cluster   cực đại, kết hợp 
hợp  tìm kiếm 
kiếm  theo chiều 
chiều  rộng
rộng   cho đến khi
chiều cao đạt mint  - l, thì tìm kiếm theo độ sâu. 
sâu. 
Mặc dù ts-Clustering  không sử dụng 
dụng  hướng
hướng   tiếp cận 
cận  trực tiếp ma trận 
trận 
gốc,, nhưng thao tác O có thể được xem như là một bước chuyển 
gốc
chuyển hoá từ cây TStree đã
đã  xây dựng bằng cách sử dụng phân nhánh với hai biểu tượng lên “ ” và

xuống ” ” .[28]

1.3. Định nghĩa và bài toán bicluster trong dữ liệu thể hiện gien theo
chuỗi thời gian. 
Với ma trận (n×m), ở đó mỗi thành phần là một giá trị thực. Trong
trường hợp
hợp   các ma trận biểu 

biểu  hiện gien, aij  miêu tả mức thể hiện của gien i 
trong điều kiện j. Ví dụ bảng minh họa dưới đây. 
đây. 

10


 

 Bảng 1: M inh
inh họa ma trận dữ liệu biểu hiện gien. 

Chúng ta sẽ xem xét trường hợp tổng quát của ma trận dữ liệu  A với tập
các hàng X  và tập các cột Y , ở đó mỗi thành phần  Aij tương ứng với giá trị đặc
trưng của mối quan hệ giữa hàng i và cột j.
Cho một ma trận  A với n hàng và m cột, được xác định bởi các tập con
các hàng X =  {x1 ,...,xn} và tập con các cột 
cột  Y =  {y1 ,...,ym}, ký hiệu ( X,Y 
 X,Y ) là thể
hiện của ma trận A. Nếu  I ⊆  X  và J ⊆  Y   là tập con 
con riêng lẻ của hàng và cột,
thì  A IJ  = (I, J)  là ma trận con của ma trận  A  mà mỗi thành phần aij  thuộc về
ma trận con với tập hàng I  và tập cột J .
Một Bicluster là một tập con của các hàng,
hàng , thể hiện
hiện trạng thái tương tự
thông qua tập con của các cột và ngược lại. Bicluster A IJ  = ( I,
 I, J ) gồm 
gồm  tập con 
con 

các hàng và tập con 
con các cột, ở đây I = {i1 ,…, ik } là tập con các hàng (I ⊆X và
k ≤ n)
n) và J= { j1 ,…, js} là tập con các cột ( J ⊆ Y và s
và s ≤ m).
m).
Các thuật toán biclustering nhằm xác định tập các bicluster   B
Bk  = (I kk  ,  J kk )  ,
 Bk   thỏa mãn một vài tính chất đặc trưng riêng
ở đó mỗi bicluster  B
riêng biệt.
 biệt. Những
đặc tính mà một bicluster phải tuân theo thay đổi tùy theo cách tiếp cận.

Trong luận văn này chúng tôi xin trình bày thuật
thuật toán biclustering 
biclustering  không xử
lý trực tiếp 
tiếp  trên ma trận 
trận  gốc
gốc   A
A, mà các phần tử của 
của  nó được chuẩn hóa sang
ma trận 
trận  biểu
biểu hiện
hiện gi
gien
en   A
A’gồm tập các ký hiệu trong bảng chữ cái  miêu tả hoạt

động của 
của  mẫu gien,
gien, kỹ
kỹ thuật tiếp cận này được sử dụng 
dụng  trong thuật toán,
toán, có thể
 phát huy khả năng
năng  xử lý 
lý của thuật toán 
toán khi khai phá các mẫu về sinh học. 
học. 

11


 

1.4. Các hướng tiếp cận chính để tìm bicluster trong dữ liệu biểu hiện
gien theo chuỗi thời gian 
Do chức năng của gien thường liên quan tới mức độ thể hiện   của gien
nên bằng các phương pháp phân tích dữ liệu biểu 
biểu   hiện gien, chúng ta có thể
dự đoán được chức năng của chúng hoặc một tiến trình tiếp theo. Các phương
 pháp phân cụm đã được sử dụng rộng rãi trong việc phân tích dữ liệu biểu
biểu  
hi
hiện
ện gien theo chuỗi thời gian, 
gian,  có thể tìm ra được nhóm gien có thể hiện
tương đối giống nhau. Các thuật toán Biclustering tìm cách phân nhóm các

đối tượng theo cả hai chiều để tìm ra một tập các gien có thể hiện giống nhau
chỉ trong một số điều kiện hay 
hay  một số 
số  thời điểm 
điểm  liên tục 
tục  nào đó.
đó. Tuy nhiên,
khó khăn mà các thuật toán biclustering là việc tìm lời giải rất khó khăn vì
đây là bài toán NPNP-khó, rất khó để tìm được nghiệm tối ưu toàn cục. Vì vậy,
kỹ thuật tiếp cận để xử lý dữ liệu biểu 
biểu   hiện gien theo chuỗi thời gian,
gian, trên cơ 
sở các giá 
giá  trị của sự biến đổi trạng thái giữa các thời điểm. Kỹ thuật tiếp cận
này sử dụng hai hoặc 
hoặc  ba
ba ký tự và nó thường được
được  xử lý bằng bước 
bước chuẩn hóa
ma trận dữ liệu biểu 
biểu  hiện
hiện   gien theo chuỗi thời gian 
gian  gốc ban đầu.
đầu. Từ ma trận
 biểu  hiện gien đã được chuẩn hóa, việc tìm kiếm các bicluster sẽ hiệu quả hơn
 biểu
và thời gian thực hiện cũng ít tốn kém hơn. 
hơn.   Một thuật toán hiệu quả sử dụng 
dụng 
kỹ thuật 

thuật xử lý 
lý chuỗi
chuỗi  dựa trên cây hậu tố tổng quát, là ý tưởng chính của
của  thuật
toán được
được   đề xuất. Mà ở đó có 
có   mối quan hệ 
hệ  tương đồng giữa các biclusters
với các nút trong của cây hậu
hậu  tố tổng quát đã 
đã xây dựng cho các bộ
các bộ  chuỗi (các
hàng trong ma trận)
trận) đại diện cho các mẫu
mẫu   biểu
biểu hiện
hiện   của
của   mỗi gien trong ma
trận.. Thuật toán này sẽ được chúng tôi trình bày 
trận
bày chi tiết 
tiết trong chương 3.

1.5. Mục đích của luận văn 
Mục đích của luận văn này là trình bày 
bày   các thuật toán biclustering dựa
trên cây hậu tố tổng quát để tìm kiếm các bicluster hoàn hảo và các bicluster 
xấp xỉ trong dữ liệu biểu hiện gien theo thời gian. Sau đó thực hiện các thuật
12

 

toán này trên một số tập dữ liệu sinh học thực tế để minh họa khả năng hoạt
động cũng như kết qủa của các thuật toán. Phân tích các bicluster thu được
 bằng cách sử dụng các thông tin chú giải gien (Gen Ontology) để thấy được ý
nghĩa sinh học của các bicluster đã tìm được.
1.6. Cấu trúc của luận văn 
Cấu  trúc của luận văn được chia thành các phần như sau: 
Cấu
sau: 
Phần 1:
1: Mở đầu –  Trình bày lý do, mục đích nghiên cứu, đối tượng, phạm vi,
nhiệm vụ, và
và phương
 phương pháp 
pháp nghiên cứu. 
cứu. 
2: Nội dung –  Phần này trình bày nội dung chính của
củ a luận văn, bao gồm
Phần 2: Nội
các chương sau: 
sau: 
Chương 1:
1: Giới thiệu các khái niệm cơ bản được đề cập trong luận văn,
cũng như một số 
số  ý tưởng của 
của  thuật toán biclustering. 
biclustering.  Trong chương này
chúng tôi trình bày định nghĩa và bài toán tìm bicluster trong dữ liệu thể hiện

gien theo thời gian.
gian .
Chương 2:
2: Trong chương này chúng tôi tập trung chủ yếu trình bày các
khái niệm cũng như các ứng dụng của cây hậu tố. 
tố.  
Chương 3:
3: Chương này chúng tôi trình bày hai thuật toán biclustering
hiệu quả để tìm các biclusters với mẫu hoàn hảo và bicluster với mẫu xấp xỉ
đó là:
là: thuật toán CCC-Biclustering
CCC-Biclustering và e-CCC-Biclustering có độ phức tạp tính
toán đa thức. Cả hai thuật toán đều 
đều dựa trên cây hậu tố tổng quát.
quát.
Chương 4:
4: Ứng dụng của thuật toán biclustering vào các việc phân tích
các tập dữ liệu thực tế.
tế . Cuối cùng là phần kết luận của luận văn, những việc
đã làm được, chưa làm được và hướng phát triển tiếp theo của luận văn.
văn.

13


 

Chương II. CÂY HẬU TỐ 
2.1. Giới thiệu chung 
Cây hậu tố (suffix trees) là một cấu trúc dữ liệu biểu diễn các hậu tố

của một chuỗi.
chuỗi. Nó cho  phép thực hiện rất nhiều thuật toán
toán   hiệu quả quan
trọng  về chuỗi và được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau của
trọng
khoa học máy tính như: đối sánh mẫu, tìm xâu con chung,
chung , thống kê tần suất
“từ ”,... Đây là những bài toán trong các kỹ thuật xử lý văn bản, tìm kiếm
thông tin, tin sinh học (bioinformatics), nén dữ liệu… 
liệu…   Cây hậu tố cho một
chuỗi S là một cây có các cạnh được gắn nhãn với các chuỗi, sao cho mỗi hậu
tố của S tương ứng với đúng một đường đi từ gốc đến hậu tố đó, nó có thể sử
dụng như một sơ đồ (diagram) của trạng thái dịch chuyển.
Một trong những điểm mạnh của cây hậu tố là cho phép thay đổi và mở 
rộng cấu trúc mỗi khi có sự cập nhật dữ liệu 
liệu   mới. Tính chất này có thể 
thể   xử lý
trên một tập dữ liệu lớn với nhiều dạng dữ liệu khác nhau, đặc biệt là dữ liệu
sinh học,
học, sẽ
sẽ  tiết kiệm được thời gian và không gian xử lý dữ liệu.
liệu.  
Khái niệm đầu tiên được giới thiệu bởi 
bởi Weiner vào năm 1973, đến năm
1976 McCreight đã đơn giản hóa thao tác xây dựng cây hậu tố với thời gian
và không gian tuyến tính, và đến 1995 Ukkonen cung cấp giải thuật 
thuật dựng cây
hậu tố trực tuyến 
tuyến   với thời gian tuyến tính (On-line construction of suffix
trees) và được gọi là thuật toán Ukkonen

Ukkonen [6]. Dưới đây chúng tôi xin 
xin  được
được  
trình bày các khái niệm và giải thuật dựng cây hậu tố cũng như một số Ứng
dụng của cây hậu tố. 
tố. 

2.2. Các khái niệm cơ bản.
Định nghĩa 1: (Cây hậu tố )  Cây hậu tố T   của chuỗi |S|  kí tự 
tự  của
của   S là
cây có hướng,
hướng, có gốc và có các tính chất sau: 
sau: 
-  Các đường đi từ gốc đến lá tương ứng 1 - 1 với các hậu tố của S.
14


 

-  Mỗi nút trong, trừ nút gốc, có ít nhất là hai con. 
con. 
-  Mỗi cạnh được gán nhãn bằng một 
một chuỗi con (không rỗng
rỗng)) của chuỗi S.
-  Các cạnh bất kỳ xuất phát từ một nút chung phải bắt đầu bằng các ký tự 
tự 
khác nhau. 
-  Đối với mỗi nút lá thứ i, có nhãn là đường đi từ nút gốc đến nút đó biểu
diễn hậu tố (suffix) thứ i của chuỗi S.[5]

Để đảm bảo luôn dựng được cây hậu tố của chuỗi S  người ta thêm một ký
tự đặc biệt ($) vào cuối chuỗi S, gọi là kí tự kết thúc, như vậy 
vậy sẽ 
sẽ không có hậu
tố nào là tiền tố của một hậu tố khác.
khác. Ví dụ cây hậu tố T(bbabab). 

 Hình 2.1. Cây hậu tố của chuỗi bbabab 

Trong ví dụ minh họa cây hậu tố T   của chuỗi  = bbabab$  có bẩy hậu
tố là bbabab$, babab$, abab$, bab$, ab$, b$ và $   được đánh số 
số  từ 1 đến 7
như hình vẽ, nhãn của nút w là ab, nhãn của nút u là b và xâu baba là nhãn
của đường đi từ gốc đến giữa cạnh (u, 2).
Sau đây là một số khái niệm liên quan đến cây hậu tố: 
tố: 
Định nghĩa 2: (Chuỗi, chuỗi con , hậu tố và tiền tố ) Một chuỗi S là danh sách
các ký tự trên bảng chữ cái ∑ (có |∑|
|∑| ký tự) được viết liên tục 
tục  từ trái sang
 phải. Bất kỳ xâu con S[i..j]  thu được 
được cũng
cũng  là một xâu ký tự liên tục trong S, có
vị trí bắt đầu tại i và kết thúc tại  j. Đặc biệt, S[1..i] là tiền tố của S kết thúc tại
vị trí i và S[i..|S|] là hậu tố của S bắt
 bắt đầu tại vị trí i.

15

 

Định nghĩa 3: (Cây
(Cây hậu tố tổng quát ) Cây hậu tố tổng quát là một cây hậu tố
được xây dựng cho 
cho tập các chuỗi Si. Mỗi nút lá lúc này nhận hai giá trị, một là
chuỗi (i); hai là vị trí bắt đầu (hậu tố) của chuỗi đó. 
đó. 
Để giải quyết bài toán xâu con chung của hai hay nhiều chuỗi chúng ta
cần mở rộng khái niệm cây hậu tố để chứa nhiều chuỗi khác nhau trong một
cấu trúc dữ liệu chung, ta sử dụng cây hậu tố tổng quát,
quát , ví dụ cây hậu tố tổng
quát T  cho hai chuỗi S1=TACTAG và S2=CACT .

 Hình 2.2. C ây
ây hậu tố tổng quát cho chuỗi S 1=TACTAG; S2 = CACT.

Độ sâu chuỗi của một nút v trong cây T là P(v), là tổng của tất cả độ dài cạnh
trên đường đi từ gốc đến nút v, đường đi chính là chuỗi nhãn của nút v.
Định nghĩa 4: ( Liên
 Liên kết hậu tố ):
): Cho x  biểu
 biểu diễn một chuỗi bất kỳ, trong đó
 x  biểu diễn ký tự đơn và    biểu diễn một chuỗi con (có thể rỗng). Xét nút

trong v với chuỗi nhãn x , nếu có một nút khác s(v) có nhãn là , một con trỏ
từ v đến s(v) được gọi là liên kết hậu tố (suffix link ).
). Trường hợp đặc biệt nếu

  rỗng thì  x  có liên kết hậu tố được trỏ đến gốc ( root ).

). Nút gốc không được
coi là nút trong và không có liên kết hậu tố nào bắt đầu từ nó. Ví dụ như hình
dưới đây, liên kết hậu tố được thể hiện
hiện  là đường nét gạch nối. 
nối. 

16


 

 Hình 2.3. C ây
ây hậu tố tổng quát và các liên kết .

2.3. Biểu diễn cây hậu tố tổng quát trong máy tính
Một cách hiệu quả để biểu diễn các cạnh 
cạnh giả sử là S[p...q] của cây hậu
tố thay vì biểu diễn tường minh nhãn cạnh của chúng, ta chỉ mô tả là một cặp
số nguyên ( p,q
 p,q). Do đó mỗi cạnh có thể lưu trữ với kích thước là hằng số, vì
vậy   không gian lưu trữ cây hậu tố là O(m). Cây hậu tố tổng quát có thể chứa
vậy
rất nhiều chuỗi 
chuỗi khác nhau nên mỗi cạnh khi lưu trữ cần lưu cả chỉ số của xâu
con nó biểu
biểu diễn. Ví dụ cây hậu tố tổng quát cho hai chuỗi S1 = TACTAG và
S2 = CACT  trong bộ nhớ như hình 2.4.

17

 

máyy tính.
 Hình 2.4. Biểu diễn cây hậu tố tổng quát trong má

Trên đây là một số khái niệm về cây hậu tố liên quan,
quan, phần tiếp theo
chúng tôi xin trình bày thuật toán dựng cây hậu tố tổng quát của Ukkone
Ukkonenn [6].

2.4. Thuật toán dựng cây hậu tố. 
 2.4.1. Dựng cây hậu tố ngầm định (implicit
(implicit suffix tree) 
Cây hậu tố ngầm định của chuỗi S là cây nhận được từ cây hậu tố của S 
sau các bước xử lý: 
lý: 
i) Xóa tất cả các ký tự kết thúc $ trong các nhãn  
ii) Xóa các cạnh không có nhãn (cạnh rỗng)  
iii) Xóa các nút có ít hơn 2 con 
Thuật toán: Gọi cây 
cây  T i là cây hậu tố ngầm định cho S[1..i]. Ý tưởng xây
m+1 trong m pha. Thêm ký tự 
dựng của thuật toán là cập nhất cây T  từ cây T 2 ,…T m+1
tự 
S[m+1]=$  thì việc mở rộng cuối cùng ta được cây hậu tố ngầm định chính là

cây hậu tố của S$. 
Đầu tiên ta có cây T 1 với một cạnh duy nhất chứa S1. Pha i+1 được chia
nhỏ thành i+1  bước

bước mở rộng trong đó ta thêm ký tự Si+1  vào hậu tố S[j..i] của
xâu S[1..i]. Tại bước mở rộng j, xét đường đi từ gốc có nhãn   = S[j..i] và thực
hiện một trong ba luật mở rộng  sau đây: 
đây: 
1)
1) Nếu
 Nếu   là nhãn của một nút lá: ký tự Si+1 được thêm vào cạnh nối với
18


 

nút lá đó. 
đó. 
2)
2) Nếu
 Nếu không có đường đi từ     bắt
bắt đầu bằng Si+1  nhưng có ít nhất một
đường đi nối tiếp   : trường hợp này ta thêm một cạnh có nhãn là Si+1,
nếu   kết thúc ở giữa một cạnh thì tạo một nút mới.
mới.  
3)  Nếu có đường đi nối tiếp     bắt đầu bằng Si+1: không làm gì và
chuyển sang bước tiếp theo. 
theo. 
Tại bước mở rộng i+1  của pha i+1,     là xâu rỗng, thuật toán đơn giản
thêm ký tự Si+1 bên
 bên dưới nút gốc (trừ khi nó
nó đã có).
Xét ví dụ trong hình 2.5
2.5 bốn hậu tố đầu tiên kết thúc

thúc ở nút lá
lá,, hậu tố cuối cùng
chỉ gồm ký tự  x  kết thúc bên trong mỗi 
mỗi   cạnh. Khi thêm ký tự thứ sáu b, bốn
hậu tố 
tố  đầu tiên được mở rộng bằng luật 1, hậu tố thứ năm sử dụng luật 2 và
với hậu tố thứ sáu là luật 3. 
3. 

(a)

(b)

 Hình 2.5. Cây hậu tố ngầm định cho xâu axabx trước (a) và sau (b) khi thêm ký tự  thứ sáu b.

Dế dàng thấy rằng ta có thể tìm thấy điểm kết thúc của mỗi hậu tố trong

i+1  hậu tố của xâu S[1..i]  bằng
bằng cách duyệt cây từ gốc với chi phí thời gian là
là  

O(||). Trong thuật toán Ukkonen, mỗi nút trong mới được tạo ra sẽ có một
liên kết hậu tố khi pha tiếp theo kết thúc. 
thúc.  Liên kết hậu tố có thể được sử dụng
dụ ng
để giảm độ phức tạp khi thao tác.
tác.
Đường đi có nhãn S[1..i]   chắc chắn phải kết thúc ở lá và
v à nó có đường
đi dài nhất trong cây T i. Khi xây dựng cây T i  ta lưu lại nút lá tương ứng với

19


 

toàn bộ
toàn
 bộ xâu đang xét S[1..i]. Bước bổ sung đầu tiên của pha i+1 lấy nút lá này
và áp dụng luật thứ nhất do đó chỉ cần thời gian hằng số [4].
Đặt S[1..i] = x  và (v, 1) là cạnh đến nút lá, nhãn của cạnh là , bước
mở rộng tiếp theo thuật toán cần tìm đường đi có nhãn là S[2..i] =  . Nếu
 Nếu v là
nút gốc, ta duyệt cây từ gốc theo thuật toán trước. Nếu v  không phải nút gốc
thì có liên kết hậu tố từ v đến nút s(v), ta bắt đầu duyệt cây từ nút s(v). Đường
đi từ vị trí hiện tại có nhãn  là đường đi từ gốc có nhãn  .
Tại bước mở rộng thứ  j  với  j > 2  ta cũng làm tương tự. Bắt đầu và kết
thúc của S[j-1..i]  là nhãn của một nút trong, khi đó ta có liên kết hậu tố của
nút này. Kể cả khi xâu S[j-1..i]  kết thúc ở một nút lá thì nút cha của nó hoặc
là một nút trong (do đó có liên kết hậu tố) hoặc là nút gốc. Vậy ta không bao
giờ phải đi ngược lên quá một cạnh. 
cạnh. 

 Hình 2.6. Bước mở rộng j > 1 trong pha i. Đi lên tối đa là cạnh từ cuối đường đi S[j-1..i]
đến nút v sau đó theo liên kết hậu tố đến s(v), đi xuống theo đường đi có nhãn    rồi áp
dụng luật bổ sung phù hợp để thêm hậu tố S[j..i+1].
S[j..i+1] . 

Việc tìm đường đi có nhãn   theo cách thông thường cần thời gian
O(||), do đường đi nhãn   chắc chắn tồn tại và không có hai cạnh nào cùng

xuất phát từ một đỉnh có nhãn bắt đầu 
đầu   cùng một ký tự nên ta có thể dựa vào
ký tự đầu nhãn và độ dài của cạnh để tìm ra điểm kết thúc của đường đi trong
thời gian tỉ lệ với số nút
n út trên đường đi.
đi.  
20


 

Gọi (v, s(v)) là một liên kết hậu tố, thì độ sâu nút của v  tối đa lớn hơn
độ sâu nút của s(v) một đơn vị. 
vị.  Với mỗi nút v  trên đường đi  x , có một nút
s(v)  trên đường đi  . Tuy nhiên, độ sâu của v  có thể lớn hơn, bằng hoặc nhỏ

hơn độ sâu của nút s(v) một đơn vị.
vị.
Mặc dù 
dù  đã
đã   được cải thiện tại 
tại  mỗi pha của 
của  thuật toán Ukkonen có thể
được thực hiện trong thời gian O(m). 
O(m).  Tuy nhiên đến đây chúng ta vẫn thấy
rằng độ phức tạp của nó 
nó  được thực hiện trong thời gian O(m2).
Để thuật toán dựng cây hậu tố ngầm định 
định   đạt được 
được  trong thời gian

tuyến tính 
tính chúng ta có một số nhận xét sau đây: 
đây: 
Nhận xét 1:
1: Luật mở rộng 3 
3 kết thúc mỗi pha [5].
 Nếu luật 3 được áp dụng nghĩa là đường đi có nhãn S[j..i]   chắc chắn
được nối tiếp bằng ký tự Si+1 nên tất cả các đường đi có nhãn S[k..i] với k > j.
Gọi  j* là chỉ số của bước mở rộng đầu tiên khi luật 3 được áp dụng. Theo đó 
đó 
ta không cần thực hiện các bước 
bước mở rộng k  với k > j* trong pha hiện
hiện tại. 
tại. 
Nhận xét 2:
2: Khi đã là nút lá thì luôn luôn là nút lá [5].
Rõ ràng trong 3 luật mở rộng không có luật nào cho phép thêm một nút
lá mới bên dưới một nút lá có nhãn  . Do đó khi một nút lá đã được tạo ra thì
nó sẽ luôn luôn là nút lá cho đến khi pha cuối cùng của thuật toán kết thúc. 
thúc.  
Với nhận xét trên gợi ý cách cài đặt hiệu quả thuật toán: thay vì cập
nhật nhãn của các nút lá một cách tường minh, ta gán nhãn cho các nút lá là
cặp ( p,
). Trong đó  p  là vị trí bắt đầu của xâu con và   là vị trí kết thúc của
 p, ).
xâu con trong S, thay thế cho vị trí cuối xâu đang xét. Như vậy trong pha i+1 
ta không cần thực hiện  ji bước
 bước mở rộng tường minh đầu tiên. 
tiên. Điểm mà ta thấy
 phù hợp với hậu duệ đầu tiên được gọi

gọi   là điểm kết thúc. Bằng cách xét các
điểm kết thúc, ta sẽ biết các điểm hoạt động sẽ được đi qua tiếp theo.
theo.

21


 

Thuật toán Ukkonen dựng cây hậu tố ngầm định: 
input: Chuỗi S. 
S. 
Dựng cây hậu tố ngầm định T 1. // T 1 có một cạnh đơn nhãn là S[1]. 
for i = 1 to m-1 do
Giai đoạn i+1. 
// Giai
// 

begin

 // Cập
 // Cập nhật T i (với tất cả các hậu tố của S[1..i] đến
T ii+1
+1 với tất các hậu tố S[1..i+1]) 

for j = 1 to i+1 do
begin

//  Mở
 Mở rộng j j 

Trong cây hiện tại, tìm vị trí kết thúc của đường đi từ 
từ  
gốc có nhãn t[j..i]. Để
Để  có thể, mở rộng đường đi bằng 
bằng  
cách thêm ký tự t[i+1] , để có xâu t[j..i+1] trong cây.
end;
end;

 Như vậy, sử dụng liên kết hậu tố và các nhận xét trên, giải thuật Ukkonen có
thể dựng cây hậu tố ngầm định trong thời gian O(m)
O(m)..
Trong mỗi pha i  của thuật toán, ta chỉ cần thực hiện các bước mở rộng
tường minh từ ji-1 đến j*. Do bước mở rộng cuối cùng theo luật 1 hoặc 2 được
áp dụng chính là một bước trước khi luật 3 lần đầu tiên được áp dụng nên ta
có  j = j*-1.  Như vậy
vậ y số bước mở rộ
rộng
ng được thực hiện có thể tính theo ccông
ông
i

thức: 

m

i 2

(  ji   ji 1  1)  1   j m   j1  m  2m .

Vậy thời gian thực hiện của thuật

toán là O(m). Như hình minh họa quá trình thực hiện của thuật toán dưới đây,
mỗi dòng là một giai đoạn trong thuật toán, mỗi số là   một bước mở rộng
tường minh được thực hiện. 
hiện. 

22


 

Dưới đây là hình ảnh minh họa quá trình thực hiện của thuật toán:
toán:  

 Hình 2.7. Quá trình thực hiện của thuật toán  

Cây hậu tố ngầm định cuối cùng T m được chuyển thành cây hậu tố thực
sự trong thời gian O(m). Ta chỉ việc thêm ký tự $ vào cuối chuỗi 
chuỗi   S và thực
hiện thuật toán, kết quả là một cây hậu tố ngầm định của chuỗi mà không có
hậu tố nào là tiền tố của hậu tố khác.
khác.
 2.4.2 . Dựng cây hậu tố tổng quát

Áp dụng 
dụng thuật toán Ukkonen
Ukkonen như đã trình bày 
bày ta dễ dàng dựng cây hậu

tố tổng quát trong thời gian O( n) với n là tổng độ dài các chuỗi. 
chuỗi. 
Đầu tiên ta dựng cây hậu tố thông thường cho xâu S1. Với các xâu S2,
S3 , .. , S K  trước tiên ta tìm tiền tố dài nhất Sk [1..i] đã tồn tại trong cây. Ta thực

hiện các giai đoạn i+1, i+2, ... mk   của thuật toán để mở rộng cây hậu tố tổng
quát cho toàn bộ xâu. 
xâu. 
Việc tìm tiền tố dài nhất đã có trong cây đồng nghĩa với việc tìm đường
đi dài nhất trong cây có nhãn Sk [1..i]   bằng
bằng cách duyệt từng ký tự trên đường
đi từ gốc. Có hai trường hợp xảy ra: 
ra: 
1. Đường đi kết thúc ở nút v  (có thể là nút gốc): thêm nút con mới nối
với v bằng
 bằng cạnh có nhãn là Sk [i+1]. 
2. Đường đi kết thúc giữa một cạnh: chia đôi cạnh tại điểm đường đi
kết thúc 
thúc và tạo ra nút mới v. Tạo nút con của v nối với nó bằng cạnh Sk[i+1].
Sau khi thực hiện xong bước mở rộng đầu tiên của giai đoạn i+1  đã
hoàn thành, ta có thể đi theo nút cha của v, theo liên kết hậu tố để thực hiện

23


 

các bước tiếp theo. Lưu ý trong trường hợp 
hợp  2 ta cũng cần đảm bảo liên kết
hậu tố của v sẽ được thiết lập trong bước mở rộng tiếp theo.

theo.  

2.5. Ứng dụng cây hậu tố.
Cây hậu tố thường được sử dụng trong nhiều 
nhiều  ứng dụng 
dụng  khác nhau, đặc
 biệt trong lĩnh vực Tin sinh học 
học như:
như:  tìm kiếm các mẫu trình tự DNA
DNA;; sắp xếp
các chuỗi gien 
gien  hay Protein (mà có thể được xem như chuỗi dài các ký tự);
tự) ;
liệu ... Cây
liệu 
trong
trong nén dữ liệu...
Cây hậu tố cũng được sử dụng trong phân tích cụm dữ liệu 
 biểu hiện gien [17], để tìm kiếm các bicluster trong dữ liệu biểu hiện gien 
gien 
(chúng tôi sẽ trình bày chi tiết ở phần chương 3).
3) .
Với nhiều ứng dụng và thường cung cấp
c ấp giải pháp trong thời gian tuyến
tuyến
tính,, dưới đây là một số ứng dụng của cây hậu tố
tính
tố::

  Chuỗi con chung dài nhất (Longest Common Substring): 

Chuỗi con của một chuỗi 
chuỗi S là chuỗi
chuỗi  thu được bằng cách chọn ra một số ký
tự liên tục trong S. Nói cách khác. Giả sử S=S1S2...Sm, một chuỗi 
chuỗi 
 Z=Si+1Si+2...Si+t  với i   0 và i+t   m là chuỗi
chuỗi  con của S. Ví dụ: chuỗi Z=bcd là

chuỗi con của chuỗi S=aabc bcd abdab.
abdab.
Cho hai chuỗi 
chuỗi  S và T , ta nói  Z   là chuỗi 
chuỗi  con chung của S và T   nếu  Z  
đồng thời là chuỗi 
chuỗi con của cả hai. 
hai. Ví dụ: S=abcdefg và T =bccdegf
=bccdegf có:

 
 
 
 

Z = bc là chuỗi con chung.
Chuỗi  efg không phải chuỗi con chung.
Chuỗi
Z = bc có độ dài 2 không phải là chuỗi 
chuỗi con chung dài nhất. 
nhất. 
Chuỗi  cde là chuỗi 

Chuỗi
chuỗi con dài nhất có độ dài 3. 
3. 

Trong
Tr
ong cây hậu tố tổng quát của chuỗi 
chuỗi  S và T , đánh dấu các nút trong
 bằng 1 (hoặc 2) nếu cây con tại nút đó chứa nút lá có nhãn 1 (hoặc 2). Nhãn
của đường đi từ gốc đến nút 
nút được đánh dấu cả hai là một chuỗi
chuỗi  con chung của
hai chuỗi
chuỗi. Nút có nhãn dài nhất hay độ sâu đường đi lớn nhất cho ta lời giải
của bài toán. 
toán. 
24


 

  Chuỗi con chung có chiều dài k (Common substrings of length k): 
Cho m chuỗi
chuỗi  S1 , S2 , ..., Sm, với mỗi giá trị k  từ 2 đến m, gọi là l(k), là độ dài
của chuỗi 
chuỗi con chung dài nhất của ít nhất k  chuỗi
chuỗi  trong tập đã cho.
Ví dụ. 
dụ. Xác định chuỗi con chung dài nhất của ít nhất hai chuỗi:
chuỗi: Cho tập

gồm m chuỗi
chuỗi,, l(k) (2  k  m) là chiều dài của chuỗi 
chuỗi con chung dài nhất tối
thiểu là k  của m chuỗi. Ví dụ cho các chuỗi sau: {sanddollar, sandlot, handler,
grand, pantry} ta có:
chuỗi  
2
4
sand
3
3
and
4
3
and
5
2
an
 Như vậy vấn đề chuỗi 
chuỗi con chung dài nhất của ít nhất hai chuỗi 
chuỗi có thể được
thực hiện như sau:
 k

l(k)

- Input: Các chuỗi 
chuỗi S1 , …, S m (tổng chiều dài n)
- Output: l(k) (2  k  m) - các chuỗi
chuỗi  con và độ dài của nó. 

nó. 

Xây dựng cây hậu tố tổng quát cho m chuỗi, mỗi chuỗi 
chuỗi duy nhất có một
ký tự kết thúc.
thúc.
Kết luận 
Trong chương này,
này, chúng tôi đã trình bày tổng quan về các chức năng
của cây hậu tố, một số kiến thức liên quan đến việc tìm kiếm chuỗi.
chuỗi . Những
kiến thức quan trọng này sẽ làm nền tảng cho các kết quả sẽ trình bày trong
các chương tiếp theo của luận văn. 
văn. 

25