Sequence length variation, indel costs, and congruence in sensitivity analysis

The behavior of two topological and four character‐based congruence measures was explored using different indel treatments in three empirical data sets, each with different alignment difficulties. The analyses were done using direct optimization within a sensitivity analysis framework in which the cost of indels was varied. Indels were treated either as a fifth character state, or strings of contiguous gaps were considered single events by using linear affine gap cost. Congruence consistently improved when indels were treated as single events, but no congruence measure appeared as the obviously preferable one. However, when combining enough data, all congruence measures clearly tended to select the same alignment cost set as the optimal one. Disagreement among congruence measures was mostly caused by a dominant fragment or a data partition that included all or most of the length variation in the data set. Dominance was easily detected, as the character‐based congruence measures approached their optimal value when indel costs were incremented. Dominance of a fragment or data partition was overwhelmed when new sequence length‐variable fragments or data partitions were added. © The Willi Hennig Society 2005.     

Size, frequency, and phylogenetic signal of multiple-residue indels in sequence alignment of introns

Indels in DNA sequences frequently affect more than a single nucleotide, creating problems for alignment, character coding and phylogenetic analysis. However, the size and frequency of multiple‐residue indels is not usually tested, and with popular alignment packages their reconstruction is indirectly acheived by reducing the affine (gap extension) cost. We explored the length distribution of indels in intron sequences of the gene Mp20 by modifying the gap opening and gap extension costs. Given a “known” tree for the study group, global homology levels were greatest under low gap cost, with gap extension costs of roughly 0.4‐fold the opening cost. Different approaches to gap coding and weighting suggested that taxonomic congruence was correlated with high frequencies of multiple‐position indels, with a maximum indel length of 2–5 bp and few indels above 15 bp, but also including a proportion of indels > 100 bp. Only a small minority of indels could be reconstructed as single‐position indels. Consequently, tree topologies improved when homologous multinucleotide indels were recoded as binary characters which are otherwise highly homoplastic and weighted characters in single‐position coding. In tree‐generating alignment procedures as implemented in POY, where gap penalty determines the character weight during tree search, the problem of assigning inappropriately high weight to multiple‐residue indels could partly be overcome by setting the extension costs to about 0.4‐fold lower than gap opening costs. We conclude that multiple consecutive gap positions are not independent characters and hence methods for parsimony reconstruction of long indels are required. Finally, we also observed a general lack of correlation between taxonomic and character congruence, demonstrating the difficulties of applying congruence criteria to decide among competing alignments. This highlights the value of recent model‐based alignment procedures which can implement the statistical distributions of indel size classes, and do not rely on potentially circular strategies for optimizing overall congruence. © The Willi Hennig Society 2006.     

Sequence alignments and pair hidden Markov models using evolutionary history

This work presents a novel pairwise statistical alignment method based on an explicit evolutionary model of insertions and deletions (indels). Indel events of any length are possible according to a geometric distribution. The geometric distribution parameter, the indel rate, and the evolutionary time are all maximum likelihood estimated from the sequences being aligned. Probability calculations are done using a pair hidden Markov model (HMM) with transition probabilities calculated from the indel parameters. Equations for the transition probabilities make the pair HMM closely approximate the specified indel model. The method provides an optimal alignment, its likelihood, the likelihood of all possible alignments, and the reliability of individual alignment regions. Human alpha and beta-hemoglobin sequences are aligned, as an illustration of the potential utility of this pair HMM approach.     

Indel seeds for homology search

We are interested in detecting homologous genomic DNA sequences with the goal of locating approximate inverted, interspersed, and tandem repeats. Standard search techniques start by detecting small matching parts, called seeds, between a query sequence and database sequences. Contiguous seed models have existed for many years. Recently, spaced seeds were shown to be more sensitive than contiguous seeds without increasing the random hit rate. To determine the superiority of one seed model over another, a model of homologous sequence alignment must be chosen. Previous studies evaluating spaced and contiguous seeds have assumed that matches and mismatches occur within these alignments, but not insertions and deletions (indels). This is perhaps appropriate when searching for protein coding sequences (<5% of the human genome), but is inappropriate when looking for repeats in the majority of genomic sequence where indels are common. In this paper, we assume a model of homologous sequence alignment which includes indels and we describe a new seed model, called indel seeds, which explicitly allows indels. We present a waiting time formula for computing the sensitivity of an indel seed and show that indel seeds significantly outperform contiguous and spaced seeds when homologies include indels. We discuss the practical aspect of using indel seeds and finally we present results from a search for inverted repeats in the dog genome using both indel and spaced seeds.     

