- 48 -
MỘT SỐ PHƯƠNG PHÁP TRONG
SẮP XẾP CHUỖI SINH HỌC



Sinh viên: Vũ Hồng Khiêm
MSV: 0121955
Email:

Người hướng dẫn: ThS. Trần Thị Minh Châu
NCS. Lê Sĩ Vinh

1. Giới thiệu
Thế kỉ 21 sẽ là thế kỉ của Tin học và Sinh
học. Hai ngành khoa học đang ngày càng khẳng
định vai trò khoa học mũi nhọn của mình trong
sự phát triển chung của nhân loại.Trên thực tế,
sự ra đời của Tin sinh học, một ngành mới kết
hợp giữa Tin Học và Sinh học, như là một qui
luật tất yếu của sự phát triển. Tin Sinh Học đã
được sự hưởng ứng tham gia củ
a đông đảo
những nhà nghiên cứu trên toàn thế giới. Bản
thân tôi, một người lính mới, kiến thức và kinh
nghiệm chưa nhiều, cũng mong muốn sẽ được
đóng góp một phần nhỏ bé nào đó trong công
cuộc khai phá miền đất mới mẻ này.
Một trong những bài toán điển hình trong
Tin Sinh Học là bài toán sắp xếp các chuỗi sinh
học thẳng hàng. Sẵp xếp chuỗi sinh học không

những cho chúng ta thấy được m
ối quan hệ tiến
hoá giữa các loài sinh vật mà còn được áp dụng
trong một số bài toán khác như chuẩn đoán cấu
trúc bậc hai của protein…
2. Khái niệm/kiến thức cơ bản
Một trở ngại đầu tiên đối với người làm Tin
Sinh Học đó là phải hiểu rõ về các khái niệm
được coi là cốt tử trong sinh học phân tử, một
nhánh của Sinh học nghiên cứu vật chất trong
thế giới vi mô. Việc tìm hiểu các khái niệm này
phục vụ cho nghiên cứu Tin Sinh Học chủ yếu
tập chung vào cấu trúc không gian của chúng.
Trong khoá luận của mình, tôi cũng đã tập
chung nêu ra các khái niệm về
DNA
,
RNA
, và
protein, đây là những khái niệm quan trọng
nhất cần phải xác định, phần lớn các vấn đề
trong Tin sinh học chỉ tập chung quanh các khái
niệm trên.
Chuỗi sinh học
thực chất là biểu diễn tuyến
tính của các đại phân tử sinh học DNA, RNA
hay protein. Chúng được biểu diễn bằng một
dãy liên tiếp có thứ tự các chữ cái đại diện. Ví
dụ về các chuỗi sinh học biểu diễn 1 đ
oạn trong

chuỗi axid amin của protein
”
RDILSVKNAGI”.
Bài toán sắp xếp chuỗi
sinh học thực chất là tìm một giả thuyết phù
hợp nhất về mối quan hệ tiến hoá của hai hay
nhiều chuỗi sinh học tương ứng. Do bản chất số
tự nhiên của các chuỗi sinh học cũng như kích
thước các chuỗi có thể lên tới hàng triệu đơn vị,
chính vì vậy việc thực hiện sắp xếp bằng các
phương pháp thông thường là hoàn toàn không
th
ể, chúng ta cần phải áp dụng những thuật toán
cũng như kĩ thuật trong Tin học để có thể giảm
được lượng tính toán cần thiết. Cụ thể trong
khoá luận của tôi đã sử dụng các phương pháp
qui hoạch động kết hợp với phương pháp chia
để trị nhằm phục đích đưa ra những phương án
tối ưu nhất có thể.
3. Sắp xếp 2 hay nhiều chuỗi sinh học
3.1. Sắp xếp 2 chuỗi
Sắp xếp 2 chuỗi là bài toán hạt nhân, quan
trọng nhất trong sắp xếp chuỗi sinh học. Đặc tả
bài toán có dạng như sau:
Một sắp xếp thực hiện trên 2 chuỗi là việc
bố trí thêm các khoảng trống (biểu diễn bởi dấu
“-“) vào các vị trí nhất định nào đó trên mỗi
chuỗi sao cho thoả mãn 2 điều kiện:
 Thứ tự các phần tử trên 2 chuỗi không
thay đổi.

 2 chuỗ
i đích thể hiện được “mức độ
tương đồng” lớn nhất.
Mức độ tương đồng được phản ánh thông
qua số lượng các cặp giống nhau ở cùng 1 vị trí
nhất định trên 2 chuỗi. Nếu sắp xếp đưa ra được
nhiều cặp giống nhau nhất thì sắp xếp đó là tối
ưu mà ta chúng ta phải sử dụng thuật toán để
tìm ra nó. Do các đặc thù về tiêu chuẩ
n của sắp
xếp phải thỏa mãn, người ta cũng phân sắp xếp
chuỗi thành 2 loại khác nhau.
Để có thể giải quyết bài toán sắp xếp chuỗi
sinh học, trước hết tôi áp dụng phương pháp mô
hình hóa để đưa vấn đề về việc tìm đường đi
trong trong đồ thị định hướng. Sau đó sẽ áp
dụng phương pháp qui hoạch động để giải
quyết bài toán tìm đường đi nói trên. Nộ
i dung
thuật toán có thể được mô tả theo các bước sau:
- 49 -
 Khởi tạo ma trận tìm đường đi tối
