In article <DRW.94Oct6155502 at taylor.mit.edu>, drw at taylor.mit.edu (Dale R. Worley) writes:
|> One can now make family trees of sequenced proteins. In some cases,
|> the roots of these trees extend back far enough to be interesting, in
|> some cases, the divergence of the eukaryotes or before. Since, in
|> theory, all modern proteins are descendents of a handful of primal
|> proteins, once you take the ancestries of proteins back far enough,
|> you should start to see family resemblances between proteins that
|> don't have much resemblance now, and the beginnings of the Big
|> Picture: the family tree of ALL proteins.
|>|> Do we have enough data to do something like this yet, and if so, what
|> does the family tree look like?
To calculate evolutionary trees, you need to establish a distance
between the amino acid sequences. But to get an idea of how even 2 such
sequences are related, you have to align them first, finding out where
mutations, insertions and deletions ("indels") may have taken place.
Alignment of more than a few sequences is computationally hard, and
even worse, the optimal alignment depends on the evolutionary tree
(you need to distinguish mutations/indels that took place close to the root
of the tree from mutations later on; due to the noise in the data, there
may be conflicting evidence.) Indeed, some methods for constructing
evolutionary trees refine distance, tree, and alignment in a cyclic
way. Theoretically you can prove that there are no polynomial-time
approximation algorithms for the problem, if you start with nothing
but the sequences. (i.e. Generalized Tree Alignment has no poly-time
approximation scheme, see a recent preprint by Jiang, Lawler, Wang 1994.)
Comments appreciated. This topic will certainly be discussed during the
online Biocomputing course planned to start in Spring 1995. (see
(use your favorite hypertext browser (e.g. Mosaic) to view these documents.)
fuellen at dali.Mathematik.Uni-Bielefeld.DEfuellen at Techfak.Uni-Bielefeld.DEfuellen at MIT.EDU
Dr Stephen R Covey, The 7 Habits of Highly Effective People, Habit #3:
Put First Things First !