close

Вход

Забыли?

вход по аккаунту

?

Prof. Huson Phylogeny 7/12/04 How to treat ties? If we can choose

код для вставки
Prof. Huson
Phylogeny
7/12/04
How to treat ties?
If we can choose from more than one possible states, then either
1. resolve all possibilities by considering all possible transversals above w
(draw-back: can produce exponential size output)
2. break ties by choosing only one state for w
3. assign the set of all equally optimal states to w
size of output: O(n В· k) (n = species, size of alphabet, k = states)
Remarks
ad(1) can lead to exponential output
ad(3) computationally easy, but we lose information on which state for v can be combined with which states
for w (to produce the optimal score along edge (v, w))
Example
cost matrix:
A
C
G
T
{C}
A
0
2.5
1
2.5
C
2.5
0
2.5
1
{A}
0
вќ¦
в– 0
вњё
G
1
2.5
0
2.5
T
2.5
1
2.5
0
{C}
0
в–јвќЄ
вњЇ
{A}
{G}
0
вњђ
вќ¦
2.5 2.5 3.5 3.5
0
вњ¶
вњё
1
вњ¶
в– в– 5
1
вњї
5
3.5 3.5 3.5 4.5
вњї вњї
6
6
7
8
A C
ad(2) Two main strategies:
• ACCTRAN (’accelerated transformation’)
’reversals’
For a tie, choose the state for w, that is most different to the state chosen for v, thus force changes
to occur as far down the tree as possible
’parallelism’
• DELTRAN (’delayed transformation’)
For a tie, choose the state for w, that is most similar to the state chosen for v, thus force changes
to occur as far up the tree as possible
1
Prof. Huson
Phylogeny
7/12/04
Branch lengths
should indicate number of changes along branch, difficult to assign, because position of chance unsually
ambiguous
Example
(x= changes)
1
0
x
0
1
x
1
x
1
x
1
x
1
x
1
1010101010
0
x
0
x
x
x
x
1
x
1
1010101010
0
x
0
x
0
x
0
x
0
x
0
1
x
0
1
Simplest way to obtain branch length is to average over all possible optimal reconstructions of each character
For the example we obtained following tree:
1
0.833
0
1
0.662
1
0.5
0
0
0
0
Chapter 7
0.166 0.233
0
0
1
1
0.233 0.166
0 0.166
1
0
0
0.5
0
1
0.622
0 0.833
0
Variants of Parimony
Camin-Sokal parsimony (1965)
Two states, 0 and 1, only allow 0 в†’ 1 change, along a rooted tree
Example
2
Prof. Huson
Phylogeny
7/12/04
4 changes required
1
0
1
вњ’
1
1
1
0
0
1
1
вќ�
в– в– state 1
How to obtain optimal score?
1. use Sankoff with cost matrix 0
1
0
0
в€ћ
1
1
0
2. observed that if any decendent of node v has state 0, then so must v
Simple algorithm
LabelRec(v);
for each child w of v: LabelRec(w)
if any child has label 0, then v gets 0,
else v gets 1
Application
Evolution of small deletions of DNA: ’once deleted, can never revert’
Code each deletions as
1, if it happened
0, if not
Not appropiate if deletions can overlap, or if can’t detect with high confidence
Dollo parsimony
named by Dollo’s Law (1893)
’a complex character, once obtained, cannot be attained in the same form again’
states: 0 and 1, allow only at most one 0 в†’ 1 transition but many 1 в†’ 0
Example
4 changes (3 losses)
3
Prof. Huson
Phylogeny
1
0
1
1
1
1
7/12/04
0
x
0
x
1
1
x
x
How to compute
0
0
1
1. use Sankoff to approximate solution 0
1
1
L , L large
0
2. solve directly, using a Fitch like algorithm with two passes, one bottom up, second top-down
Application
Gene content phylogeny:
Genome x1 , . . . , xm
absence or presence of a gene gi in genome xj is indicated by 0 or 1.
пЈ«
genes
в†’
a11
пЈ¬ ..
A=пЈ­ .
...
an1
...
aij =
пЈ¶
a1n
..  ↓ genomes
. пЈё
amn
0 if a gene is absent in xj
1 if a gene is present in xj
Assumption
new gene only created once, but can be lost multiple times
4
Документ
Категория
Без категории
Просмотров
7
Размер файла
146 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа