Quantum Computing Approach for Alignment-Free Sequence Search and Classification

View Sample PDF

Author(s): Rao M. Kotamarti (Southern Methodist University, USA), Mitchell A. Thornton (Southern Methodist University, USA)and Margaret H. Dunham (Southern Methodist University, USA)
Copyright: 2013
Pages: 22
Source title: Bioinformatics: Concepts, Methodologies, Tools, and Applications
Source Author(s)/Editor(s): Information Resources Management Association (USA)
DOI: 10.4018/978-1-4666-3604-0.ch090

Keywords: Bioinformatics / Medical Information Science Reference / Medicine & Healthcare

Purchase

View Quantum Computing Approach for Alignment-Free Sequence Search and Classification on the publisher's website for pricing and purchasing information.

Abstract

Many classes of algorithms that suffer from large complexities when implemented on conventional computers may be reformulated resulting in greatly reduced complexity when implemented on quantum computers. The dramatic reductions in complexity for certain types of quantum algorithms coupled with the computationally challenging problems in some bioinformatics problems motivates researchers to devise efficient quantum algorithms for sequence (DNA, RNA, protein) analysis. This chapter shows that the important sequence classification problem in bioinformatics is suitable for formulation as a quantum algorithm. This chapter leverages earlier research for sequence classification based on Extensible Markov Model (EMM) and proposes a quantum computing alternative. The authors utilize sequence family profiles built using EMM methodology which is based on using pre-counted word data for each sequence. Then a new method termed quantum seeding is proposed for generating a key based on high frequency words. The key is applied in a quantum search based on Grover algorithm to determine a candidate set of models resulting in a significantly reduced search space. Given Z as a function of M models of size N, the quantum version of the seeding algorithm has a time complexity in the order of as opposed to O(Z) for the standard classic version for large values of Z.

The IRMA Community

Research IRM

Quantum Computing Approach for Alignment-Free Sequence Search and Classification

Purchase

Abstract

Related Content

IRMA Sponsors