Mining non-contiguous mutation chain in biological sequences based on 3D-structure

Abstract

Understanding how an infectious agent mutates from one form to another can provide insights into the mechanisms of disease pathogenesis and epidemiology. Existing methods of sequence analysis which focus on identifying regions of similarity may help explain functional or henotypic variability. However, these approaches do not take into account the spatio-temporal dynamics of virus evolution. Recently, Sheng et. al [42] introduced an approach that incorporated spatio-temporal information to analyze mutation chains in influenza A proteomes. However, this work was restricted to mining contiguous subsequences of mutations, not taking into account the practical 3D-structure of the protein.

In this thesis, we generalize the definition for mutation chain to allow for mining of non-contiguous mutations. We design an efficient algorithm, termed ptMutationChian-Miner, to search for non-contiguous mutation chains in influenza A proteomes. This algorithm utilizes three pruning strategies local hot positions, valid Mutation Space and increment join to reduce the search space. Experiments on both synthetic and real world influenza A virus datasets show that the algorithm is effective in discovering non-continuous mutations that occur geographically over time.