Tiếp cận phương pháp maximum
likelihood để tái cấu trúc cây
sinh loài


Nội dung(1)
•
•
•
•
•

Cây phân loài
Maximum likelihood
Mô hình tiến hóa
MLE trên một mô hình tiến hóa
Tìm hiểu trong thời gian tới


Cây sinh loài
• Phát sinh sinh loài đó là tái tạo lịch sử tiến
hóa.
• Dựa trên các phương pháp toán học để
suy luận lịch sử tiến hóa sự sống trên
hành tinh chúng ta.
• Việc tái cấu trúc này liên quan đến việc
nhận diện chỉ định những đặc tính đồng
dạng (homologous characters)- được chia
sẻ giữa các lòai sinh vật khác nhau.

Cây sinh loài
• Định nghĩa: Một cây
sinh loài S với đỉnh
gốc là T với tất cả
đỉnh bên trong có
bậc tối thiểu là 3,
những nhãn lá biểu
diễn bởi tập hợp S
gồm có những dạng
khác nhau (được gọi
là taxa).


Một số phương pháp tái cấu trúc
cây sinh loài
1. Trong phương pháp Maximum parsimony (MP): một sự
giả định cho rằng cây tiến hóa tốt nhất mổ tả tiến trình
tiến hóa tốt nhất chính là cây mô tả được các lòai ít thay
đổi nhất tức là có ít đột biến nhất.
2. Phương pháp distance method: Trong phương pháp
này từng cặp trình tự một sẽ được so sánh thẳng hàng
cặp đôi và ứng với từng cặp, khỏang cách di truyền sẽ
được tính tóan.
3. Phương pháp Maximum Likelihood (ML): hợp lý tối đa là
phương pháp tiêu tốn nhiều thời gian nhất nhưng lại cho
kết quả đáng tin cậy nhất. Ứng với mỗi mô hình tiến hóa
được chọn, phương pháp này sẽ tính tóan khả năng xác
suất mà một cây tiến hóa có thể có từ chuỗi trình tự
phân tích. Cây tiến hóa có xác suất cao nhất là cây cuối
cùng được chọn.



Ứơc lượng hợp lí cực đại (MLE)
• Xét mô hình thống kê trên không gian trạng thái
hữu hạn [m]:={1, 2, 3,…, m}.
• Một phân bố xác suất trên tập [m] là một bộ đơn
giản sau:


Ứơc lượng hợp lí cực đại (MLE)
• Một mô hình thống kê đại số là một ánh xạ
với
là các tham số chưa biết mô hình.
• Các tham số
phân bố trên tập mở
Θ ⊂¿
¿

Rd được gọi là không gian tham số của mô
hình f.
Giả sử rằng fi(θ)>0 tất cả i є[m] và θ є Θ
Từ giả thuyết đó, chúng ta có:


Ứơc lượng hợp lí cực đại (MLE)
• Dữ liệu của chúng ta được cho bởi dạng một
chuỗi của sự quan sát

u=i1 ,i2 ,i3 ,... ,i N


với ij là một phần tử trong không gian trạng thái
[m], và N chiều dài của chuỗi quan sát, thường
gọi là kích cỡ của mẫu.


Dữ liệu thống kê và “good fit”
đối với dữ liệu
• Chúng ta nói rằng mô hình f là thích hợp đối
với dữ liệu u nếu tồn tại một vector
θ ∈Θ sao cho phân bố xác suất f θ  xấp xỉ
v
v= v , v , v , . .. , v ∈¿
với tần số mẫu w:= N với
Nm
¿
và v k :=∣{ j ∈[ N ]:i j =k}∣
1

2

3

m


Hàm hợp lí (likelihood function)
• Xác suất của chuỗi mẫu quan sát bằng:
v

v


L θ = f i  θ  f i  θ . . . f i  θ = f 1  θ  f 2  θ  . . . f m  θ 
1

2

1

2

v

m

N

• Nếu v được xác định thì L là một hàm từ Θ
vào R+, được gọi là hàm hợp lí (likelihood
function).
• Vấn đề của ước lượng hợp lí cực đại là
làm cực đại hàm Lθ .


Log hàm hợp lí
• Vì hàm Lθ  và hàm log Lθ  có cùng điểm
cực trị, mà hàm Lθ  lại biểu diễn dưới
dạng tích nên ta thay phương trình hợp lý
bởi dạng phương trình tương đương
m


l  θ =log L θ =v 1 log f 1  θ . ..v m log f m  θ =∑ v i log f i  θ 
i=1

mục đích giảm nhẹ khâu tính tóan: lấy đạo
hàm và giải phương trình.


Ví dụ: Bài tóan DiaNA
• Một người là DiaNA có 3 tứ diện có tên là X, Y,
Z trên mỗi tứ diện được đánh các nhãn là A, G,
C, T.


Bài toán DiaNA (tt)
• DiaNA chọn ngẫu nhiên một trong 3 tứ
diện trên trước khi tung ngẫu nhiên chúng,
gọi xác suất để nhận các mặt A, G, C, T
tiếp đất tương ứng là:

p A , pG , p C , pT

p

i

= 1 and

p

i


≥0

for

all i
4



p

A

,

p

G

,

p

C

,

p


T

 :

¿
Δ = Δ m −1 : =¿
¿

∑
i= 1

¿


Bài tóan DiaNA (tt)
• Giả sử 2 tứ diện X, Y không cân đối, vì thế khi tung
lên và xác suất nhận các mặt tiếp đất khác nhau và
cho ở bảng sau:

• Sau 49 lần chọn và tung, DiaNA ghi nhận được dãy
chuỗi u sau :
u=TCACGTGATGAGAGCATTCTCAGACCGTGACGCGTGTAGCAGCGGCTC


Tham số hóa mô hình thống kê
bài tóan
• DiaNA sẽ chọn tứ diện X, Y, Z với xác suất
tương ứng là θ 1 ,θ 2 và 1−θ 1−θ 2 trước khi tung
chúng ngẫu nhiên.
• Hàm likelihood và log likelihood cho mẫu dữ liệu

trên là:

• Hàm hợp lý là một hàm thực trên tam gíac


Xác định xác suất từng kí tự
Xác suất của từng PA, PC, PG, PT:


Giải tìm nghiệm hợp lí cực đại
• Giải bài tóan cực trị hàm log likelihood trên
bằng cách giải hệ phương trình
∂l ∂l
=
=0
∂θ 1 ∂ θ 2

ta tính được nghiệm:


Nhận xét kết quả bài toán
• Giá trị hàm log likelihood:
Và xác suất tương ứng:
và gần với tần số mẫu:


Mô hình tiến hóa
• Chuỗi phân kỳ từ cùng một tổ tiên nhưng vì sự
hoán chuyển và chia rẽ của sự hóan chuyển đó
làm tiến hóa cộng đồng bởi sự chọn lọc, kết quả

của sự thay đổi trạng thái của một nucleotide
thành một nucleotide khác ở những vị trí khác
nhau.
• Tái cấu trúc cây sinh loài, chúng ta cần phải
chấp nhận một số giả định về quá trình và trạng
thái thay thế ở trong mô hình.


Mô hình tiến hóa
• Mô hình đơn giản nhất là mô hình mà trong đó
khả năng của bất kỳ nucleotide nào thay đổi
thành bất kỳ nucleotide khác là bằng nhau.
• Dự đoán khả năng rằng một nucleotide cụ thể ở
một vị trí cụ thể sẽ thay đổi đến một nucleotide
xác định khác trên một khoảng thời gian, chúng
ta cần phải biết là tỉ lệ tức thời của sự thay đổi.
• Mô hình đơn giản này có một tham số và được
biết là mô hình Jukes-Cantor.


Ma trận các tỉ lệ
Chúng ta cần xây dựng một bảng mà cho thấy tỉ lệ tức
thời cho mỗi một khả năng thay đổi ở một vị trí như sau:
Substituted Base
A
C
G
T
A
-3




Original baseC

-3  

G


-3  
T



-3 
Ma trận này thường được gọi là ma trận Q.
Đây không phải ma trận xác xuất, mà là ma trận các tỉ lệ,
tổng các phần tử của một hàng bằng 0.


Ma trận xác suất thay thế
• Từ ma trận tỉ lệ thay thế tức thời đó chúng ta tính ma
trận thay thế tương ứng θ(t) bởi mũ e.

• Qua một số phép tính toán ta có


Xác suất chuyển đổi
• Vậy: Nếu chúng ta biết có G ở vị trí nào đó ở

thời điểm t=0, chúng ta hỏi rằng khả năng bao
nhiêu ở đó vẫn là G vào thời điểm t (kí hiệu
P(GG)(t) ), và tương tự như vậy khả năng là bao
nhiêu nếu như A thay thế vào vị trí đó (kí hiệu
P(GA)(t)).
• Nếu tỉ lệ thay đổi là  trên đơn vị thời gian như
mô hình Jukes - Cantor trên, thì:
P(GG)(t) = 1/4 + 3/4e-4t and P(GA)(t)=1/4-1/ 4e-4t


Nhận xét về xác suất chuyển đổi
• Bởi vì theo mô hình Jukes-Cantor thì tất
cả thay thế là như nhau, nên phát biểu
chung là:
P(ii)(t) = 1/4 + 3/4e-4t và P(ij)(t)=1/4-1/4e-4t
• Ta thấy:
– Khi t 0 thì P(ii) 1 và P(ij)0,
– Khi t ∞ thì P(ii) 1/4 và P(ij)1/4

Điều này phù hợp với thực tế.


Một số mô hình khác
• Hiện nay, ngòai mô hình Jukes-Cantor
còn có một số mô hình khác thường sử
dụng như: Kimura-2, Kimura-3,…. Trong
các mô hình này có sự khác nhau về tỉ lệ
thay đổi trạng thái giữa các Base.