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.

Restriction site mapping requires a generator to put forward possible maps and a constraint checker to reject false maps. Ideally these combine to give an algorithm which calculates a sound and complete solution set. Three algorithms for generation are presented and compared. Two decompose a multi-enzyme problem (greater than or equal to 3) into subproblems. The constraint checker is based on separation theory. Some insights into the extent of constraint checking involved in and feasibility of more checking for three or more enzymes are discussed. The trade-off between computation time and the soundness of the solution set is examined.

A computer algorithm for restriction-site mapping consists of a generator of partial maps and a consistency checker. This paper examines consistency checking and argues that a method based on separation theory extracts the maximum amount of information from fragment lengths in digest data. It results in the minimum number of false maps being generated.