Các phương sai sắp hàng đa chuỗi nhanh

Chương 4: Kết quả thực nghiệm và bình luận

Một đánh giá toàn diện và so sánh được các chương trình sắp hàng đa chuỗiđòi hỏi một số lượng lớn các sự dữ liệu được sắp xếp chính xác mà có thể được sử dụng như các bộ kiểm thử. Các bộ dữ liệu này có thể chỉ ra được hiệu suất của các chương trình sắp hàng đa chuỗi phụ thuộc vào số lượng các chuỗi, mức độ giống nhau giữa các chuỗi và số lượng các phép chèn thêm vào liên kết này. Các yếu tố khác cũng có thể ảnh hưởng đến chất lượng liên kết chẳng hạn như độ dài của chuỗi, … BAliBASE là bộ dữ liệu đáp ứng được đầy đủ các yêu cầu như thế. Do đó trong khóa luận này tôi sẽ sử dụng BAliBASE để kiểm tra hiệu năng của hai phương pháp sử dụng cây quyết định (cả về tốc độ lần điểm chuẩn) và so sánh nó với các chương trình sắp hàng đa chuỗi khác.

4.1 Giới thiệu về BAliBASE‌

BAliBASE - Benchmark Alignment dataBASE là một bộ dữ liệu được xây dựng bởi các nhà khoa học Julie D. Thompson, Olovier Poch và một số nhà khoa học khác. Việc xây dựng bộ dữ liệu BAliBASE hoàn toàn dựa trên những kết quả đã được kiểm chứng trước đó đồng thời bắt cặp dựa trên kinh nghiệm của chính những nhà khoa học này. BAliBASE là một bộ dữ liệu mở, được thiết kế để phục vụ cho mục đích đánh giá các chương trình sắp hàng đa chuỗi. Nó đặt ra tất cả các trường hợp gặp phải trong quá trình sắp hàng. Cơ sở dữ liệu của BAliBASE được làm một cách thủ công với các chú thích chi tiết.

4.1.1 BAliBASE 2

BAliBASE 2 có tất cả 8 reference, nhưng chỉ thường sử dụng 5 reference đầu tiên. Các file dữ liệu được cung cấp dưới định dạng RSF hoặc MSF.

4.1.2 BAliBASE 3

BAliBASE 3 bao gồm 5 reference. Mỗi reference bao gồm một số lượng file. Các file có tên là BBnnnnn bao gồm các chuỗi full-length, trong khi các file có tên là BBSnnnnn là các chuỗi chỉ chứa các vùng tương đồng (homologous).

4.1.3 Cách đánh giá của BAliBASE

BAliBASE sử dụng hai hệ số điểm là sum of pair (SP) và total colum (TC) để kiểm tra tính chính xác của một đa chuỗi thẳng hàng so với kết quả mà các nhà khoa học bắt cặp một cách thủ công.

Điểm SP được tính theo thuật toán sau:

- Đặt s(x, y). Ở đây x và y là hai amino axit, s(x, y) là điểm khi bắt cặp x với y

trong đa chuỗi thẳng hàng. khi đó ta sẽ có giá trị của s(x, y) tương ứng là:

s(x, y) = 1 nếu x và y đều là một amino axit.

s(x, y) = -1 nếu x và y là hai amino acid khác nhau. s(x, y) = -2 nếu x là gap, y khác gap và ngược lại. s(x, y) = 0 nếu x và y đều là gap.

- Giả sử SP(mi) là giá trị của điểm “sum of pair” ở cột thứ i của đa chuỗi thẳng hàng mà ta cần tính điểm ( phân biệt với đa chuỗi thẳng hàng mà các nhà khoa học đã sắp hàng bằng tay để làm kết quả so sánh ), giá trị SP(mi) được tính bằng cách lấy tổng của các s(x, y) trong đó x và y là các amino axit được lấy từ cột thứ i của đa chuỗi thẳng hàng. Sau đó điểm SP của cả đa chuỗi sẽ được tính bằng cách lấy tổng tất cả các điểm SP(mi) của tất cả các cột trong đa chuỗi.

Một ví dụ đơn giản cho việc tính toán SP(mi) như sau:

Bảng 6: Tính toán SP(mi)

m1	m2	m3	m4	m5	m6	m7	m8	m9
seq1	G	T	T	C	C	T	G	-	T
seq2	-	T	G	C	-	T	G	-	T
seq3	G	T	G	C	-	T	T	-	T
Score	-3	3	-1	3	-4	3	-1	0	3

Có thể bạn quan tâm!

Xem toàn bộ 50 trang tài liệu này.

Ví dụ trên thể hiện một đa chuỗi thẳng hàng với 3 chuỗi và độ dài mỗi chuỗi là 9.

Ở đây với cột thứ 1. Ta có:

SP(m1) = s(G, -) + s (G, G) + s (-, G) = -2 + 1 + -2 = -3.

Tương tự với các điểm SP của các cột từ m2 cho đến m9.

Như vậy, điểm SP(m) của đa chuỗi thẳng hàng trên sẽ là: SP(m) = 3.

