作者arist ( 在他方 )
看板puzzle
標題[益智遊戲] 親緣樹
時間Sun May 31 11:21:13 2009
[簡介]
在生物資訊中，其中一個關心的問題就是如何還原重建出物種的演化樹(如下圖)。
從此演化樹中，任取三個我們可以看出哪兩個有比較近的親緣關係。
例如：
取 A,B,C 來看，知 A,C 的親緣較近，B 和另兩個較遠，將之記作 [(A,C),B]。
取 C,D,E 來看，知 C,D 的親緣較近，E 和另兩個較遠，將之記作 [(C,D),E]。
╱╲
╱╲ ╲
╱ ╲ ╲
╱ ╱╲ ╲
╱╲ ╱ ╱╲ ╲
A C B D F E
當然，有了演化樹，我們要得出親緣關係，是很容易。
但反之，若我們只有親緣關係，要如何重建演化樹呢？
(在實際問題中，因實驗會有誤差，有時有一小部分的關係是錯誤的，
如何在允許部分錯誤下去還原整個樹更是複雜的問題)
[遊戲規則] (基本版)
1. 兩人先各自劃一個演化樹(可依難易度調整遊戲的物種數目)，
2. 每回合兩人輪流詢問對方一個[三物種的親緣關係]，
3. 被詢問者要回答哪兩個物種關係較近。
4. 重複 2.3 的情況，直到有一方宣稱他已經重建整個演化樹。
若公布結果時，其答案為正確，則為勝，否者為輸。
[遊戲規則] (進階版)
在 3. 中，允許至多一次說謊的機會。
[暖身練習]
已知 6 物種的親緣關係如下：
[(A,B),C], [(C,D),B)] , [(C,D),E], [(D,E),F], [(A,E),F]
你有辦法重建，唯一的演化樹嗎?
若還不為一，你會想要再詢問哪三個物種關係呢?
[益智問題]
若在6個物種下，有辦法確定幾次內衣定可以得出答案呢?
(有Error, 和沒 Error 的情況各為何?)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.231.45
1F：→ arist:想找人試玩的可以丟我水球 05/31 11:21
2F：推 newacc:請問原PO的舉例中 05/31 23:57
3F：→ newacc:BDF誰比較近?一樣嗎? 05/31 23:57
4F：→ newacc:咦等等－ －ａ 05/31 23:58
5F：→ newacc:沒事我瞭了XD(請無視我XD) 06/01 00:00
6F：推 newacc:呃好像還是有疑問XD 06/01 00:10
7F：→ newacc:呃我又沒問題了.................呃我糊塗了XD 06/01 00:11
8F：推 newacc:(無限鬼打牆ing....XD) 06/01 00:13
9F：推 newacc:暖身我無法推出.......問ABE親源? 06/01 00:32
10F：推 chyrliin: 暖身題跟樓上一樣之問ABE親緣? 06/01 18:05
11F：推 puzzlez:第一個例子的C,D,E我沒有弄懂...他們都是五等親不是嗎? 06/01 18:10
12F：推 puzzlez:好像應該是[(C,E),D]才對...... 06/01 18:11
13F：推 chyrliin:延伸交點 06/01 18:23
14F：→ arist:CD 的親緣比較近， CE 的親緣比較遠 是 [(C,D),E] 沒錯 06/01 21:59
15F：→ arist:E 在一開始就和 {A,B,C,D,F} 分化了，所以E 距大家都很遠 06/01 22:00
16F：→ arist:接著 {A,B,C,D,F} 又分化為 {A,C} {B,D,F} 兩堆 06/01 22:01
17F：→ arist:暖身題加 [(A,E),B]則解為 ((((A,E),B),(C,D)),F) 06/01 22:13
18F：→ arist:若再加 [(A,B),E] 則解還不唯一 06/01 22:14
※ 編輯: arist 來自: 140.112.231.45 (06/01 22:15)
※ 編輯: arist 來自: 140.112.231.45 (06/01 22:21)
19F：推 newacc:暖身再問BCE 06/01 22:42
20F：→ newacc:呃我是指如果是[(A,B),E] 06/01 22:43
21F：推 puzzlez:想很久還是無法理解@@" 我先留給其他人做，自己以後再說吧 06/01 22:44
22F：推 puzzlez:好像只差[A或B 與 C或D 與 E]了........ 06/02 22:32
23F：→ arist:那暖身題只是熟悉一下規則 06/02 23:06
24F：→ arist:實際雙人玩時，要怎樣來問親緣關係是個比較有趣的問題 06/02 23:07