Một phương pháp cải tiến cho bài toán xác định các gen liên quan đến bệnh

Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR'9)”; Cần Thơ, ngày 4-5/8/2016 DOI: 10.15625/vap.2016.00051 MỘT PHƯƠNG PHÁP CẢI TIẾN CHO BÀI TOÁN XÁC ĐỊNH CÁC GEN LIÊN QUAN ĐẾN BỆNH Nguyễn Đại Phong1, Đặng Vũ Tùng2, Lê Đức Hậu3, Từ Minh Phƣơng4 1 Viện Công nghệ thông tin và Truyền thông, Trƣờng Đại học Bách Khoa Hà Nội 2 Trung tâm Tin học, Học viện Thanh thiếu niên Việt Nam 3 Trung tâm Tin học, Đại học Thủy Lợi 4 Khoa Công nghệ thông tin, Học viện Công nghệ Bƣu chính viễn thông phongnd.hust@gmail.com, tung_dv@yahoo.com, hauldhut@gmail.com, phuongtm@ptit.edu.vn TÓM TẮT — Xác định gen gây bệnh thường bắt đầu việc phân hạng các gen ứng viên theo mức độ liên quan đến bệnh. Việc làm này nhằm mục đích thu hẹp tập gen liên quan đến bệnh cần xác định bởi các thực nghiệm y sinh chuyên sâu. Hiện nay, có rất nhiều phương pháp khác nhau được đề xuất để phân hạng các gen ứng viên dựa trên mối quan hệ giữa các protein trong mạng tương tác gen/protein. Trong đó, hầu hết các phương pháp đều dựa trên giả thiết “mô đun bệnh”, tức là các gen liên quan đến cùng một bệnh có xu hướng nằm kề nhau trên các mạng tương tác. Các phương pháp này có xu hướng ưu tiên những gen ứng viên gần với gen gây bệnh đã biết trên mạng tương tác. Nhưng trong quá trình thực nghiệm, chúng tôi nhận thấy với nhiều bệnh, các gen liên quan đã biết cũng không hoàn toàn tạo thành một mô đun mà thậm chí chúng còn cách nhau rất xa trên mạng tương tác. Do đó, các phương pháp phân hạng hiện có không còn đạt hiệu quả cao. Để giải quyết vấn đề này, chúng tôi đề xuất một phương thức cải tiến mới nhằm mục đích ưu tiên cho các gen liên quan đến những bệnh có tính chất trên bằng cách tăng cường trọng số liên kết cho các gen ở xa các gen gây bệnh đã biết. Chúng tôi đã kiểm chứng hiệu quả phân hạng của phương pháp này với 148 bệnh trên mạng tương tác protein của người và so sánh hiệu quả phân hạng của phương pháp đề xuất với các phương pháp nổi trội hiện có như bước ngẫu nhiên có quay lại (RWR) và dựa trên xác suất liên kết (ERIN). Kết quả thực nghiệm đã chỉ ra rằng phương pháp của chúng tôi đạt độ chính xác là 95.3%, tốt hơn RWR (93.4%) và ERIN (89.8%). Thêm vào đó, sử dụng phương pháp của mình, chúng tôi đã xác định được một số gen mới liên quan đến bệnh ung thư tuyến tiền liệt. Từ khóa — Disease genes prioritization, protein interaction network, random walk with restart algorithm, prostate cancer. I. GIỚI THIỆU Xác định các gen mới có liên quan đến bệnh là một bài toán quan trọng trong nghiên cứu y sinh. Đây có thể coi là bƣớc khởi đầu trong việc tìm ra phƣơng pháp điều trị cho các bệnh phát sinh do yếu tố di truyền [1-3]. Trong giai đoạn trƣớc đây, việc xác định gen gây bệnh đƣợc thực hiện chủ yếu bằng thực nghiệm sinh học để xác định các vùng nhiễm sắc thể khả nghi liên quan bệnh cần nghiên cứu [4, 5]. Tuy nhiên, những vùng nhiễm sắc thể này thƣờng chứa hàng trăm gen ứng viên, trong khi chỉ có một số ít các gen thực sự liên quan đến bệnh [6]. Để xác định đƣợc chính xác các gen thực sự liên quan đến bệnh cần nghiên cứu, các nhà y sinh học phải tiến hành các thí nghiệm cho từng gen trong danh sách gen ứng viên thu đƣợc. Đây là công việc rất tốn kém về thời gian và kinh phí. Thách thức này hiện nay một phần đã đƣợc giải quyết bằng phƣơng pháp phân hạng gen ứng viên liên quan đến bệnh trong Tin sinh học và nó đã trở thành trọng tâm trong lĩnh vực di truyền học. Các phƣơng pháp phân hạng gen gây bệnh dựa trên mạng thƣờng căn cứ vào nguyên lý “mô đun bệnh” (nghĩa là, các gen/protein liên quan đến cùng một bệnh hoặc các bệnh tƣơng tự nhau có xu hƣớng nằm kề nhau trong các mạng tƣơng tác [5]) để tính toán độ tƣơng tự tƣơng giữa các gen ứng viên và các gen gây bệnh đã biết. Có rất nhiều phƣơng pháp dựa trên mạng đã đƣợc đề xuất cho bài toán này nhƣ: dựa trên các láng giềng gần nhất, dựa trên các cụm trên mạng. Ngoài ra, các thuật toán ph biến trong phân tích mạng xã hội và mạng Web dùng để đánh giá tầm quan trọng tƣơng đối của nút nhƣ: HITS with priors, PageRank with priors, K-step Markov [7], RL_Rank [8] và ERIN [9] cũng đã đƣợc sử dụng cho bài toán phân hạng các gen ứng viên trên các mạng tƣơng tác gen/protein. Trong số các phƣơng pháp phân hạng gen dựa trên mạng, phƣơng pháp sử dụng thuật toán bƣớc ngẫu nhiên có quay lại RWR [10- 12] đƣợc áp dụng ph biến hơn các phƣơng pháp khác vì thuật toán này xem xét toàn bộ các liên kết giữa các gen gây bệnh đã biết với các gen ứng viên trên mạng tƣơng tác gen/protein, bao gồm cả các tƣơng tác trực tiếp và gián tiếp. Không những đạt đƣợc hiệu quả cao trong bài toán phân hạng gen ứng viên liên quan đến bệnh, thuật toán này còn đƣợc sử dụng hiệu quả trong việc xác định các microRNA mới liên quan đến bệnh [13] cũng nhƣ các đích tác động mới của thuốc [14]. Tiếp nối thành công của thuật toán RWR cho bài toán phân hạng và tìm kiếm gen gây bệnh trên mạng tƣơng tác gen/protein đồng nhất. Một phiên bản mới của thuật toán đã đƣợc đề xuất sử dụng trên mạng không đồng nhất kết hợp giữa mạng tƣơng tác gen/protein và mạng kiểu hình bệnh [15] hoặc mạng tƣơng tự bệnh [16] gọi là RWRH. Thuật toán này cho hiệu quả dự đoán tốt hơn RWR trên mạng protein đồng nhất. Tuy nhiên, một thách thức cần đƣợc giải quyết là vấn đề nhiễu dữ liệu trong các mạng tƣơng tác sinh học nói chung và sự t ng hợp chƣa đầy đủ các liên kết giữa các gen trong mạng tƣơng tác gen/protein dẫn đến mạng tƣơng tác gen/protein hiện có chƣa bao phủ hết toàn bộ các liên kết của hệ gen ngƣời. Cụ thể, khi làm thực nghiệm chúng tôi nhận thấy với nhiều bệnh, các gen liên quan đã biết cũng không hoàn toàn tạo thành một mô đun mà thậm chí chúng Nguyễn Đại Phong, Đặng Vũ Tùng, Lê Đức Hậu, Từ Minh Phƣơng 417 còn cách nhau rất xa trên mạng tƣơng tác. Vì vậy, các phƣơng pháp phân hạng gen hiện có vẫn chƣa đạt đƣợc hiệu quả cao. Để giải quyết vấn đề này, chúng tôi đề xuất một phƣơng pháp kết hợp nhằm mục đích tìm kiếm các gen ứng viên gây bệnh có liên kết yếu hoặc ở xa những gen gây bệnh đã biết. Trong phƣơng pháp này, chúng tôi tiến hành phân hạng tất cả các gen ứng viên bằng thuật toán dựa trên xác suất liên kết, sau đó trích chọn một tập các gen có độ liên quan cao nhất đối với các gen bệnh đã biết. Tập gen còn lại sẽ đƣợc tăng cƣờng trọng số liên kết bằng phƣơng pháp RWRH để xác định thêm các gen có khả năng liên quan đến bệnh đã biết. Kết quả thực nghiệm cho thấy phƣơng pháp đề xuất tốt hơn đáng kể so với các phƣơng pháp đã đƣợc sử dụng trong việc tìm kiếm gen ứng viên gây bệnh. Các phần còn lại của bài báo đƣợc bố cục nhƣ sau: Phần 2 mô tả dữ liệu, các nghiên cứu liên quan và phƣơng pháp đề xuất. Phần 3 trình bày các kết quả thực nghiệm. Cuối cùng là phần kết luận nêu các đóng góp chính của bài báo và đề xuất các hƣớng cải tiến mới. II. DỮ LIỆU VÀ PHƢƠNG PHÁP A. Dữ liệu Để có thể thực nghiệm với các thuật toán phân hạng dựa trên mạng, chúng tôi cần một mạng tƣơng tác gen/protein và các bệnh đã biết một số gen liên quan. Cụ thể, chúng tôi đã sử dụng mạng tƣơng tác gen/protein từ [11, 17]. Đây là một mạng vô hƣớng, có trọng số (biểu thị độ tƣơng tự về chức năng giữa các gen/protein) gồm 11.886 gen và 111.943 liên kết. Thêm vào đó, chúng tôi sử dụng các cơ sở dữ liệu về bệnh và các gen liên quan đã biết từ OMIM [18]. Kết quả thu đƣợc 622 bệnh với t ng số 3246 gen liên quan, trong đó 148 bệnh có từ 2 gen liên quan trở lên đã đƣợc phát hiện. Với mỗi bệnh, tập các gen đã biết đƣợc sử dụng nhƣ là tập gốc trong quá trình phân hạng bởi các thuật toán. B. Các phương pháp phân hạng dựa trên đồ thị Trong bài báo này, mạng tƣơng tác gen/protein đƣợc biểu diễn bởi một đồ thị vô hƣớng, có trọng số G = (V, E) trong đó, tập các nút V là các gen/protein và tập các cạnh E thể hiện liên kết tƣơng tác giữa các gen/protein. Giả sử, cho trƣớc S (S⊆V) là tập các gen bệnh đã biết (còn gọi là tập hạt giống hay tập nút gốc), tức là một số lƣợng nhỏ các gen đã đƣợc phát hiện có liên quan đến bệnh trong các nghiên cứu trƣớc đó, C (C ⊆V) là tập các gen ứng viên có liên kết với các nút trong S. Mục tiêu của bài toán phân hạng gen là tính toán điểm số cho các gen trong tập C theo độ liên quan với S. Các điểm số này sau đó đƣợc xếp hạng và căn cứ vào đó để đề xuất các gen gây bệnh mới. 1. Thuật toán dựa trên xác suất liên kết (ERIN) Thuật toán dựa trên xác xuất liên kết [9] là một phƣơng pháp mới trong phân tích mạng xã hội và đã đƣợc ứng dụng cho bài toán phân hạng gen gây bệnh [19] đạt kết quả khả quan. Thuật toán này xác định tất cả các đƣờng đi không chu trình từ một nút (hoặc tập nút gốc) tới các nút còn lại trên đồ thị. Bắt đầu từ một nút gốc s chuyển tới các nút láng giềng bằng phƣơng pháp tìm kiếm theo chiều sâu (DFS). Tại mỗi bƣớc, nó tính t ng xác suất đƣờng đi từ nút gốc tới nút đƣợc thăm hiện hành. Quá trình sẽ dừng khi t ng xác suất đƣờng đi nhỏ hơn một ngƣỡng giá trị  cho trƣớc. Điều này có nghĩa là đƣờng đi tới các nút chƣa thăm không còn quan trọng bởi vì xác xuất đƣờng đi từ nút gốc tới các nút này là quá nhỏ. Xác suất di chuyển từ nút vi tới nút láng giềng vj biểu thị độ liên quan của nút vj với vi và đƣợc xác định theo công thức: ( ) { ( ) ( ) ∑ ( ) ( ) (1) trong đó: e(vi,vj), e(vi,vk) là trọng số các cạnh tƣơng ứng giữa nút vi với các nút láng giềng vj và vk ; f là hệ số giảm trừ (0< f <1). Ở đây cần chú ý rằng việc lựa chọn giá trị hệ số f dựa trên 2 tiêu chí: 1) giá trị f phải bảo toàn đƣợc thuộc tính của phƣơng pháp bƣớc ngẫu nhiên; 2) cho phép xác suất hội tụ ở mức chấp nhận đƣợc. Về nguyên tắc, hệ số f càng nhỏ càng tốt nhƣng khi đó thời gian tính toán sẽ tăng lên đáng kể. Xác suất đƣờng đi từ một nút khởi đầu s đến nút kết thúc t biểu hiện mức độ liên quan giữa s và t đƣợc xác định theo công thức: ( ) ( )(∏ ( )) ( ) (2) trong đó, P(vi,vj) đƣợc định nghĩa ở công thức (1). Rõ ràng xác suất đƣờng đi PPath là một giá trị thuộc khoảng [0, 1] do các thừa số trong (2) cũng thuộc khoảng [0, 1]. Nếu từ nút khởi đầu s tới nút kết thúc t có nhiều con đƣờng thì độ liên quan của t đối với s đƣợc xác định là t ng tất cả các xác suất đƣờng đi từ nút s đến nút t và đƣợc xác định theo công thức: ( | ) ∑ ( ) (3) trong đóp  G, có điểm bắt đầu là s và điểm kết thúc t, PathProbp(s, t) ≥ . Nhƣ vậy, nếu nút s có nhiều đƣờng đi tới t, điều này cho thấy rằng t có độ liên quan cao đối với s. 418 MỘT PHƢƠNG PHÁP CẢI TIẾN CHO BÀI TOÁN XÁC ĐỊNH CÁC GEN LIÊN QUAN ĐẾN BỆNH Đối với tập hợp các nút truy vấn S, thuật toán sẽ thực hiện cho từng nút trong tập hợp. Độ liên quan trung bình của nút t so với một tập các nút truy vấn S đƣợc tính theo công thức sau: ( | ) | | ∑ ( | ) (4) Khi áp dụng thuật toán này cho bài toán phân hạng và tìm kiếm gen gây bệnh, giả sử s là một gen gây bệnh đã biết và t là một gen ứng viên trên đồ thị mạng tƣơng tác protein. Nếu các xác suất đƣờng đi của tất cả các con đƣờng từ s tới t đều nhỏ hơn ngƣỡng giá trị  thì gen t hầu nhƣ không liên quan tới bệnh. Vì vậy, chúng ta chỉ xem xét các gen có ít nhất một đƣờng đi tới s có xác suất đƣờng đi lớn hơn ngƣỡng  cho trƣớc. Đối với một tập gen bệnh đã biết S, độ liên quan trung bình của mỗi gen ứng viên đối với S đƣợc sử dụng để xếp hạng các gen ứng viên. Cuối cùng, các gen ứng viên có điểm xếp hạng cao nhất sẽ đƣợc lựa chọn. Kết quả của thuật toán này cho chúng ta k gen có độ liên quan cao nhất với các gen bệnh đã biết. Trong đó, k là một số rất nhỏ so với t ng số gen trong đồ thị mạng tƣơng tác gen/protein. 2. Thuật toán bƣớc ngẫu nhiên có quay lại (RWR) Bƣớc ngẫu nhiên có quay lui là một biến thể của thuật toán bƣớc ngẫu nhiên trên đồ thị. Theo thuật toán này, một thực thể xuất phát từ một nút khởi đầu. Sau đó, nó di chuyển trên đồ thị bằng cách chuyển đến các nút lân cận một cách ngẫu nhiên với xác suất tỷ lệ với trọng số của các cạnh kết nối. Tại thời điểm t bất kỳ trong quá trình di chuyển, thực thể cũng có thể quay lại nút khởi đầu với một xác suất nhất định đƣợc gọi là xác suất quay lại  thuộc khoảng [0, 1]. Giả sử G = (V, E) là một đồ thị vô hƣớng có trọng số, trong đó V = (v1, v2, ...,vn) là tập các nút và E = ((vi, vj) | vi, vj  V) là tập các cạnh. Gọi S  V là tập các nút gốc (nút khởi đầu), W là ma trận kề của đồ thị G. Thuật toán bƣớc ngẫu nhiên có quay lại đƣợc mô tả nhƣ sau: ( ) (5) trong đó: pt+1 là vector xác suất của tập các nút |V| tại thời điểm t, phần tử thứ i biểu diễn xác suất của thực thể tại nút vi  V; W’ là ma trận chuẩn hóa từ ma trận kề W, trong đó W’i j (kí hiệu các phần tử (i, j) trong W’) biểu diễn xác suất mà thực thể di chuyển từ vi tới vj nằm trong tập V\{vi}; p0 là vector xác suất khởi đầu trong đó các phần tử có giá trị là 0 (nếu chúng không thuộc tập nút gốc) và 1/|S| (nếu chúng thuộc tập nút gốc). Khi áp dụng RWR cho bài toán phân hạng gen ứng viên dựa trên mạng [10, 12], tập hợp các nút gốc S là các gen bệnh đã biết và các gen ứng viên là các gen còn lại trên mạng tƣơng tác gen/protein. Ma trận chuẩn hóa W' đƣợc xác định nhƣ sau: ( ) ∑ ( ) (6) trong đó WG là ma trận kề của đồ thị mạng tƣơng tác gen/protein. Tất cả các gen ứng viên cuối cùng đƣợc phân hạng khi vector xác suất p∞ đạt trạng thái n định sau một số bƣớc lặp (tức là chênh lệch giữa pt+1 và pt nhỏ hơn một giá trị tới hạn, ở đây chúng tôi chọn là 10 -6 ). 3. Thuật toán kết hợp xác suất liên kết và bƣớc nhẫu nhiên có quay lại (CRWR) Dựa trên ý tƣởng của giải thuật RWRH cho mạng không đồng nhất đã đƣợc áp dụng để dự đoán các gen gây bệnh dựa trên mạng không đồng nhất kiểu gen - kiểu hình [15] và kiểu gen - bệnh tƣơng tự [16]. Trong nghiên cứu này chúng tôi đề xuất một phƣơng pháp phân hạng gen mới bằng cách kết hợp thuật toán dựa trên xác suất đƣờng đi với RWRH gọi là CRWR (Complex Random Walk with Restart), nhằm mục đích tăng cƣờng tầm quan trọng/độ liên quan cho các gen ở xa các gen bệnh đã biết trong cùng một mạng tƣơng tác gen/protein. Đầu tiên, từ mạng tƣơng tác gen/protein đồng nhất, chúng tôi sử dụng thuật toán dựa trên xác suất đƣờng đi để tách mạng tƣơng tác gen/protein thành hai mạng con GH và GL. Ở đây, GH chứa các gen có độ liên quan cao nhất đối với các gen bệnh đã biết, GL chứa các gen còn lại trong mạng tƣơng tác gen/protein. Bƣớc tiếp theo, chúng tối áp dụng thuật toán RWRH để tăng cƣờng trọng số cho các mạng trên. Cụ thể là ma trận W' đƣợc xác định nhƣ sau: [ ] (7) trong đó: W'H, W'L, lần lƣợt là các ma trận chuẩn hóa của các mạng con GH và GL. W'HL, W'LH là các ma trận chuẩn hóa của các liên mạng con. Giả sử,  là xác suất chuyển ngẫu nhiên của thực thể từ mạng con GH sang mạng con GL hoặc ngƣợc lại. Khi đó, các ma trận đƣợc xác định nhƣ sau: ( ) { ( ) ∑ ( ) ∑ ( ) (8) Nguyễn Đại Phong, Đặng Vũ Tùng, Lê Đức Hậu, Từ Minh Phƣơng 419 ( ) { ( ) ∑ ( ) ∑ ( ) (9) ( ) { ( ) ∑ ( ) ∑ ( ) ( )( ) ∑ ( ) (10) ( ) { ( ) ∑ ( ) ∑ ( ) ( )( ) ∑ ( ) (11) ở đây, WH, WL và WHL là các ma trận kề của đồ thị mạng GH, GL và mạng hỗn hợp. Vì thuật toán chỉ áp dụng cho một mạng gen/protein thuần nhất nên vector khởi đầu p0 vẫn đƣợc xác định nhƣ thuật toán RWR theo công thức sau: { | | (12) C. Phương pháp đánh giá Để đánh giá hiệu suất của phƣơng pháp phân hạng, đối với mỗi bệnh chúng tôi sử dụng phƣơng pháp kiểm tra chéo bỏ-ra-một (LOOCV: Leave-one-out cross validation). Theo đó, với mỗi lần lặp, một gen bệnh đã biết đƣợc lấy ra và coi nhƣ là một gen ứng viên bình thƣờng, các gen còn lại đƣợc sử dụng nhƣ các gen gốc làm dữ liệu đầu vào cho thuật toán. Cụ thể nhƣ sau: với tập gen bệnh đã biết S và tập gen ứng viên C (là tất cả các gen còn lại trên mạng), một gen s S đƣợc lấy ra và chúng tôi tiến hành phân hạng tập gen C{s} theo thuật toán đề xuất với tập S\{s} đƣợc sử dụng nhƣ tập các nút gốc. Quá trình này đƣợc lặp lại cho tất cả các gen bệnh đã biết. Sau đó chúng tôi thay đ i ngƣỡng  từ 1 cho đến |C{s}|. Giá trị sensitivity và 1-specificity đƣợc tính toán theo các công thức: (13) (14) trong đó TP (true positive) là số trƣờng hợp thử nghiệm mà thứ hạng của s ≤ , FN (false negative) là số trƣờng hợp thử nghiệm mà thứ hạng của s  , FP (false positive) là số trƣờng hợp thử nghiệm mà thứ hạng của c ≤  (với mỗi cC) và TN (true negative) là số trƣờng hợp thử nghiệm mà thứ hạng của c   (với mỗi cC). Một cặp giá trị sensitivity và 1-specificity tƣơng ứng với một điểm trên đƣờng cong ROC. Tiếp đó, hiệu suất của phƣơng pháp phân hạng đƣợc xác định bằng cách tính toán giá trị AUC (Area Under ROC Curve) là phần diện tích dƣới đƣờng cong ROC. III. THỰC NGHIỆM VÀ KẾT QUẢ Trong phần này, chúng tôi đánh giá ảnh hƣởng của các tham số tới sự n định cũng nhƣ hiệu quả của phƣơng pháp đề xuất. Đồng thời lựa chọn bộ tham số tốt nhất để so sánh hiệu quả phân hạng với RWR và ERIN trên cùng một bộ dữ liệu theo giá trị AUC. Cuối cùng, chúng tôi ứng dụng phƣơng pháp này để xác định các gen mới liên quan tới bệnh ung thƣ tuyến tiền liệt. A. Ảnh hưởng của tham số Thực nghiệm đầu tiên đƣợc chúng tôi tiến hành để xác định ảnh hƣởng của tham số  tới hiệu quả của phƣơng pháp đề xuất. Chúng tôi lần lƣợt thay đ i giá trị tham số  từ 0.1 đến 0.9 sau đó đó tính toán giá trị AUC cho từng trƣờng hợp theo phƣơng pháp đã đề xuất ở phần II.C. Kết quả thực nghiệm đƣợc mô tả trong Hình 1. Dựa trên kết quả thử nghiệm, chúng tôi nhận thấy khi giá trị tham số  ≤ 0.2, thuật toán đề xuất cho giá trị AUC cao nhất; trong trƣờng hợp 0.2 0.7, kết quả phân hạng giảm một cách đáng kể. Điều này cho thấy rằng, với giá trị  đƣợc lựa chọn phù hợp (cụ thể là  = [0.1, 0.2]), thuật toán đề xuất sẽ ƣu tiên cả những gen ứng viên nằm trong phân vùng cách xa các gen gây bệnh đã biết, dẫn đến đạt hiệu quả tốt hơn. 420 MỘT PHƢƠNG PHÁP CẢI TIẾN CHO BÀI TOÁN XÁC ĐỊNH CÁC GEN LIÊN QUAN ĐẾN BỆNH Hình 1. Biểu diễn các giá trị AUC trung bình trên 148 bệnh với tham số β tăng từ 0.1 đến 0.9 B. So sánh với RWR và ERIN Để khẳng định hiệu quả phƣơng pháp đề xuất, chúng tôi tiến hành thực nghiệm và so sánh kết quả phân hạng với các phƣơng pháp RWR, ERIN trên cùng một bộ dữ liệu đã mô tả trong phần II.A và phƣơng pháp đánh giá LOOCV. Dựa trên kết quả phân hạng gen gây bệnh của [10-12] và [9], chúng tôi thiết lập giá trị các tham số  = 0.7 cho phƣơng pháp RWR và  = 10-6, f = 0.1 cho phƣơng pháp ERIN. Đối với mỗi phƣơng pháp, chúng tôi tiến hành vẽ đƣờng cong ROC và tính giá trị AUC trung bình cho tất cả 148 bệnh bằng cách tính các giá trị sensitivity và 1- specificity cho từng bệnh, sau đó tính giá trị sensitivity và 1-specificity trung bình của 148 bệnh tại các ngƣỡng . Hình 2 biểu diễn đƣờng cong ROC và giá trị AUC trung bình của cả ba phƣơng pháp đƣợc so sánh. Hình 2. Đƣờng cong ROC biểu diễn kết quả thực thi của các thuật toán Với kết quả thực nghiệm này, chúng tôi nhận thấy rằng so với các phƣơng pháp phân hạng dựa trên mạng tƣơng tác protein khác nhƣ RWR, ERIN thì phƣơng pháp đề xuất của chúng tôi đạt đƣợc hiệu suất cao hơn rõ rệt. Điều này cho thấy rằng độ chính xác của CRWR là tốt hơn bởi sự ƣu tiên trọng số liên kết của các gen nằm ở phân vùng xa các gen gây bệnh đã biết. C. Dự đoán các gen liên quan đến bệnh ung thư tuyến tiền liệt Trong phần này, chúng tôi kiểm chứng khả năng xác định các gen mới liên quan đến bệnh của phƣơng pháp đề xuất bằng cách áp dụng phƣơng pháp này cho một bệnh cụ thể. Để thực hiện điều này, chúng tôi tiến hành xác định các Nguyễn Đại Phong, Đặng Vũ Tùng, Lê Đức Hậu, Từ Minh Phƣơng 421 gen mới liên quan đến bệnh ung thƣ tuyến tiền liệt (prostate cancer) có mã MIM là 176807 và thu thập các bằng chứng y văn của các gen có thứ hạng cao trong kết quả phân hạng. Ung thƣ tuyến tiền liệt xảy ra khi những tế bào bất thƣờng phát triển trong tuyến tiền liệt. Những tế bào này có thể tiếp tục nhân lên một cách không kiểm soát và đôi khi lan ra ngoài tuyến tiền liệt sang những bộ phận kế cận hay xa hơn của cơ thể. Tra cứu trong cơ sở dữ liệu OMIM, chúng tôi thu thập đƣợc 22 gen đã đƣợc chứng minh là có liên quan tới bệnh. Trong đó có 7 gen không có liên kết trong mạng tƣơng tác gen/protein chúng tôi sử dụng để làm thực nghiệm. Tập 15 gen còn lại đƣợc sử dụng nhƣ là tập gốc trong quá trình phân hạng, các gen còn lại trong mạng tƣơng tác gen/protein đƣợc coi là các gen ứng viên và phân hạng theo phƣơng pháp đã đề xuất Thông tin về các gen liên quan tới bệnh đƣợc trình bày trong Bảng 1 Bảng 1. Các gen gây bệnh ung thƣ tuyến tiền liệt và số liên kết trong mạng gen/protein TT Ký hiệu của gen Mã Entrez của gen Số liên kết PPI TT Ký hiệu của gen Mã Entrez của gen Số liên kết PPI 1 367 AR 108 12 100188789 HPC6 0 2 675 BRCA2 42 13 347747 HPCQTL19 0 3 3732 CD82 17 14 9566 HPCX 0 4 999 CDH1 64 15 1316 KLF6 3 5 11200 CHEK2 80 16 8379 MAD1L1 6 6 60528 ELAC2 3 17 4481 MSR1 14 7 3029 HAGH 25 18 4601 MXI1 10 8 6928 HNF1B 44 19 7834 PCAP 0 9 408259 HPC3 0 20 5728 PTEN 30 10 408260 HPC4 0 21 7991 TUSC3 8 11 619402 HPC5 0 22 463 ZFHX3 3 Sau khi phân hạng, chúng tôi lựa chọn 30 gen có thứ hạng cao nhất và tiến hành thu thập bằng chứng về mối quan hệ giữa các gen này với bệnh ung thƣ tuyến tiền liệt từ cơ sở dữ liệu PubMed [19]. Thông tin về các gen và mã các văn y chứng minh sự liên quan giữa các gen này với bệnh đƣợc trình bày trong Bảng 2. Các gen còn lại mặc dù chƣa có bằng chứng trực tiếp liên quan đến bệnh cần nghiên cứu nhƣng chúng cũng là nguyên nhân gây ra các bệnh ung thƣ khác nhƣ: ung thƣ tuyến giáp, tuyến mô, đại tràng, Các gen này chúng tôi đề xuất với các nhà y sinh học nghiên cứu và tìm kiểm thêm các chứng cứ liên quan đến bệnh bằng các thí nghiệm y sinh chuyên sâu. Bảng 2. Các gen liên quan tới bệnh ung thƣ tuyến tiền liệt trong số 30 gen có thứ hạng cao nhất Xếp hạng Ký hiệu của gen Mã Entrez của gen Mã y văn tham khảo trên PubMed 2 4602 MYB 26089205 3 10401 PIAS3 11071847 4 1487 CTBP1 23097625 7 1051 CEBPB 25772238 9 688 KLF5 24931571 15 6184 RPN1 19064571 21 6185 RPN2 17220478 24 7157 TP53 25827447 25 9611 NCOR1 23129261 26 4609 MYC 25973080 28 10608 MXD4 15862967 IV. KẾT LUẬN Trong bài báo này, chúng tôi đã đề xuất một phƣơng pháp kết hợp giữa thuật toán dựa trên xác suất đƣờng đi và bƣớc ngẫu nhiên có quay lại áp dụng cho bài toán phân hạng gen với mục đích tìm kiếm các gen ứng viên gây bệnh nằm xa các gen bệnh đã biết trên đồ thị mạng tƣơng tác gen/protein. Kết quả thực nghiệm cho thấy phƣơng pháp đề xuất đạt đƣợc hiệu quả tốt hơn so với các phƣơng pháp đƣợc sử dụng một cách đơn lẻ trƣớc đó. Chúng tôi cũng đã áp dụng phƣơng pháp đề xuất để tìm kiếm các gen liên quan đến bệnh ung thƣ tuyến tiền liệt và thu đƣợc kết quả khả quan. Với kết quả này, có thể thấy rằng khả năng dự đoán gen bệnh mới dựa trên độ liên quan/ tầm quan trọng tƣơng đối của chúng so với các gen bệnh đã biết là hoàn toàn khả thi. Các gen ứng viên thứ hạng cao có thể đƣợc đề xuất cho các nhà nghiên cứu y, sinh học kiểm tra bằng các thí nghiệm sinh học chuyên sâu. Phƣơng pháp đề xuất trong bài báo có thể đƣợc phát triển thành một phần mềm ứng dụng, triển khai trong các cơ sở nghiên cứu y sinh học phục vụ công tác nghiên cứu và đào tạo. Đồng thời cũng có thể ứng dụng để phát hiện các gen liên quan đến những căn bệnh di truyền cụ thể. Đây cũng là bƣớc tiền đề cho việc tìm ra các phƣơng pháp điều trị thích hợp cho các bệnh liên quan đến gen. Trong các nghiên cứu tiếp theo, chúng tôi sẽ thực hiện thêm các kiểm nghiệm kết quả bằng cách tìm các bằng 422 MỘT PHƢƠNG PHÁP CẢI TIẾN CHO BÀI TOÁN XÁC ĐỊNH CÁC GEN LIÊN QUAN ĐẾN BỆNH chứng y văn về mối liên quan giữa các gen ứng viên có thứ hạng cao và bệnh đang đƣợc xem xét. Đồng thời, chúng tôi cũng sẽ thử nghiệm phƣơng pháp đề xuất với các đồ thị mạng sinh học khác nhƣ: mạng trao đ i chất, mạng điều hòa gen, mạng tƣơng tác di truyền để khẳng định thêm về hiệu quả thuật toán. TÀI LIỆU THAM KHẢO [1] G. H. Fernald, E. Capriotti, R. Daneshjou, K. J. Karczewski, and R. B. Altman, "Bioinformatics challenges for personalized medicine," Bioinformatics, vol. 27, pp. 1741-1748, 2011. [2] K. Reynolds, "Achieving the Promise of Personalized Medicine," Clinical Pharmacology & Therapeutics, vol. 92, pp. 401- 405, 2012. [3] D. Jones, "Steps on the road to personalized medicine," Nature Reviews Drug Discovery, vol. 6, pp. 770-771, 2007. [4] M. ML, M. JC, L. AC, A.-B. M, C. ME, and e. al, "Meta-analysis of 13 genome scans reveals multiple cleft lip/palate genes with novel loci on 9q21 and 2q32-35," American Journal of Human Genetics, vol. 75(2), pp. 161-173, 2004. [5] S. R, U. I, and S. R, "Network-based prediction of protein function," Molecular Systems Biology, vol. 3(88), 2007. [6] J. LB, "Linkage disequilibrium and the search for complex disease genes," Genome Research, vol. 10(10), pp. 1435-1444, 2000. [7] C. J., A. B., and J. A., "Disease candidate gene identification and prioritization using protein interaction networks," BMC Bioinformatics, vol. 10, 2009. [8] Đ. V. Tùng, D. A. Trà, L. Đ. Hậu, and T. M. Phƣơng, "Phân hạng gen gây bệnh sử dụng học tăng cƣờng kết hợp với xác suất tiền nghiệm," Tạp chí Công nghệ thông tin & Truyền thông, vol. 13(33), pp. 55-66, 2015. [9] H. Wang, C. K. Chang, H.-I. Yang, and Y. Chen, "Estimating the Relative Importance of Nodes in Social Networks," Journal of Information Processing Society of Japan, vol. 21(3), pp. 414-422, 2013. [10] D.-H. Le and Y.-K. Kwon, "GPEC: A Cytoscape plug-in for random walk-based gene prioritization and biomedical evidence collection," Computational Biology and Chemistry, vol. 37, pp. 17-23, 2012. [11] D.-H. Le and Y.-K. Kwon, "Neighbor-favoring weight reinforcement to improve random walk-based disease gene prioritization," Computational Biology and Chemistry, vol. 44, pp. 1-8, 2013. [12] S. Köhler, S. Bauer, D. Horn, and P. N. Robinson, "Walking the Interactome for Prioritization of Candidate Disease Genes," The American Journal of Human Genetics, vol. 82, pp. 949-958, 2008. [13] D.-H. Le, "Network-based ranking methods for prediction of novel disease associated microRNAs," Computational Biology and Chemistry, vol. 58, pp. 139-148, 2015. [14] X. Chen, M.-X. Liu, and G.-Y. Yan, "Drug–target interaction prediction by random walk on the heterogeneous network," Molecular BioSystems, vol. 8, pp. 1970-1978, 2012. [15] L. Y and P. JC, "Genome-wide inferring gene-phenotype relationship by walking on the heterogeneous network," Bioinformatics, vol. 26, pp. 1219-1224, 2010. [16] D.-H. Le and V.-T. Dang, "Ontology-based disease similarity network for disease gene prediction," Vietnam J Comput Sci, p. 9, 2016. [17] B. Linghu, E. S. Snitkin, Z. Hu, Y. Xia, and C. DeLisi, "Genome-wide prioritization of disease genes and identification of disease-disease associations from an integrated human functional linkage network," Genome Biology, vol. 10, 2009. [18] J. Amberger, C. A. Bocchini, A. F. Scott and A. Hamosh, "McKusick's Online Mendelian Inheritance in Man (OMIM®)", Nucleic Acids Research, 37 (2009), pp. D793-D796. [19] J. D. Osborne, S. Lin, W. A. Kibbe, L. J. Zhu, M. I. Danila and R. L. Chisholm, "GeneRIF is a more comprehensive, current and computationally tractable source of gene-disease relationships than OMIM", Oxford University Press (2006). AN IMPROVED METHOD FOR DETERMINING DISEASE-RELATED GENES Nguyen Dai Phong, Dang Vu Tung, Le Duc Hau, Tu Minh Phuong ABSTRACT — In computational biology, the identification of disease genes often begins with prioritizing candidate genes according to their relevance to a disease phenotype. This helps to narrow the set of disease-related genes which need to be identified by intensive biomedical experiments. Currently, many different methods have been proposed to prioritize candidate genes based on the relationships between proteins, which are encoded in gene/protein interaction networks. Most of these methods are based on the assumption of “module disease”, i.e. genes relating to the same disease tend to be located next to each other on the interaction network. These methods prioritize candidate genes which are close to known disease genes on the interaction network. However, during the course of experiments, we found that for many diseases, the known genes do not completely form a module, but are located far from each other on the interaction network. In such cases, the existing methods for gene prioritization are no longer effective. In this paper, we propose an improved method to prioritize genes related to the abovementioned diseases by increasing the linking weights for genes which are located away from known disease genes. We experimentally evaluate the efficiency in prioritizing genes of this method on 148 diseases on human’s interaction network and compare its performance with that of other significant methods, such as Random walk with restart (RWR) algorithm and method based on the probability of association (ERIN). The experiment results show that our proposed method achieves high performance of 95.3%, which is better than RWR (93.4%) and ERIN (89.8%). In addition, by using such method, we are able to identify a number of new genes which are related to prostate cancer.