Welcome to the InfoSci Platform
Quantum Computing Approach for Alignment-Free Sequence Search and Classification

Quantum Computing Approach for Alignment-Free Sequence Search and Classification

Rao M. Kotamarti, Mitchell A. Thornton, Margaret H. Dunham
Copyright: © 2012 |Pages: 22
ISBN13: 9781466618305|ISBN10: 1466618302|EISBN13: 9781466618312
DOI: 10.4018/978-1-4666-1830-5.ch017
Cite Chapter Cite Chapter

MLA

Kotamarti, Rao M., et al. "Quantum Computing Approach for Alignment-Free Sequence Search and Classification." Multidisciplinary Computational Intelligence Techniques: Applications in Business, Engineering, and Medicine, edited by Shawkat Ali, et al., IGI Global, 2012, pp. 279-300. https://doi.org/10.4018/978-1-4666-1830-5.ch017

APA

Kotamarti, R. M., Thornton, M. A., & Dunham, M. H. (2012). Quantum Computing Approach for Alignment-Free Sequence Search and Classification. In S. Ali, N. Abbadeni, & M. Batouche (Eds.), Multidisciplinary Computational Intelligence Techniques: Applications in Business, Engineering, and Medicine (pp. 279-300). IGI Global. https://doi.org/10.4018/978-1-4666-1830-5.ch017

Chicago

Kotamarti, Rao M., Mitchell A. Thornton, and Margaret H. Dunham. "Quantum Computing Approach for Alignment-Free Sequence Search and Classification." In Multidisciplinary Computational Intelligence Techniques: Applications in Business, Engineering, and Medicine, edited by Shawkat Ali, Noureddine Abbadeni, and Mohamed Batouche, 279-300. Hershey, PA: IGI Global, 2012. https://doi.org/10.4018/978-1-4666-1830-5.ch017

Export Reference

Mendeley
Favorite

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.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.