The Huck Institutes of the Life Sciences

Computations 19x faster with new adaptive algorithm

Researchers using a new algorithmic process for a heuristic embedding strategy they call "Adaptive GDDA-BLAST" can now see the results of their computations 19 times faster than with their previous computational method. The new method has the added benefits of detecting structural homology in highly divergent protein sequences and isolating secondary structural elements of transmembrane and ankyrin-repeat domains, with possibly wide-ranging impacts on human health and disease studies.

One of the major challenges faced by biologists is how to identify the relation between highly divergent protein sequences. In general, when pairwise sequence identity between protein sequences fall below the 25% identity, statistical measurements do not clearly identify phylogenetic relations, structural features or protein functions. GDDA-BLAST (Gestalt Domain Detection Algorithm - Basic Local Alignment Search Tool), was originally designed to address these challenges but due to the length of protein sequences and the need to insert “seed” information at every position of the query sequence, it was prohibitive in nature.


Adaptive GDDA-BLAST works 19 times faster by exploiting similarities among embedded sequences. Instead of inserting a seed into every position of a query sequence, Adaptive GDDA-BLAST embeds a seed at the query positions where the seed is likely to be extended to an alignment. Costly computations are thus avoided.


The researchers believe that the alignment information that can be discovered using this method will have broad impacts on human health and disease, as well as basic science endeavours. In addition, the theories behind these algorithms are also likely to have applications in other fields that use pattern-based prediction algorithms.


The research team included Damian van Rossum, Director of the Center for Comparative Proteomics, and his colleague at the Center, Yoojin Hong. It was partially funded by the Huck Institutes.


Read the full article.