Забыли?

?

# 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(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
вЂў 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/--страниц
Пожаловаться на содержимое документа