Kimura alignment

[Lloyd Allison]

histone at acpub.duke.edu (Ronald DeBry) writes:

>article <D39Dv5.Ax8 at zoo.toronto.edu> mes at zoo.toronto.edu (Mark Siddall) writes:
>>Given a multiple hit site wherein roman numerals represent taxa and letters
>>are bases and the following distribution of states:
>>Taxon   I   II   III   IV   V  VI
>>        A   A     G    G    T   T
>>There are two possible explanations:
>>a) one transition and one transversion.
>>b) two transversions:
>>The decision as to which, requires reference to some tree.  But we do not
>>yet have a tree, in fact, the tree is the end point of what we are 
>>attempting to do.

>alignment should really be conditional on the evolutionary relationships
>(whether you are using a Kimura substitution model or not).  Two kinds
>of solutions have been proposed.  One can use an iterative reciprocal
>process, where a trial alignment is used to give a trial phylogeny,
>which is used to generate a new alignment then a new phylogeny and so on
>until it converges on a stable alignment/phylogeny.  This approach has
>been implemented as a computer program by Jotun Hein.  The on;y
>alternative that I know of is a series of papers by Rich Thorne.  In his
>method (essentially) all possible alignments are generated.  Each
>alignment is given a likelihood based on a model incorporating both
>insertion/deletion and substitution, and a distance matrix is calculated
>by weighting each alignment based on its likelihood.  The phylogeny is
>then inferred from that weighted distance matrix.
>   As someone who subscribes to the idea that phylogenetic inference is a
>statistical problem and that maximum likelihood in some form is the best
>approach, ...
>Ron DeBry Department of Medicine Duke Univ Medical Center
>histone at acpub.duke.edu

In the following we do Gibbs sampling over many, but not all
(that is infeasible), multiple alignments to get a good approx'
to the tree's true edge lengths.
Gibbs sampling is simulated annealing at a constant temperature;
if you cool it you also get a simulated annealing search for an
optimal alignment. This is for a fixed given tree, but it can be used to
compare a "few" competing evolutionary trees. (In principle you could
let the tree vary too, but then I don't know that I would like to wait up
for it to finish.)

%A L. Allison
%A C. S. Wallace
%T The posterior probability distribution of alignments and its application to
   parameter estimation of evolutionary trees and to optimization of multiple
   alignments.
%J J. Mol. Evol.
%V 39
%P 418-430
%D 1994

Lloyd ALLISON
Central Inductive Agency,
Dept. of Computer Science, Monash University, Clayton, Victoria 3168, AUSTRALIA
tel: 61 3 905 5205       fax: 61 3 905 5146       email: lloyd at cs.monash.edu.au
<A HREF="http://www.cs.monash.edu.au/~lloyd/tildeStrings">Molecular Biology</A>