The combinatorics of tandem duplication trees.

Area of Science:

• Computational Biology
• Evolutionary Genetics
• Bioinformatics

Background:

• Tandemly repeated sequences are common in genomes and arise from unequal recombination.
• Understanding the evolutionary history of these repeats, particularly through duplication trees, is crucial.
• Previous studies have provided counts for small numbers of repeats, but efficient methods for larger sets were lacking.

Purpose of the Study:

• To develop a recurrence relation for counting rooted and unrooted tandem duplication trees.
• To provide a method for estimating the number of duplication trees for large sets of tandemly repeated sequences.
• To establish a priori probabilities for phylogenies of repeated sequences being duplication trees.

Main Methods:

• Development of a recurrence relation to count tandem duplication trees consistent with observed sequence data.
• Tabulation of tree counts for small numbers of tandemly repeated sequences (n).
• Derivation of an asymptotic formula for estimating tree counts for large values of n.
• Presentation of a linear-time algorithm for recognizing duplication trees.

Main Results:

• The number of rooted duplication trees is precisely twice the number of unrooted trees.
• Recurrence relation and asymptotic formula provide accurate counts and estimates for duplication trees.
• Analysis of human immunoglobulin and T-cell receptor sequences revealed most maximum-parsimony trees were tandem duplication trees.

Conclusions:

• The developed recurrence relation and formulas offer a robust framework for analyzing tandem duplication events.
• Findings support the proposed mechanisms of tandem gene duplication in evolutionary processes.
• Efficient algorithms for recognizing and simulating duplication trees are now available.