Quasi alignment methods for molecular sequence analysis.

摘要

Next generation sequencing has made it possible to extend genomic analysis to complete genomes. However, the classic alignment methods are computationally expensive for large genomic analyses resulting in either cost or performance challenges. Alignment-free methods do not rely on the need for aligning several sequences, but derive much analysis using the number of occurrences of sub-sequence patterns along the sequences. This allows the alignment-free analysis to be computationally more efficient than the classic alignment methods and this offers scalability for the growing use of large sequences such as complete genomes. Within the class of alignmentfree methods, this research introduces quasi alignment methods for building sequence signatures based on Extensible Markov Models (EMM). By applying data mining concepts, the EMM signatures serve as profile models for communities of related sequences applicable for representing a hierarchical organization of a taxonomy. This work proposes new methods for taxonomic classification, verification and phylogenetic relationships along with statistical significance reporting based on the adapted Karlin-Altschul framework. Several published papers with experiments based on the 16S rRNA of the microbial organisms are presented. The research further improves the new method using quantum computing frame work to reduce the search time.