Significance of nucleotide sequence alignments: a method for random sequence permutation that preserves dinucleotide...

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Sequence similarity is often quantified by evolutionary distance.
• Base composition alone may not explain similarity in closely related sequences.
• The role of nucleotide order and usage patterns (dinucleotide, codon) requires investigation.

Purpose of the Study:

• To determine if sequence similarity can be explained by base composition alone.
• To assess the contribution of nucleotide order, dinucleotide, and codon usage to sequence similarity.
• To develop an efficient method for generating random permutations that preserve specific sequence usage patterns.

Main Methods:

• Calculating evolutionary distance between nucleotide sequences.
• Generating random permutations of sequences to determine average permutation distance.
• Formulating the permutation problem as generating random Eulerian walks on a directed multigraph.
• Developing and describing an efficient algorithm for generating such walks.

Main Results:

• The nucleotide order contributes to sequence similarity when the evolutionary distance is significantly smaller than the average permutation distance.
• An efficient algorithm for generating random Eulerian walks on directed multigraphs was developed.
• The algorithm enables the generation of random sequence permutations preserving dinucleotide, trinucleotide, and codon usage.

Conclusions:

• Sequence similarity is influenced by factors beyond base composition, including nucleotide order and specific usage patterns.
• The developed algorithm provides a robust method for analyzing sequence similarity by controlling for dinucleotide and codon usage.
• The similarity between specific human beta-1 interferon gene segments is not solely attributable to nonrandom dinucleotide and codon usage.