Significance of nucleotide sequence alignments: a method for random sequence permutation that preserves dinucleotide and codon usage

The similarity of two nucleotide sequences is often expressed in terms ofevolutionary distance, a measure of the amount of change needed totransform one sequence into the other. Given two sequences with a smalldistance between them, can their similarity be explained by their basecomposition alone? The nucleotide order of these sequences contributes totheir similarity if the distance is much smaller than their averagepermutation distance, which is obtained by calculating the distances formany random permutations of these sequences. To determine whether theirsimilarity can be explained by their dinucleotide and codon usage, randomsequences must be chosen from the set of permuted sequences that preservedinucleotide and codon usage. The problem of choosing random dinucleotideand codon-preserving permutations can be expressed in the language of graphtheory as the problem of generating random Eulerian walks on a directedmultigraph. An efficient algorithm for generating such walks is described.This algorithm can be used to choose random sequence permutations thatpreserve (1) dinucleotide usage, (2) dinucleotide and trinucleotide usage,or (3) dinucleotide and codon usage. For example, the similarity of two60-nucleotide DNA segments from the human beta-1 interferon gene(nucleotides 196-255 and 499-558) is not just the result of their nonrandomdinucleotide and codon usage.