Morphology versus molecules: the phylogenetic relationships of Sepsidae (Diptera: Cyclorrhapha) based on morphology and DNA sequence data from ten genes

The Sepsidae is, with approximately 300 described species, a relatively small family of cyclorrhaphan flies whose behaviour, morphology, and development have been extensively studied. However, currently the only available tree for Sepsidae is more than 10 years old and was based entirely on morphological characters. Here, we present the results of parsimony and Bayesian analyses based on 75 species, ten genes, and morphology. Parsimony and Bayesian analyses produce largely congruent and well‐supported topologies regardless of whether indels are coded as 5th character states, as missing values, or all sites with indels are removed. The tree confirms the monophyly of Sepsidae and identifies the Ropalomeridae as its sister group. With regard to higher‐level relationships, we identify widespread conflict between the morphological and the DNA sequence data. The proposed hypothesis based on both partitions largely reflects the signal in the molecular data. Particularly surprising is the rejection of two relationship hypotheses with strong morphological support, namely the sister group relationship between Orygma and the remaining Sepsidae and the monophyly of the Sepsis species group. Our partitioned Bremer support (PBS) analyses imply that indel coding has a stronger effect on the relative performance of individual gene partitions than the exclusion of alignment‐ambiguous sequences or the location of a gene on the mitochondrial or nuclear genome. However, these analyses also reveal unexpectedly strong fluctuations in PBS values given that indel treatment has only a minor effect on tree topology and jacknife support. These unexpected fluctuations highlight the need for a comparative study across multiple data sets that investigates the influence of conflict and indel treatment on PBS values. © The Willi Hennig Society 2008.     

Optimal intron analyses in the trimeresurus radiation of Asian pitvipers

Nuclear introns are commonly used as phylogenetic markers, but a number of issues related to alignment strategies, indel treatments, and the incorporation of length-variant heterozygotes (LVHs) are not routinely addressed when generating phylogenetic hypotheses. Topological congruence in relation to an extensive mitochondrial DNA multigene phylogeny (derived from 2,423 bp of 12S, 16S, ND4, and CYTB genes) of the Asian pitviper Trimeresurus radiation was used to compare combinations of "by eye" and edited and unedited ClustalX 1.8 alignments of two nuclear introns. Indels were treated as missing data, fifth character states, and assigned simple and multistate codes. Upon recovery of the optimal alignment and indel treatment strategy, a total evidence approach was used to investigate the phylogenetic utility of the indels and test new generic arrangements within Trimeresurus. Approximately one third of the intron data partitions exhibited LVHs, suggesting that they are common in introns. Furthermore, a simple concatenation approach can facilitate the incorporation of LVHs into phylogenetic analyses to make use of all available data and investigate mechanisms of molecular evolution. Analyses of ClustalX 1.8-assisted alignments were generally more congruent than the "by eye" alignment and the analysis of a simple coded, edited ClustalX 1.8 (gap opening cost 5, gap extension cost 1) alignment revealed the most congruent tree. The total evidence approach supported the new arrangements within Trimeresurus, suggesting that the phylogeny should be considered as a working benchmark in Asian pitviper systematics. Finally, a critical appraisal of the diverse array of indels (56 to 57 per intron, ranging from 1 to 151 bp in length) suggested that they are a combination of Hennigian and homoplasious events unrelated to indel size or location within the intron. [Alignment; indels; intron analysis; length-variant heterozygotes; Trimeresurus.].     

SATe-II: very fast and accurate simultaneous estimation of multiple sequence alignments and phylogenetic trees