- Sau đó điểm SP(m) với đa chuỗi thẳng hàng cần tính điểm sẽ được so sánh với kết quả SP(R) mà các nhà khoa học đã làm một cách thủ công có sẵn trong BAliBASE và điểm SP cuối cùng của đa chuỗi thẳng hàng mà phương pháp đưa ra sẽ được tính theo công thức: SP(m) / SP(R) * 100. Đây chính là cách tính điểm sum of pair (SP) của BAliBASE.

Hệ số điểm thứ hai của BAliBASE là total column (TC). Điểm TC chính là tỉ lệ số cột mà đa chuỗi thẳng hàng cần tính điểm chứa các amino axit giống hệt với cột của đa chuỗi thằng hàng mà các nhà khoa học đã làm thủ công trong BAliBASE.

Qua hai hệ số điểm SP và TC chúng ta có thể xác định được phần nào độ chính xác của kết quả của phương pháp sắp hàng đa chuỗi cần kiểm tra.

4.2 Kết quả thực nghiệm‌

Kết quả dưới đây, là kết quả của 2 bộ dữ liệu BAliBASE 2 và 3 với các phương pháp:

- CLUSTALW version 2.0.12

- MUSCLE version 3.6

- PROBCONS version 1.12

- MAFFT version 6.617

BAliBASE 2

Programs

Ref11(27)

Ref12(27)

Ref13(28)

Ref20(23)

Ref30(12)

Ref40(12)

Ref50(12)

Average

Time(s)

CLUSTALW

87.21

80.15

83.87

76.26

86.38

78.75

93.26

59.26

72.33

48.08

85.55

69.76

85.78

63.42

83.74

68.26

1383

MUSCLE

84.96

77.11

88.78

81.96

88.76

91.46

93.56

59.61

78.33

53.92

88.13

75.33

97.25

90.08

86.37

73.04

281

PROBCONS

89.48

84.26

90.46

84.89

91.95

94.85

94.01

61.04

81.68

63.08

92.25

77.91

98.58

94.00

91.24

81.18

4733

LINSI

84.91

78.59

82.12

89.84

84.28

57.30

51.17

94.02

83.67

74.67

371

Automatic-FAST

89.48

84.26

90.46

84.89

90.95

91.11

93.88

60.17

81.58

61.83

92.25

77.91

98.49

93.08

91.02

80.16

2280

Automatic-ACCURACY

89.48

84.26

90.46

84.89

90.95

91.11

93.88

60.17

81.59

61.92

92.25

77.91

98.58

94.00

91.02

80.20

2716

Bảng 7: Kết quả các phương pháp với BAliBASE 2

BAliBASE 3 Homologous

Programs

RV11(38)

RV12(44)

RV20(41)

RV30(30)

RV40(49)

RV50(15)

Average

Time(s)

CLUSTALW

66.25

41.76

90.30

78.95

92.35

45.00

81.77

48.30

N/A

79.76

41.73

82.90

53.46

7020

MUSCLE

74.84

54.92

92.89

82.30

95.55

55.02

86.47

53.83

N/A

87.25

51.13

87.81

61.58

450

PROBCONS

80.72

62.92

95.06

87.20

95.68

59.93

90.69

64.97

N/A

90.91

60.53

90.82

68.70

13030

LINSI

69.57

48.60

92.57

80.73

93.93

49.76

87.55

59.30

N/A

88.38

51.47

86.43

59.47

1100

EINSI

69.46

48.46

92.55

80.68

93.82

50.05

87.58

59.66

N/A

89.86

59.62

86.51

60.28

1300

Automatic-FAST

80.57

62.58

94.98

86.93

95.24

57.90

90.12

63.17

N/A

88.91

56.40

90.37

67.37

3340

Automatic-ACCURACY

80.72

62.92

94.86

86.70

95.36

58.44

90.44

63.60

N/A

89.85

53.73

90.55

67.36

3850

Bảng 8: Kết quả các phương pháp với BAliBASE 3 – homologous

BAliBASE 3 full-length

Programs

RV11(38)

RV12(44)

RV20(41)

RV30(30)

RV40(49)

RV50(16)

Average

Time(s)

CLUSTALW

50.02

22.74

86.50

71.30

85.16

21.98

72.56

27.30

78.93

39.55

74.25

30.75

75.37

37.39

17015

MUSCLE

59.39

35.56

91.82

80.70

89.07

34.32

80.38

38.43

86.82

46.76

85.46

48.00

82.48

48.26

1905

PROBCONS

66.80

41.48

94.17

85.55

91.69

40.66

84.6

54.3

90.24

52.86

89.17

56.69

86.37

55.66

32012

LINSI

66.31

43.81

93.56

83.49

92.72

45.21

86.6

59.31

92.69

61.53

90.15

59.26

87.25

59.33

3445

EINSI

66.11

43.6

93.48

83.19

92.51

44.6

86.81

59.53

92.37

61.13

89.76

59.55

87.09

59.08

3781

Automatic-FAST

66.65

41.18

93.75

84.30

91.31

41.90

84.77

52.13

91.59

57.08

88.45

54.69

86.46

56.09

7200

Automatic-ACCURACY

66.73

41.26

