THE SIZE DISTRIBUTION OF INSERTIONS AND DELETIONS IN HUMAN AND RODENT PSEUDOGENES SUGGESTS THE LOGARITHMIC GAP PENALTY FOR SEQUENCE ALIGNMENT

The size distributions of deletions, insertions, and indels (i.e., insertions or deletions) were studied, using 78 human processed pseudogenes and other published data sets. The following results were obtained: (1) Deletions occur more frequently than do insertions in sequence evolution; none of the pseudogenes studied shows significantly more insertions than deletions. (2) Empirically, the size distributions of deletions, insertions, and indels can be described well by a power law, i.e., f(k) = Ck(-b), where f(k) is the frequency of deletion, insertion, or indel with gap length k, b is the power parameter, and C is the normalization factor. (3) The estimates of b for deletions and insertions from the same data set are approximately equal to each other, indicating that the size distributions for deletions and insertions are approximately identical. (4) The variation in the estimates of b among various data sets is small, indicating that the effect of local structure exists but only plays a secondary role in the size distribution of deletions and insertions. (5) The linear gap penalty, which is most commonly used in sequence alignment, is not supported by our analysis; rather, the power law for the size distribution of indels suggests that an appropriate gap penalty is w(k) = a + b In k, where a is the gap creation cost and b1nk is the gap extension cost. (6) The higher frequency of deletion over insertion suggests that the gap creation cost of insertion (a(i)) should be larger than that of deletion (a(d)); that is, a(i) - a(d) = In R, where R is the frequency ratio of deletions to insertions.