Highly accurate estimation of phylogenetic trees for large data sets is difficult, in part because multiple sequence alignments must be accurate for phylogeny estimation methods to be accurate. Coestimation of alignments and trees has been attempted but currently only SATé estimates reasonably accurate trees and alignments for large data sets in practical time frames (Liu K., Raghavan S., Nelesen S., Linder C.R., Warnow T. 2009b. Rapid and accurate large-scale coestimation of sequence alignments and phylogenetic trees. Science. 324:1561-1564). Here, we present a modification to the original SATé algorithm that improves upon SATé (which we now call SATé-I) in terms of speed and of phylogenetic and alignment accuracy. SATé-II uses a different divide-and-conquer strategy than SATé-I and so produces smaller more closely related subsets than SATé-I; as a result, SATé-II produces more accurate alignments and trees, can analyze larger data sets, and runs more efficiently than SATé-I. Generally, SATé is a metamethod that takes an existing multiple sequence alignment method as an input parameter and boosts the quality of that alignment method. SATé-II-boosted alignment methods are significantly more accurate than their unboosted versions, and trees based upon these improved alignments are more accurate than trees based upon the original alignments. Because SATé-I used maximum likelihood (ML) methods that treat gaps as missing data to estimate trees and because we found a correlation between the quality of tree/alignment pairs and ML scores, we explored the degree to which SATé's performance depends on using ML with gaps treated as missing data to determine the best tree/alignment pair. We present two lines of evidence that using ML with gaps treated as missing data to optimize the alignment and tree produces very poor results. First, we show that the optimization problem where a set of unaligned DNA sequences is given and the output is the tree and alignment of those sequences that maximize likelihood under the Jukes-Cantor model is uninformative in the worst possible sense. For all inputs, all trees optimize the likelihood score. Second, we show that a greedy heuristic that uses GTR+Gamma ML to optimize the alignment and the tree can produce very poor alignments and trees. Therefore, the excellent performance of SATé-II and SATé-I is not because ML is used as an optimization criterion for choosing the best tree/alignment pair but rather due to the particular divide-and-conquer realignment techniques employed.     

Molecular phylogenetics of the lizard genus Microlophus (squamata:tropiduridae): aligning and retrieving indel signal from nuclear introns

We use a multigene data set (the mitochondrial locus and nine nuclear gene regions) to test phylogenetic relationships in the South American "lava lizards" (genus Microlophus) and describe a strategy for aligning noncoding sequences that accounts for differences in tempo and class of mutational events. We focus on seven nuclear introns that vary in size and frequency of multibase length mutations (i.e., indels) and present a manual alignment strategy that incorporates insertions and deletions (indels) for each intron. Our method is based on mechanistic explanations of intron evolution that does not require a guide tree. We also use a progressive alignment algorithm (Probabilistic Alignment Kit; PRANK) and distinguishes insertions from deletions and avoids the "gapcost" conundrum. We describe an approach to selecting a guide tree purged of ambiguously aligned regions and use this to refine PRANK performance. We show that although manual alignment is successful in finding repeat motifs and the most obvious indels, some regions can only be subjectively aligned, and there are limits to the size and complexity of a data matrix for which this approach can be taken. PRANK alignments identified more parsimony-informative indels while simultaneously increasing nucleotide identity in conserved sequence blocks flanking the indel regions. When comparing manual and PRANK with two widely used methods (CLUSTAL, MUSCLE) for the alignment of the most length-variable intron, only PRANK recovered a tree congruent at deeper nodes with the combined data tree inferred from all nuclear gene regions. We take this concordance as an objective function of alignment quality and present a strongly supported phylogenetic hypothesis for Microlophus relationships. From this hypothesis we show that (1) a coded indel data partition derived from the PRANK alignment contributed significantly to nodal support and (2) the indel data set permitted detection of significant conflict between mitochondrial and nuclear data partitions, which we hypothesize arose from secondary contact of distantly related taxa, followed by hybridization and mtDNA introgression.     

Graph-based modeling of tandem repeats improves global multiple sequence alignment

Tandem repeats (TRs) are often present in proteins with crucial functions, responsible for resistance, pathogenicity and associated with infectious or neurodegenerative diseases. This motivates numerous studies of TRs and their evolution, requiring accurate multiple sequence alignment. TRs may be lost or inserted at any position of a TR region by replication slippage or recombination, but current methods assume fixed unit boundaries, and yet are of high complexity. We present a new global graph-based alignment method that does not restrict TR unit indels by unit boundaries. TR indels are modeled separately and penalized using the phylogeny-aware alignment algorithm. This ensures enhanced accuracy of reconstructed alignments, disentangling TRs and measuring indel events and rates in a biologically meaningful way. Our method detects not only duplication events but also all changes in TR regions owing to recombination, strand slippage and other events inserting or deleting TR units. We evaluate our method by simulation incorporating TR evolution, by either sampling TRs from a profile hidden Markov model or by mimicking strand slippage with duplications. The new method is illustrated on a family of type III effectors, a pathogenicity determinant in agriculturally important bacteria Ralstonia solanacearum. We show that TR indel rate variation contributes to the diversification of this protein family.     

Evolutionary distances in the twilight zone--a rational kernel approach

