Reconstruction of strings past.

A major use of string-alignment algorithms is to compare macromolecules that are thought to have evolved from a common ancestor to estimate the duration of, or the amount of mutation in, their separate evolution and to infer as much as possible about their most recent common ancestor. Minimum message length encoding, a method of inductive inference, is applied to the string-alignment problem. It leads to an alignment method that averages over all alignments in a weighted fashion. Experiments indicates that this method can recover the actual parameters of evolution with high accuracy and over a wide range of values, whereas the use of a single optimal alignment gives biased results.