supplementary.bbl

\begin{thebibliography}{10}
\providecommand{\url}[1]{\texttt{#1}}
\providecommand{\urlprefix}{URL }
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi:\discretionary{}{}{}#1}\else
  \providecommand{\doi}{doi:\discretionary{}{}{}\begingroup
  \urlstyle{rm}\Url}\fi
\providecommand{\bibAnnoteFile}[1]{%
  \IfFileExists{#1}{\begin{quotation}\noindent\textsc{Key:} #1\\
  \textsc{Annotation:}\ \input{#1}\end{quotation}}{}}
\providecommand{\bibAnnote}[2]{%
  \begin{quotation}\noindent\textsc{Key:} #1\\
  \textsc{Annotation:}\ #2\end{quotation}}
\providecommand{\eprint}[2][]{\url{#2}}

\bibitem{Durbin98}
Durbin R, Eddy S, Krogh A, Mitchison G (1998) Biological Sequence Analysis:
  Probabilistic Models of Proteins and Nucleic Acids.
\newblock Cambridge, UK: Cambridge University Press.
\bibAnnoteFile{Durbin98}

\bibitem{HolmesRubin2002a}
Holmes I, Rubin GM (2002) Pairwise {RNA} structure comparison using stochastic
  context-free grammars.
\newblock Pacific Symposium on Biocomputing, 2002.
\bibAnnoteFile{HolmesRubin2002a}

\bibitem{Holmes2005}
Holmes I (2005) Accelerated probabilistic inference of {RNA} structure
  evolution.
\newblock BMC Bioinformatics 6.
\bibAnnoteFile{Holmes2005}

\bibitem{Holmes2003}
Holmes I (2003) Using guide trees to construct multiple-sequence evolutionary
  {HMM}s.
\newblock Bioinformatics 19 Suppl. 1: i147-157.
\bibAnnoteFile{Holmes2003}

\bibitem{Holmes2004}
Holmes I (2004) A probabilistic model for the evolution of {RNA} structure.
\newblock BMC Bioinformatics 5.
\bibAnnoteFile{Holmes2004}

\bibitem{HofackerEtAl94}
Hofacker IL, Fontana W, Stadler PF, Bonhoeffer S, Tacker M, et~al. (1994) Fast
  folding and comparison of {RNA} secondary structures.
\newblock Monatshefte f\"{u}r Chemie 125: 167-188.
\bibAnnoteFile{HofackerEtAl94}

\bibitem{KlostermanEtAl2006}
Klosterman PS, Uzilov AV, Bendana YR, Bradley RK, Chao S, et~al. (2006)
  {XRate}: a fast prototyping, training and annotation tool for phylo-grammars.
\newblock BMC Bioinformatics 7.
\bibAnnoteFile{KlostermanEtAl2006}

\bibitem{DowellEddy2006}
Dowell RD, Eddy SR (2006) Efficient pairwise {RNA} structure prediction and
  alignment using sequence alignment constraints.
\newblock BMC Bioinformatics 7.
\bibAnnoteFile{DowellEddy2006}

\bibitem{WuytsEtAl2004}
Wuyts J, Perrière G, Van De~Peer Y (2004) {{T}he {E}uropean ribosomal {R}{N}{A}
  database}.
\newblock Nucleic Acids Research 32: D101--103.
\bibAnnoteFile{WuytsEtAl2004}

\bibitem{GriffithsJonesEtAl2003}
Griffiths-Jones S, Bateman A, Marshall M, Khanna A, Eddy SR (2003) Rfam: an
  {RNA} family database.
\newblock Nucleic Acids Research 31: 439-441.
\bibAnnoteFile{GriffithsJonesEtAl2003}

\bibitem{WilliamsEtAl2006}
Williams PD, Pollock DD, Blackburne BP, Goldstein RA (2006) Assessing the
  accuracy of ancestral protein reconstruction methods.
\newblock PLoS Comput Biol 2: e69.
\bibAnnoteFile{WilliamsEtAl2006}

\bibitem{PollockChang2007}
Pollock DD, Chang BSW (2007) Dealing with uncertainty in ancestral sequence
  reconstruction: sampling from the posterior distribution.
\newblock In: Liberles  \cite{Liberles2007}, chapter~8.
\bibAnnoteFile{PollockChang2007}

\bibitem{ChangEtAl2007}
Chang BSW, Matz MV, Field SF, M\"{u}ller J, van Hazel I (2007) Dealing with
  model uncertainty in reconstructing ancestral proteins in the laboratory:
  examples from archosaur visual pigments and coral fluorescent proteins.
\newblock In: Liberles  \cite{Liberles2007}, chapter~15.
\bibAnnoteFile{ChangEtAl2007}

\bibitem{Gaucher2007}
Gaucher EA (2007) Experimental resurrection of ancient biomolecules: gene
  synthesis, heterologous protein expression, and functional assays.
\newblock In: Liberles  \cite{Liberles2007}, chapter~14.
\bibAnnoteFile{Gaucher2007}

\bibitem{Sakakibara2003}
Sakakibara Y (2003) {{P}air hidden {M}arkov models on tree structures}.
\newblock In: Proceedings of the Eleventh International Conference on
  Intelligent Systems for Molecular Biology. Menlo Park, CA: AAAI Press, pp.
  232--240.
\newblock Evaluation Studies.
\bibAnnoteFile{Sakakibara2003}

\bibitem{Sakakibara2004}
Matsui H, Sato K, Sakakibara Y (2004) Pair stochastic tree adjoining grammars
  for aligning and predicting pseudoknot {RNA} structures.
\newblock Proceedings / {IEEE} Computational Systems Bioinformatics Conference,
  {CSB} {IEEE} Computational Systems Bioinformatics Conference : 290-299.
\bibAnnoteFile{Sakakibara2004}

\bibitem{MamitsukaAbe94}
Mamitsuka H, Abe N (1994) Predicting location and structure of beta-sheet
  regions using stochastic tree grammars.
\newblock In: Altman R, Brutlag D, Karp P, Lathrop R, Searls D, editors,
  Proceedings of the Second International Conference on Intelligent Systems for
  Molecular Biology. Menlo Park, CA: AAAI Press, pp. 276-284.
\bibAnnoteFile{MamitsukaAbe94}

\bibitem{JoshiSchabes97}
Joshi A, Schabes Y (1997).
\newblock Tree-adjoining grammars.
\newblock \urlprefix\url{citeseer.ist.psu.edu/joshi97treeadjoining.html}.
\bibAnnoteFile{JoshiSchabes97}

\bibitem{RivasEddy2000}
Rivas E, Eddy SR (2000) The language of {RNA}: a formal grammar that includes
  pseudoknots.
\newblock Bioinformatics 16: 334-340.
\bibAnnoteFile{RivasEddy2000}

\bibitem{MeyerMiklos2007}
Meyer IM, Mikl\'os I (2007) {S}imul{F}old: simultaneously inferring rna
  structures including pseudoknots, alignments, and trees using a {B}ayesian
  {MCMC} framework.
\newblock PLoS Computational Biology 3: e149.
\bibAnnoteFile{MeyerMiklos2007}

\bibitem{HeinEtal2000}
Hein J, Wiuf C, Knudsen B, Moller MB, Wibling G (2000) Statistical alignment:
  computational properties, homology testing and goodness-of-fit.
\newblock Journal of Molecular Biology 302: 265-279.
\bibAnnoteFile{HeinEtal2000}

\bibitem{Miklos2002}
Mikl\'{o}s I (2002) An improved algorithm for statistical alignment of
  sequences related by a star tree.
\newblock Bulletin of Mathematical Biology 64: 771-779.
\bibAnnoteFile{Miklos2002}

\bibitem{Metzler2003}
Metzler D (2003) Statistical alignment based on fragment insertion and deletion
  models.
\newblock Bioinformatics 19: 490-499.
\bibAnnoteFile{Metzler2003}

\bibitem{DrummondRambaut2007}
Drummond AJ, Rambaut A (2007) {BEAST}: Bayesian evolutionary analysis by
  sampling trees.
\newblock BMC Evolutionary Biology 7.
\bibAnnoteFile{DrummondRambaut2007}

\bibitem{SatijaEtAl2008}
Satija R, Pachter L, Hein J (2008) Combining statistical alignment and
  phylogenetic footprinting to detect regulatory elements.
\newblock Bioinformatics 24: 1236-1242.
\bibAnnoteFile{SatijaEtAl2008}

\bibitem{GorodkinEtAl97}
Gorodkin J, Heyer LJ, Stormo GD (1997) Finding the most significant common
  sequence and structure motifs in a set of {RNA} sequences.
\newblock Nucleic Acids Research 25: 3724-3732.
\bibAnnoteFile{GorodkinEtAl97}

\bibitem{MathewsTurner02}
Mathews DH, Turner DH (2002) Dynalign: an algorithm for finding the secondary
  structure common to two {RNA} sequences.
\newblock Journal of Molecular Biology 317: 191-203.
\bibAnnoteFile{MathewsTurner02}

\bibitem{HofackerEtAl2004}
Hofacker IL, Bernhart SH, Stadler PF (2004) Alignment of {RNA} base pairing
  probability matrices.
\newblock Bioinformatics 20: 2222-2227.
\bibAnnoteFile{HofackerEtAl2004}

\bibitem{Miyazawa94}
Miyazawa S (1994) A reliable sequence alignment method based on probabilities
  of residue correspondence.
\newblock Protein Engineering 8: 999-1009.
\bibAnnoteFile{Miyazawa94}

\bibitem{BucherHofmann96}
Bucher P, Hofmann K (1996) A sequence similarity search algorithm based on a
  probabilistic interpretation of an alignment scoring system.
\newblock In: States DJ, Agarwal P, Gaasterland T, Hunter L, Smith RF, editors,
  Proceedings of the Fourth International Conference on Intelligent Systems for
  Molecular Biology. Menlo Park, CA: AAAI Press, pp. 44-51.
\bibAnnoteFile{BucherHofmann96}

\bibitem{Holmes98}
Holmes I, Durbin R (1998) Dynamic programming alignment accuracy.
\newblock Journal of Computational Biology 5: 493-504.
\bibAnnoteFile{Holmes98}

\bibitem{BrayPachter2004}
Bray N, Pachter L (2004) {MAVID}: Constrained ancestral alignment of multiple
  sequences.
\newblock Genome Research 14: 693-699.
\bibAnnoteFile{BrayPachter2004}

\bibitem{DoEtAl2004}
Do CB, Brudno M, Batzoglou S (2004).
\newblock {PROBCONS}: Probabilistic consistency-based multiple alignment of
  amino acid sequences.
\newblock Submitted.
\bibAnnoteFile{DoEtAl2004}

\bibitem{LoytynojaGoldman2005}
Loytynoja A, Goldman N (2005) An algorithm for progressive multiple alignment
  of sequences with insertions.
\newblock Proceedings of the National Academy of Sciences of the USA 102:
  10557-62.
\bibAnnoteFile{LoytynojaGoldman2005}

\bibitem{SchwartzPachter2007}
Schwartz AS, Pachter L (2007) Multiple alignment by sequence annealing.
\newblock Bioinformatics 23: e24-9.
\bibAnnoteFile{SchwartzPachter2007}

\bibitem{BradleyPachterHolmes2008}
Bradley RK, Pachter L, Holmes I (2008) Specific alignment of structured {RNA}:
  Stochastic grammars and sequence annealing.
\newblock Bioinformatics 24: 2677-2683.
\bibAnnoteFile{BradleyPachterHolmes2008}

\bibitem{EickmeyerEtAl2008}
Eickmeyer K, Huggins P, Pachter L, Yoshida R (20087) On the optimality of the
  neighbor-joining algorithm.
\newblock Algorithms for Molecular Biology 3.
\bibAnnoteFile{EickmeyerEtAl2008}

\bibitem{KarlinAltschul93}
Karlin S, Altschul SF (1993) Applications and statistics for multiple
  high-scoring segments in molecular sequences.
\newblock Proceedings of the National Academy of Sciences of the USA 90:
  5873-5877.
\bibAnnoteFile{KarlinAltschul93}

\bibitem{Mott2000}
Mott R (2000) Accurate formula for {P}-values of gapped local sequence and
  profile alignments.
\newblock Journal of Molecular Biology 300: 649-659.
\bibAnnoteFile{Mott2000}

\bibitem{Eddy2008}
R ES (2008) A probabilistic model of local sequence alignment that simplifies
  statistical significance estimation.
\newblock PLoS Computational Biology 4.
\bibAnnoteFile{Eddy2008}

\bibitem{Liberles2007}
Liberles DA, editor (2007) Ancestral Sequence Reconstruction. Oxford University
  Press.
\bibAnnoteFile{Liberles2007}

\end{thebibliography}