Phylogenetic tree reconstruction is traditionally based on multiple sequence alignments (MSAs) and heavily depends on the validity of this information bottleneck. With increasing sequence divergence, the quality of MSAs decays quickly. Alignment-free methods, on the other hand, are based on abstract string comparisons and avoid potential alignment problems. However, in general they are not biologically motivated and ignore our knowledge about the evolution of sequences. Thus, it is still a major open question how to define an evolutionary distance metric between divergent sequences that makes use of indel information and known substitution models without the need for a multiple alignment. Here we propose a new evolutionary distance metric to close this gap. It uses finite-state transducers to create a biologically motivated similarity score which models substitutions and indels, and does not depend on a multiple sequence alignment. The sequence similarity score is defined in analogy to pairwise alignments and additionally has the positive semi-definite property. We describe its derivation and show in simulation studies and real-world examples that it is more accurate in reconstructing phylogenies than competing methods. The result is a new and accurate way of determining evolutionary distances in and beyond the twilight zone of sequence alignments that is suitable for large datasets.     

Incorporating indels as phylogenetic characters: Impact for interfamilial relationships within Arctoidea (Mammalia: Carnivora)

Insertion and deletion events (indels) provide a suite of markers with enormous potential for molecular phylogenetics. Using many more indel characters than those in previous studies, we here for the first time address the impact of indel inclusion on the phylogenetic inferences of Arctoidea (Mammalia: Carnivora). Based on 6843 indel characters from 22 nuclear intron loci of 16 species of Arctoidea, our analyses demonstrate that when the indels were not taken into consideration, the monophyly of Ursidae and Pinnipedia tree and the monophyly of Pinnipedia and Musteloidea tree were both recovered, whereas inclusion of indels by using three different indel coding schemes give identical phylogenetic tree topologies supporting the monophyly of Ursidae and Pinnipedia. Our work brings new perspectives on the previously controversial placements among Arctoidea families, and provides another example demonstrating the importance of identifying and incorporating indels in the phylogenetic analyses of introns. In addition, comparison of indel incorporation methods revealed that the three indel coding methods are all advantageous over treating indels as missing data, given that incorporating indels produces consistent results across methods. This is the first report of the impact of different indel coding schemes on phylogenetic reconstruction at the family level in Carnivora, which indicates that indels should be taken into account in the future phylogenetic analyses.     

Molecular systematics of teioid lizards (Teioidea/Gymnophthalmoidea: Squamata) based on the analysis of 48 loci under tree‐alignment and similarity‐alignment

We infer phylogenetic relationships within Teioidea, a superfamily of Nearctic and Neotropical lizards, using nucleotide sequences. Phylogenetic analyses relied on parsimony under tree‐alignment and similarity‐alignment, with length variation (i.e. gaps) treated as evidence and as absence of evidence, and maximum‐likelihood under similarity‐alignment with gaps as absence of evidence. All analyses produced almost completely resolved trees despite 86% of missing data. Tree‐alignment produced the shortest trees, the strict consensus of which is more similar to the maximum‐likelihood tree than to any of the other parsimony trees, in terms of both number of clades shared, parsimony cost and likelihood scores. Comparisons of tree costs suggest that the pattern of indels inferred by similarity‐alignment drove parsimony analyses on similarity‐aligned sequences away from more optimal solutions. All analyses agree in a majority of clades, although they differ from each other in unique ways, suggesting that neither the criterion of optimality, alignment nor treatment of indels alone can explain all differences. Parsimony rejects the monophyly of Gymnophthalmidae due to the position of Alopoglossinae relative to Teiidae, whereas support of Gymnophthalmidae by maximum‐likelihood was low. We address various nomenclatural issues, including Gymnophthalmidae Fitzinger, 1826 being an older name than Teiidae Gray, 1827. We recognize three families in the arrangement Alopoglossidae + (Teiidae + Gymnophthalmidae). Within Gymnophthalmidae we recognize Cercosaurinae, Gymnophthalminae, Rhachisaurinae and Riolaminae in the relationship Cercosaurinae + (Rhachisaurinae + (Riolaminae + Gymnophthalminae)). Cercosaurinae is composed of three tribes—Bachiini, Cercosaurini and Ecpleopodini—and Gymnophthalminae is composed of three—Gymnophthalmini, Heterodactylini and Iphisini. Within Teiidae we retain the currently recognized three subfamilies in the arrangement: Callopistinae + (Tupinambinae + Teiinae). We also propose several genus‐level changes to restore the monophyly of taxa.     

Diatom phylogenetics inferred based on direct optimization of nuclear-encoded SSU rRNA sequences

