Evolutionary tree of *all* proteins

[Georg Fuellen]

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 
http://www.techfak.uni-bielefeld.de/techfak/persons/fuellen/BCChome.html, 
US mirror 
http://www.mit.edu:8001/afs/athena/user/f/u/fuellen/News/Ga/REM/Gna/BCChome.html
(use your favorite hypertext browser (e.g. Mosaic) to view these documents.)

kindest regards,
  georg
fuellen at dali.Mathematik.Uni-Bielefeld.DE
fuellen at Techfak.Uni-Bielefeld.DE
fuellen at MIT.EDU
    Dr Stephen R Covey, The 7 Habits of Highly Effective People, Habit #3:
    Put First Things First !