Search

Traditional genome alignment methods based on dynamic programming are often a. computational expensive, b. unable to compare the genomes of distant species and c. unable to deal with low information regions. We are presenting an information-theoretic approach for pairwise genome local alignment. Our method, the expert model aligner, the XMAligner, relies on the expert model compression algorithm. To align two sequences, XMAligner first compresses one sequence to measure the information content at each position in the sequence. Then the sequence is compressed again but this time with the background knowledge from the other sequence to obtain the conditional information content. The information content and the conditional information content from the two compressions are examined. Similar regions in the compressed sequence should have the conditional information content lower than the individual information content. The method is applied to align the genomes of Plasmodium falciparum and Plasmodium knowlesi against other three Plasmodium genomes with different levels of diversity. Despite the differences in nucleotide composition of the reference sequences, the conserved regions found by XMAligner in three alignments are relatively consistent. A strong correlation was found between the similar regions detected by the XMAligner and the hypothetical annotation of Plasmodium species. The alignment results can be integrated into the DNAPlatform for visualisation.

This paper introduces a novel algorithm for biological sequence compression that makes use of both statistical properties and repetition within sequences by maintaining a panel of experts to predict the probability distribution of the next symbol in the sequence to be encoded. Expert probabilities are combined to obtain the final distribution. Experiments show that our algorithm outperforms existing compressors on typical DNA and protein sequence datasets while maintaining a practical running time. The resulting information sequence provides insight for further study of the biological sequence. We demonstrate a number pattern discovery tasks using our model.