Direct optimization (DO) of 126 nuclear‐encoded SSU rRNA diatom sequences was conducted. The optimal phylogeny indicated several unique relationships with respect to those recovered from a maximum likelihood (ML) analysis of an alignment based on maximizing primary and secondary structural similarity between 126 nuclear‐encoded SSU rRNA diatom sequences ( Medlin and Kaczmarska, 2004 ). Dividing diatoms into the subdivisions Coscinodiscophytina and Bacillariophytina was not supported by the DO phylogeny, due to the paraphyly of the former. The same pertains to Coscinodiscophyceae, Mediophyceae, Thalassiosira, Fragilaria and Amphora. The ordinal‐level classification of the diatoms proposed by Round et al. (1990 ) was for the most part found to be unsupported. The DO phylogeny represented a more rigorous hypothesis than the ML tree because DO maximized character congruence during the homology testing (i.e., alignment/tree search) process whereas the non‐phylogenetic similarity‐based alignment used in the ML analysis did not. The above statement is supported by “controlled” parsimony analyses of 35 sequences, which strongly suggested that dissimilarities in the DO and ML tree structure were due to the specific homology testing approach used. It could not be precluded that differences in taxon sampling and the use of a dissimilar optimality criteria contributed to discrepancies in the structure of the optimal ML and DO trees.     

Joint Bayesian estimation of alignment and phylogeny

We describe a novel model and algorithm for simultaneously estimating multiple molecular sequence alignments and the phylogenetic trees that relate the sequences. Unlike current techniques that base phylogeny estimates on a single estimate of the alignment, we take alignment uncertainty into account by considering all possible alignments. Furthermore, because the alignment and phylogeny are constructed simultaneously, a guide tree is not needed. This sidesteps the problem in which alignments created by progressive alignment are biased toward the guide tree used to generate them. Joint estimation also allows us to model rate variation between sites when estimating the alignment and to use the evidence in shared insertion/deletions (indels) to group sister taxa in the phylogeny. Our indel model makes use of affine gap penalties and considers indels of multiple letters. We make the simplifying assumption that the indel process is identical on all branches. As a result, the probability of a gap is independent of branch length. We use a Markov chain Monte Carlo (MCMC) method to sample from the posterior of the joint model, estimating the most probable alignment and tree and their support simultaneously. We describe a new MCMC transition kernel that improves our algorithm's mixing efficiency, allowing the MCMC chains to converge even when started from arbitrary alignments. Our software implementation can estimate alignment uncertainty and we describe a method for summarizing this uncertainty in a single plot.     

Characterization of pairwise and multiple sequence alignment errors

We characterize pairwise and multiple sequence alignment (MSA) errors by comparing true alignments from simulations of sequence evolution with reconstructed alignments. The vast majority of reconstructed alignments contain many errors. Error rates rapidly increase with sequence divergence, thus, for even intermediate degrees of sequence divergence, more than half of the columns of a reconstructed alignment may be expected to be erroneous. In closely related sequences, most errors consist of the erroneous positioning of a single indel event and their effect is local. As sequences diverge, errors become more complex as a result of the simultaneous mis-reconstruction of many indel events, and the lengths of the affected MSA segments increase dramatically. We found a systematic bias towards underestimation of the number of gaps, which leads to the reconstructed MSA being on average shorter than the true one. Alignment errors are unavoidable even when the evolutionary parameters are known in advance. Correct reconstruction can only be guaranteed when the likelihood of true alignment is uniquely optimal. However, true alignment features are very frequently sub-optimal or co-optimal, with the result that optimal albeit erroneous features are incorporated into the reconstructed MSA. Progressive MSA utilizes a guide-tree in the reconstruction of MSAs. The quality of the guide-tree was found to affect MSA error levels only marginally.     

Measuring the fit of sequence data to phylogenetic model: allowing for missing data

