Towards improved assessment of functional similarity in large-scale screens: a study on indel length

Although insertions and deletions are a common type of evolutionary sequence variation, their origins and their functional consequences have not been comprehensively understood. Most alignment algorithms/programs only roughly reflect the evolutionary processes that result in gaps--which typically require further evaluation. Interestingly, it is widely believed that gaps are the predominant form of sequence variation resulting in structural and functional changes. Thus it is desirable to distinguish between gaps that reflect true point mutations and alignment artifacts when it comes to assessing the functional similarity of proteins based on computational alignments. Here we introduce pair hidden Markov model-based solutions to rapidly assess the statistical significance of gaps in alignments resulting from classical Needleman-Wunsch-like alignment procedures which implement affine gap penalty scoring schemes. Surprisingly, although it has a natural formulation, the emanating Markov chain problem had no known efficient solution thus far. In this article, we present the first efficient algorithm to solve it. We demonstrate that, when comparing paralogous protein pairs (from Escherichia coli) of equal alignment identity and similarity, alignments that contain gaps of significant length are significantly less similar in terms of functionality, as measured with respect to Gene Ontology (GO) term similarity. This demonstrates for the first time, in a formally sound manner, that insertions and deletions cause more severe functional changes between proteins than substitutions. Our method can be reliably employed to quickly filter alignment outputs for protein pairs that are more likely to be functionally similar and/or divergent and establishes a sound and useful add-on for large-scale alignment studies.