ưu.
 Dựa trên các qui tắc gán trọng
số/trừ điểm khoảng trắng ta sẽ tính
toán các điểm còn lại trong ma trận
cho tới khi lấp đầy ma trận.
 Tìm lại đường đi ngắn nhất bằng kĩ
thuật back-tracking.
Vấn đề quan trọng nhất đối với bài toán sắp

xếp 2 chuỗi đó là cách đ
ánh giá của chúng ta
đối với các tham số cho hàm trừ điểm các
khoảng trống này, một công việc mang nhiều ý
nghĩa sinh học xong lại ảnh hưởng đến kết quả.
Ngoài ra, việc sử dụng ma trận trọng số cũng có
ý nghĩa rất quan trọng đến việc kết quả thực thi
của bài toán.
3.2. Bài toán sắp xếp nhiều chuỗi
Sắp xếp nhiều chuỗi là sắp xếp chuỗi áp
dụng cho nhiều chuỗi sinh học khác nhau, nó
có rất nhiều ứng dụng trong việc xây dựng cây
phả hệ giữa nhiều loài sinh vật và trong vấn đề
chuẩn đoán cấu trúc bậc cao của protein. Về
mặt lý thuyết ta hoàn toàn có thể áp dụng kĩ
thuật lập trình động như đã làm với trường hợp
2 chuỗi. Tuy vậy, phương pháp trên không thể

đáp ứng được yêu cầu về thời gian thực thi,
ngay cả khi số lượng chuỗi cần sắp xếp chỉ có 3
hay 4 chuỗi. Chính vì vậy, người ta đã phải áp
dụng nhiều kĩ thuật khác nhau nhằm tối ưu hóa
thời gian tính toán. Trong phần này, tôi đã tìm
hiểu cách tiếp cập phả hệ, cụ thể là sử dụng
phương pháp ClustalW, đây là một phương
pháp được sử dụng rộ
ng rãi và có thể nói là
cách tiếp cận hiệu quả nhất cho tới thời điểm
này. ClustalW đã và đang được cải tiến hơn nữa
bởi rất nhiều nhóm nghiên cứu khác nhau.

Nội dung cơ bản của cách tiếp cận phả hệ đó
là việc xây dựng cây phát sinh loài, hay còn gọi
là cây chỉ dẫn. Cây này mô tả một cách trực
quan mối quan hệ tiến hóa giữa các chuỗi được
sắp xếp. Sau khi
đã có cây phát sinh loài, sắp
xếp đa chuỗi được xây dựng dựa trên việc
nhóm các chuỗi theo thứ tự độ tương đồng lớn
nhất tại thời điểm đó. Như vậy, các chuỗi sẽ
đựợc lần lượt thêm vào sắp xếp cho đến khi kết
thúc quá trình.
4. Kết luận và kết quả thu được
Qua thời gian nghiên cứu của mình, tôi cũng
đã học hỏi được rất nhiều điều lý thú từ lĩnh
vực khoa học mới mẻ này, đặc biệt là cách thức
áp dụng các thuật toán Tin học vào việc giải
quyết một vấn đề thực tế trong các lĩnh vực
khác. Tôi đã nghiên cứu và cài đặt thành công
thuật toán sắp xếp loại 1 áp dụng cho 2 chuỗi
sinh học khác nhau. Kết quả thu được có
độ
chính xác cao và có thể áp dụng cho nhiều bài
toán nghiên cứu về sau.
Đối với bài toán sắp xếp nhiều chuỗi, tôi đã
tham khảo và làm thực nghiệm với phần mềm
ClustalW do Viện nghiên cứu Tin Sinh Học
Châu Âu phát triển. Kết quả thực nghiệm trên
những bộ dữ liệu rất lớn, với lượng tính toán
khổng lồ đã chứng minh tính ưu việt cao của
phương pháp này.

5. Kết luận
Trong thời gian làm khóa luận này, tôi tập
chung phần lớn thời gian vào tìm hiểu các vấn
đề liên quan đến kĩ thuật tối ưu hóa trong thuật
toán sắp xếp áp dụng cho hai chuỗi. Đây cũng
là vấn đề có vai trò rất quan trọng bởi nó là một
thành phần được sử dụng lại nhiều lần trong bài
toán sắp xếp với nhiều chuỗi. Trên thực tế, có
rất nhiều cách tiếp cận giải quyết khác nhau
đối
với sắp xếp nhiều chuỗi. Việc tìm ra một cách
giải quyết độc lập và hiểu quả là một hướng
hoàn toàn khả thi cao. Đây sẽ là một hướng đi
mà tôi chọn trong thời gian nghiên cứu tiếp
theo.
Tuy kết quả chưa đạt những thành công lớn,
xong tôi cũng đã có dịp tìm hiểu những kiến
thức về Sinh học phân tử, những thứ sẽ cần
thi
ết cho tôi có thể thuận lợi hơn khi áp dụng
các kiến thức trong Tin học vào Sinh Học.
Tài liệu tham khảo
[1] Arthur M. Lesk, “Introduction to
Bioinformatics” University of Cambridge
[2] Julie D.Thompson and Desmond
G.Higgins+ and Toby J.Gibson,
“CLUSTALW: improving the sensitivity of
progressive multiple sequence alignment
through sequence weighting, position-
specific gap penalties and weight

matrix choice”.