mở đầu cho kỷ nguyên chinh phục cơ chế di truyền trong sinh vật phù hợp với học thuyết Darwin. Hơn 60 năm qua, sinh học phân tử nói riêng và công nghệ sinh học nói chung phát triển mạnh mẽ, trở nên lĩnh vực nghiên cứu và ứng dụng hấp dẫn, tạo ra cuộc cách mạng đối với sự hiểu biết của chúng ta về chức năng của tế bào, mở ra con đường để phát hiện ra cơ chế sinh học phức tạp và sự liên quan của chúng đến bệnh tật và sự phát triển của cơ thể sống. Trong đó, hiểu biết về quá trình tổng hợp protein đặt nền tảng cho sinh học phân tử. Quá trình tổng hợp protein DNA mang thông tin di truyền và điều khiển tổng hợp protein của sinh vật, còn protein quyết định đặc tính, chức năng và quá trình phát triển của cơ 16 thể sống [Lê Sỹ Vinh, 2014].
DNA là chuỗi xoắn kép được cấu tạo từ 4 loại nucleotide: Adenine, Cytosine, Guanine và Thymine, chúng được ký hiệu tương ứng là A, C, G và T. Một đoạn của chuỗi DNA mang thông tin cần thiết để tạo nên protein gọi là một đoạn gen hay gọn hơn là một gen. Mỗi sinh vật có nhiều gen, chẳng hạn con người có khoảng 25 nghìn gen khác nhau. Quá trình tổng hợp protein từ thông tin ở DNA gồm 2 giai đoạn: phiên mã và dịch mã [Lê Sỹ Vinh, 2014] như được minh họa trong hình 1.
Trong giai đoạn phiên mã, đoạn gen mang thông tin hướng dẫn tổng hợp protein được chuyển sang đoạn RNA có nội dung tương tự đoạn gen nhờ thay Thymine bởi Uracil, được ký hiệu là U. Trong giai đoạn dịch mã, đoạn RNA được dịch mã để tạo nên chuỗi các amino acid và chuỗi này được cuộn gấp (folded) tạo thành protein. Các protein được cấu tạo từ 20 loại amino acid. Quá trình tổng hợp protein Trong quá trình tiến hóa, các gen/RNA/protein được di truyền và có thể biến đổi nhờ các biến dị của các nucleotide/amino acid thành phần dưới dạng xóa/chèn/ thay thế một nucleotide bằng một nucleotide khác.
Tùy theo việc đặc điểm sinh học của sinh vật do protein quy định có phù hợp với môi trường hay không mà biến dị được củng cố tồn tại/ phát triển hoặc tiếp tục biến đổi bởi 17 biến dị khác nếu không triệt tiêu cùng các cá thể mang nó. Sự biến đổi theo thời gian của các bộ gen tạo nên quá trình tiến hóa của các loài sinh vật. Nhận thức này đặt cơ sở cho các nghiên cứu và ứng dụng trong sinh học phân tử và tin-sinh học. Sinh học phân tử và phân tích các trình tự trong tin sinh học Thoạt tiên, các nghiên cứu sinh học phân tử được thực hiện và kiểm chứng bằng thực nghiệm trong các phòng thí nghiệm.
Tuy nhiên việc nghiên cứu trong phòng thí nghiệm đòi hỏi nhiều thời gian và chi phí cao nên kìm hãm tiến trình nghiên cứu. Các tri thức về quá trình tổng hợp protein và cấu trúc của quá trình tổng hợp protein cùng sự phát triển, ứng dụng rộng rãi của công nghệ thông tin cho phép thực hiện các phân tích Tin-Sinh để trợ giúp các dự đoán và nghiên cứu trong sinh học phân tử. Các bài toán và kỹ thuật dóng hàng trình tự [Lê Sỹ Vinh, 2014] Dựa trên sự phân tích tương đồng/dị biệt cấu trúc của các trình tự DNA và protein, người ta có được các nhận biết về quan hệ giữa các loài sinh vật và các cá thể, dự đoán các đặc tính sinh học từ các loài mới dựa trên đặc tính của các loài đã nghiên cứu kỹ gần với nó. Như đã nói ở trên, trong quá trình tiến hóa của các loài, các gen/RNA/protein được di truyền và có thể biến đổi nhờ các biến dị của các nucleotide/amino acid thành phần dưới dạng xóa/chèn/ thay thế một nucleotide bằng một nucleotide khác.
Sau khi giải trình tự gen/RNA/protein người ta sử dụng các kỹ thuật học máy để phân tích chúng, bắt đầu từ các bài toán đơn giản như dóng hàng 2 hoặc nhiều trình tự, xác định trình tự con đến các bài toán phức tạp hơn như: xây dựng cây phân loài, tìm kiếm motif và vị trí của chúng (xác định miền điều hòa gen), suy diễn haplotype, dự đoán biến đổi amino acid, v. 18 Các bài toán phức tạp này được mô hình hóa dựa trên các nhận xét của các nhà sinh học. Nhiều bài toán trong chúng là những bài toán tối ưu tổ hợp xử lý dữ liệu tuần tự và thuộc loại NP-khó. Để dễ hình dung cách đặt bài toán và sử dụng, ta trở lại với bài toán tìm kếm motif và làm quen với bài toán xây dựng cây phân loài.
Bài toán tìm kiếm DNA motif và mô hình hóa tổng quát DNA motif là một đoạn ngắn trong DNA, chúng thường có chức năng đặc biệt đối với các gen trong bộ gen, chẳng hạn, điều hòa gen [Hoang X. Huan, Tuyet, Ha, & Hung, 2015]. Đoạn này thường lặp đi lặp lại trong bộ gen. Các thuật toán tin sinh sẽ tìm ra các đoạn nghi ngờ là motif và vị trí của chúng trên các bộ gen để các nhà sinh vật kiểm tra lại bằng thực nghiệm thay vì tìm kiếm mù để làm thực nghiệm.
Bài toán được mô hình hóa tổng quát như sau [Hoang X. Huan et al., SN } các trình tự độ dài m trên bộ chữ cái Σ. Với giá trị l < m cho trước , cần tìm trình tự x = {𝑥1, 𝑥2 , .𝑥𝑙 } trên bộ chữ cái Σ với độ dài l và tập xâu con M = {𝑚1 , 𝑚2 ,., 𝑚𝑁 } có cùng độ dài l được lấy ra từ các chuỗi Si tương ứng sao cho nó tốt nhất theo một tiêu chuẩn định trước nào đó. Tiêu chuẩn đồng thuận xác định bởi tổng khoảng cách Hamming tới các xâu trong tập là nhỏ nhất.
Tuy nhiên người ta cũng có thể định nghĩa motif là xác định hàm mục tiêu khác theo mục đích của nhà sinh học, chẳng hạn số trình tự trong tập S có khoảng cách Hamming tới x là nhỏ nhất. Với tiêu chuẩn được chọn, các thuật toán đề xuất sẽ cho ta các motif và vị trí của chúng trên các trình tự để nhà sinh học xem xét quyết định làm thực nghiệm kiểm định hay không (trợ giúp quyết định). 19 Bài toán xây dựng cây phân loài [Lê Sỹ Vinh, 2014] Trong bài toán này, dựa trên phân tích tính tương đồng thể hiện qua dữ liệu sinh học phân tử (DNA/protein) của các loài, người ta dự đoán quan hệ giữa các loài và xây dựng cây phân loài. Hai loài có hệ gen và protein càng gần nhau thì quan hệ tiến hóa càng gần nhau.
Dựa trên phân tích quan hệ như vậy, người ta xây dựng cây nhị phân không gốc với cấu trúc như sau: Mỗi nút là ứng với một loài sinh vật hiện thời Mỗi nút trong ứng với một loài sinh vật tổ tiên mà thông thường ta không có thông tin về loài này. Mỗi cạnh của cây nối nút của cây ứng với hai loài sinh vật có quan hệ tiến hóa trực tiếp. Khoảng cách nối hai nút ứng với hai loài trên cây cho biết khoảng cách tiến hóa giữa chúng Các quan hệ trên cây xây dựng được cho ta kết qủa dự đoán dựa trên kỹ thuật phân tích hiện có, khi có thêm kỹ thuật mới để xét tính tương đồng, chẳng hạn, tính tương tự mạng protein (sẽ đề cập ở dưới) ta sẽ điều chỉnh cho chính xác hơn. Mặc dù các cây được xây dựng như thế không hoàn toàn chính xác với tiến hóa thực nhưng nó rất hữu ích cho các nhà sinh học khi nghiên cứu các loài sinh vật.
Nhờ nó mà các nhà sinh học có thể dự đoán một số đặc điểm sinh học có tính di truyền từ các đặc điểm của những loài gần gũi với nó. Việc nghiên cứu tính tương đồng các trình tự DNA/Protein không đủ thông tin cho nghiên cứu chức năng và đặc tính y học nên người ta quan tâm đến các bài toán phân tích dữ liệu 3 chiều. Chẳng hạn, người ta nhận thấy trong quá trình tổng hợp protein, nếu các amino acid được cuộn gấp sai sẽ gây nên các bệnh di truyền. Nếu ta dự báo và phát hiện được lỗi cuộn gấp thì có thể phát hiện bệnh và tìm được phương thức điều trị.
Để phát triển nghiên cứu, người ta đã xây dựng các CSDL không gian và các mạng sinh học. Các mạng sinh học Dóng hàng các chuỗi thuộc hệ gen đã tăng cường kiến thức y sinh học nhờ phát hiện các vùng trình tự có sự tương đồng giữa các gen ở các loài khác nhau, các vùng đó có khả năng phản ánh các mối quan hệ chức năng và tiến hóa giữa các trình tự [Alföldi & Lindblad-Toh, 2013; Altschul, Gish, Miller, & Lipman, 1990; Biesecker et al., 2009; Tsai, Iafrate, & Joung, 2014]. Tuy nhiên, các gen hoặc các sản phẩm protein của chúng không hoạt động một cách độc lập mà chúng thực hiện các quá trình tế bào bằng cách tương tác với nhau. Các tương tác này được mô hình hóa bởi mạng sinh học, chẳng hạn như: mạng điều hòa gen, mạng trao đổi chất, mạng tương tác protein-protein (protein-protein interactive: PPI), mạng các vị trí liên kết protein.
Không giống như các nghiên cứu về các chuỗi gen, nghiên cứu mạng sinh học cho phép hiểu được các quá trình tế bào phức tạp phát sinh từ các hoạt động chung của các phân tử sinh học. Những tiến bộ trong công nghệ sinh học hiện thời cung cấp nhiều dữ liệu cho phép ta nghiên cứu sâu hơn về các mạng sinh học và cho ta nhiều tri thức quý giá. Chẳng hạn, việc dóng hàng mạng sinh học nhằm tìm ánh xạ tương ứng đủ tốt giữa các nút mạng của các loài khác nhau cho phép xác định các vùng mạng có sự tương đồng về kiểu cấu trúc tô pô và cấu trúc trình tự, nhờ đó có thể chuyển một cách hiệu quả các kiến thức về chức năng của tế bào từ các loài đã được nghiên cứu tốt sang những loài chưa được nghiên cứu nhiều hoặc khó làm thực nghiệm. Bởi vì việc nghiên cứu thực nghiệm trên con người gặp nhiều khó khăn bởi các rào cản đạo đức và pháp luật, nhờ dóng hàng mạng mà người ta có thể chuyển các tri thức đã biết từ nấm men (Saccharomyces cerevisiae), ruồi giấm (Drosophila melanogaster), hoặc sâu (Caenorhabditis elegans) sang tri thức của con người dựa trên phát hiện các vùng mạng được bảo tồn [Clark & Kalita, 2014; Malod-Dognin & Pržulj, 2014; R.
21 Luận án này tập trung nghiên cứu hai bài toán thời sự: dóng hàng nhiều mạng các vị trí liên kết protein và dóng hàng toàn cục hai mạng tương tác protein-protein (về sau sẽ gọi gọn là mạng tương tác protein). Bài toán dóng hàng nhiều mạng các vị trí liên kết protein.