93.53

83.82

91.10

42.17

85.37

53.03

89.55

52.86

87.26

52.19

85.92

55.05

7530

Bảng 9: Kết quả các phương pháp với BAliBASE 3 – ful llength

Nhận xét

Bảng 7 chỉ ra kết quả của các phương pháp với bộ dữ liệu BAliBASE 2. Với mỗi phương pháp và 1 reference tương ứng, bảng 7 đưa ra 2 chỉ số lần lượt là điểm SP, TC của phương pháp đó với reference tương ứng. Cột cuối cùng thể hiện tổng số điểm SP, TC của từng phương pháp với bộ dữ liệu BAliBASE 2, cũng như tổng thời gian xử lý của từng phương pháp với bộ dữ liệu BAliBASE 2.

Từ bảng 7, ta có thể thấy, PROBCONS với bộ dữ liệu BAliBASE 2 cho kết quả tốt nhất, nhưng thời gian xử lý của nó quá lâu (lên đến 4733 s). Mặc dù BAliBASE 2 phần lớn gồm toàn những bộ dữ liệu nhỏ (chỉ khoảng vài đến vài chục chuỗi). Các phương pháp còn lại cho kết quả không tốt bằng mặc dù tốc độ xử lý cao hơn hẳn. Còn 2 phương án sử dụng cây quyết định cho kết quả tốt gần tương đương trên từng reference (đôi khi các phương án này cho kết quả tốt nhất). Mặc dù kết quả trung bình trên bộ dữ liệu BAliBASE 2, PROBCONS cao hơn 2 phương pháp sử dụng cây quyết định, nhưng không đáng kể (SP: 91.24 so với 91.02 và TC: 81.18 so với 80.20 và 80.16), tuy nhiên thời gian xử lý của phương pháp PROBCONS cao hơn gấp đôi so với 2 phương pháp sử dụng cây quyết định (4733 s so với 2280 s và 2716 s).

Bảng 8 chỉ ra kết quả với bộ dữ liệu BAliBASE 3 – homologous. Qua đó ta có thể thấy, PROBCONS cho kết quả tốt nhất với bộ dữ liệu này, tuy nhiên thời gian xử lý của nó quá lớn (13030 s). Còn các phương pháp khác lại cho kết quả tồi hơn hẳn mặc dù thời gian xử lý thấp hơn. Còn 2 phương pháp sử dụng cây quyết định, thì phương pháp Automatic – ACCURACY cho kết quả tốt nhất trên RV11 và bằng với PROBCONS. Còn kết quả cuối cùng chỉ kém phương án PROBCONS một ít. Điểm SP: PROBCONS là 90.82 so với 90.55 và 90.37 lần lượt của Automatic – ACCURACY và Automatic – FAST. Điểm TC: PROBCONS: 68.70 so với 67.36 và

67.37. Mặc dù 2 phương án này cho kết quả thấp hơn một chút, nhưng bù lại thời gian xử lý của chúng lại nhanh hơn rất nhiều ( 3850 và 3340 so với 13030

Bảng 9 chỉ ra kết quả của các phương pháp với bộ dữ liệu BAliBASE 3 – full length. Ở đây, MAFFT-L-INS-i và MAFFT-E-INS-i cho kết quả cao nhất với hầu hết các reference. PROBCONS cho kết quả thấp hơn một chút. 2 phương pháp sử dụng cây quyết định ở bộ dữ liệu này cho kết quả không thật sự khả quan. Nó không cho kết quả cao nhất ở bộ dữ liệu nào. Tuy nhiên kết quả cuối cùng nó cũng chỉ thấp hơn 2 phương pháp của MAFFT và cao hơn các phương pháp còn lại và thời gian xử lý thì hoàn toàn có thể chấp nhận được.

Qua những kết quả trên, ta có thể thấy rằng: Mặc dù 2 phương pháp sử dụng cây quyết định không cho kết quả tốt nhất trên từng bộ dữ liệu riêng biệt nhưng kết quả của chúng luôn đứng lần lượt là thứ 2 và thứ 3 trên từng bộ, chỉ kém kết qua tốt nhất một tỉ lệ rất nhỏ và hơn hẳn những phương pháp khác. Trong khi những phương pháp PROBCONS, MAFFT có thể tốt nhất trên 1 vài bộ dữ liệu, nhưng chúng vẫn mang những nhược điểm nhất định trên những bộ dữ liệu khác nhau.

Do 2 bộ dữ liệu chuẩn ở trên, chỉ bao gồm những dữ liệu nhỏ (chỉ khoảng vài chục đến trên một trăm chuỗi) không đủ để thể hiện hết những ưu điểm của hai phương pháp sử dụng cây quyết định này (do không thể thể hiện ưu điểm về mặt tốc độ khi xử lý các bộ test lớn, và không thể hiện được khả năng xử lý những bộ test ngoại cỡ - số lượng chuỗi cực lớn, độ dài chuỗi cực lớn).

Qua đó có thể nhận thấy ưu điểm của 2 phương án sử dụng cây quyết định mà tôi đưa ra.

Xem tất cả 50 trang.

Ngày đăng: 30/04/2022