title: Number of distinct sequence alignments with k-match and match sections.
abstract: 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.
  
  
  CONCLUSIONS
  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.
authors: School of Science, Hangzhou Dianzi University, Hangzhou 310018, China.
authors: Xiaoqing
authors: X
authors: Liu
authors: Shangqiu Medical College, Shangqiu 476100, China.
authors: Xiaohua
authors: X
authors: Yang
authors: College of Life Sciences, Zhejiang Sci-Tech University, Hangzhou 310018, China.
authors: Cong
authors: C
authors: Wang
authors: College of Life Sciences, Zhejiang Sci-Tech University, Hangzhou 310018, China.
authors: Yuhua
authors: Y
authors: Yao
authors: College of Life Sciences, Zhejiang Sci-Tech University, Hangzhou 310018, China; Center for Systems Biology, University of Texas at Dallas, Richardson, TX 75080, USA. Electronic address: daiailiu04@yahoo.com.
authors: Qi
authors: Q
authors: Dai
mesh_terms: D004247:DNA / Q000235:genetics*; D008962:Models, Theoretical; D016415:Sequence Alignment / Q000379:methods*
chemical_list: D004247:DNA
keywords: Combinatorics; Deletion; Insertion; Match section; Sequence alignment; k-match