Number of distinct sequence alignments with k-match and match sections.

BACKGROUND

Recent developments in sequence alignment have led to significant advances in our understanding of the functional, structural or evolutionary relationships among biological sequences. Great efforts have been made to count the total number of sequence alignments, but little attention has been paid to specific alignments associated with conserved patterns.

METHODS

We propose a new combinatorial method to count specific alignments. First, we represent a sequence alignment as a system of cells. Using combinatorial techniques and Stirling׳s formula, we then count the numbers of specific alignments with a k-match or match section of size k.

RESULTS

We developed three theorems related to different types of specific alignments. We found that the number of the alignments with match sections of at least k was less than that of k-match sections and the number of specific alignments was significantly lower than the results reported by Covington.

DISCUSSION

The presence of a large number of alignments makes a direct search for the optimal alignment unfeasible for long sequences, whereas our proposed method based on specific alignments decreases the search space by many times. This facilitates the development of a faster algorithm for performing sequence comparisons.