Traditional approaches to estimating evolutionary trees from DNA 
sequences assume that these sequences are arranged in an alignment 
matrix to specify per-residue homology information. However, this 
multiple sequence alignment is estimated, not observed, and so 
uncertainty in alignment estimates must be taken into account. We 
describe a model and algorithm for simultaneously estimating multiple 
sequence alignments and the phylogenetic trees that relate the proteins. 
Unlike current techniques which base phylogeny estimates on a single 
best estimate of the alignment, we take all alignments into 
consideration. Furthermore, because the alignment and phylogeny are 
constructed simultaneously, a guide tree is not needed. This solves the 
problem in which alignments created by progressive alignment are biased 
toward the guide tree used to generate them. Joint estimation also 
allows us to use more accurate substitution models (such as \Gamma_{4} + 
INV) when estimating the alignment, and to use the evidence in shared 
indels to group sister taxa in the phylogeny. Our model makes use of 
affine gap penalties, and can correctly deal with insertions and 
deletions of multiple letters. We use a Markov Chain Monte Carlo (MCMC) 
method to estimate the most probable tree, and its support. We will 
describe new transition kernels which improve the mixing efficiency, 
allowing the chain to converge even when starting from random 
alignments. Our current software can show alignment uncertainty; it 
should also improve model fit compared to current models (such as 
Clustal W), and improve the accuracy of estimating trees, alignments, 
and model parameters.