It is fundamentally important to assess the fit of data to model in phylogenetic and evolutionary studies. Phylogenetic methods using molecular sequences typically start with a multiple alignment. It is possible to measure the fit of data to model expectations of data, for example, via the likelihood-ratio (G) test or the X(2) test, if all sites in all sequences have an unambiguous residue. However, nearly all alignments of interest contain sites (columns of the alignment) with missing data, that is, ambiguous nucleotides, gaps, or unsequenced regions, which must presently be removed before using the above tests. Unfortunately, this is often either undesirable or impractical, as it will discard much of the data. Here, we show how iterative ML estimators may directly estimate the site-pattern probabilities for columns with missing data, given only standard i.i.d. assumptions. The optimization may use an EM or Newton algorithm, or any other hill-climbing approach. The resulting optimal likelihood under the unconstrained or multinomial model may be compared directly with the likelihood of the data coming from the model (a G statistic). Alternatively the modified observed and the expected frequencies of site patterns may be compared using a X(2) test. The distribution of such statistics is best assessed using appropriate simulations. The new method is applicable to models using codons or paired sites. The methods are also useful with Hadamard conjugations (spectral analysis) and are illustrated with these and with ML evolutionary models that allow site-rate variability.     

Probabilistic whole-genome alignments reveal high indel rates in the human and mouse genomes

MOTIVATION: The two mutation processes that have the largest impact on genome evolution at small scales are substitutions, and sequence insertions and deletions (indels). While the former have been studied extensively, indels have received less attention, and in particular, the problem of inferring indel rates between pairs of divergent sequence remains unsolved. Here, I describe a novel and accurate method for estimating neutral indel rates between divergent pairs of genomes. RESULTS: Simulations suggest that new method for estimating indel rates is accurate to within 2%, at divergences corresponding to that of human and mouse. Applying the method to these species, I show that indel rates are up to twice higher than is apparent from alignments, and depend strongly on the local G + C content. These results indicate that at these evolutionary distances, the contribution of indels to sequence divergence is much larger than hitherto appreciated. In particular, the ratio of substitution to indel rates between human and mouse appears to be around gamma = 8, rather than the currently accepted value of about gamma = 14.     

Phylogenetic analysis of Themira (Sepsidae: Diptera): sensitivity analysis, alignment, and indel treatment in a multigene study

In this study we use sensitivity analysis sensu Wheeler (1995 ) for a matrix entirely composed of DNA sequences. We propose that not only congruence but also phylogenetic structure, as measured by character resampling, should be used to choose among competing weighting regimes. An extensive analysis of a five‐gene data set for Themira (Sepsidae: Diptera) reveals that even with different ways of partitioning the data, measures of topological congruence, character incongruence, and phylogenetic structure favor similar weighting regimes involving the down‐weighting of transitions. We furthermore use sensitivity analysis for obtaining empirical evidence that allows us to select weights for third positions, deciding between treating indels as fifth character states or missing values, and choosing between manual and computational alignments. For our data, sensitivity analysis favors manual alignment over a Clustal‐generated numerical alignment, the treatment of indels as fifth character states over considering them missing values, and equal weights for all positions in protein‐encoding genes over the down‐weighting of third positions. Among the topological congruence measures compared, symmetric tree distance performed best. Partitioned Bremer Support analysis reveals that COI contributes the largest amount of support for our phylogenetic tree for Themira. © The Willi Hennig Society 2005.     

Empirical analysis of protein insertions and deletions determining parameters for the correct placement of gaps in protein sequence alignments

To understand how protein segments are inserted and deleted during divergent evolution, a set of pairwise alignments contained exactly one gap, and therefore arising from the first insertion-deletion (indel) event in the time separating the homologs, was examined. The alignments showed that "structure breaking" amino acids (PGDNS) were preferred within and flanking gapped regions, as are two residues with hydrophilic side-chains (QE) that frequently occur at the surface of protein folds. Conversely, hydrophobic residues (FMILYVW) occur infrequently within and flanking the gapped region. These preferences are modestly different in protein pairs separated by an episode of adaptive evolution, than in pairs diverging under strong functional constraints. Surprisingly, regions near an indel have not evolved more rapidly than the sequence pair overall, showing no evidence that an indel event must be compensated by local amino acid replacement. The gap-lengths are best approximated by a Zipfian distribution, with the probability of a gap of length L decreasing as a function of L(-1.8). These features are largely independent of the length of the gap and the extent of divergence (measured by both silent and non-silent sequence changes) separating the two proteins. Surprisingly, amino acid repeats were discovered in more than a third of the polypeptide segments in and around the gap. These correspond to repeats in the DNA sequence. This suggests that a signature of the mechanism by which indels occur in the DNA sequence remains in the encoded protein sequences. These data suggest specific tools to score gap placement in an alignment. They also suggest tools that distinguish true indels from gaps created by mistaken gene finding, including under-predicted and over-predicted introns. By providing mechanisms to identify errors, the tools will enhance the value of genome sequence databases in support of integrated paleogenomics strategies used to extract functional information in a post-genomic environment.