Pengembangan Quantum Pattern Matching untuk Pencarian Pola DNA pada Whole Genome Sequencing

Mahdi, Muhammad Alfan (2026) Pengembangan Quantum Pattern Matching untuk Pencarian Pola DNA pada Whole Genome Sequencing. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025221275-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (8MB) | Request a copy

Abstract

Pertumbuhan data Whole Genome Sequencing (WGS) yang pesat membuat algoritma pencarian klasik seperti Knuth-Morris Pratt dan Boyer-Moore kurang optimal untuk pencarian pola DNA berskala besar, khususnya dalam validasi desain guide RNA (gRNA) untuk menghindari efek off-target. Algoritma Grover menawarkan percepatan kuadratik, namun penerapannya pada perangkat Noisy Intermediate-Scale Quantum (NISQ) masih dibatasi jumlah qubit dan kedalaman sirkuit yang rentan noise. Tugas akhir ini mengembangkan metode quantum pattern matching hibrida kuantum-klasik yang menggabungkan teknik Tiled Search untuk memecah teks DNA panjang menjadi blok-blok tumpang tindih sesuai kapasitas qubit, dengan mekanisme Anchor-Verify, yaitu pencarian prefiks pendek pola secara kuantum yang diverifikasi ulang secara klasik untuk mengeliminasi false positive. Metode dibangun dalam satu iterasi Algoritma Grover dengan dua varian oracle Hamming distance, berbasis Adder dan berbasis Quantum Fourier Transform (QFT), dengan ambang batas mismatch yang dapat dikonfigurasi sehingga mendukung baik exact maupun approximate pattern matching. Evaluasi pada simulator Qiskit Aer bebas noise terhadap panjang teks 132–4.100 karakter dan ukuran window 16–64 posisi, serta validasi terbatas pada 50 sekuens gRNA Sorghum WGS, menunjukkan trade-off antara efisiensi dan akurasi. Oracle QFT unggul dalam efisiensi qubit, depth, dan jumlah gerbang, sementara oracle Adder unggul signifikan dalam precision dan recall. Konfigurasi window 16 posisi memberikan keseimbangan terbaik antara akurasi dan waktu eksekusi, membuktikan kelayakan pendekatan hibrida kuantum-klasik berbasis Tiled Search dan Anchor-Verify sebagai solusi praktis pencarian pola DNA aproksimasi pada era NISQ.
=========================================================================================================================================
The rapid growth of Whole Genome Sequencing (WGS) data makes classical search algorithms such as Knuth-Morris-Pratt and Boyer-Moore less than optimal for large-scale DNA pattern searching, especially in the validation of guide RNA (gRNA) designs to avoid off-target effects. Grover's algorithm offers quadratic speedup, but its application on Noisy Intermediate-Scale Quantum (NISQ) devices is still limited by the number of qubits and the depth of circuits that are susceptible to noise. This final project develops a quantum-classical hybrid quantum pattern matching method that combines the Tiled Search technique to break down long DNA texts into overlapping blocks according to qubit capacity, with the Anchor-Verify mechanism, which is a quantum search for short pattern prefixes that are re-verified classically to eliminate false positives. The method is built in one iteration of the Grover Algorithm with two variants of the Hamming distance oracle, Adder-based and Quantum Fourier Transform (QFT)-based, with a configurable mismatch threshold that supports both exact and approximate pattern matching. Evaluation on a noise-free Qiskit Aer simulator across text lengths of 132–4,100 characters and window sizes of 16–64 positions, with limited validation on 50 real Sorghum WGS gRNA sequences, demonstrates a trade-off between efficiency and accuracy. The QFT oracle excels in qubit efficiency, depth, and number of gates, while the Adder oracle significantly excels in precision and recall. The 16 position window configuration provides the best balance between accuracy and execution time, proving the feasibility of the Tiled Search and Anchor-Verify-based quantum-classical hybrid approach as a practical solution for approximate DNA pattern search in the NISQ era.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Algoritma Grover, Bioinformatika, Hamming Distance, NISQ, Quantum Pattern Matching, Bioinformatics, Grover’s Algorithm, Hamming Distance, NISQ, Quantum Pattern Matching.
Subjects:	Q Science > QA Mathematics > QA336 Artificial Intelligence Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Muhammad Alfan Mahdi
Date Deposited:	25 Jul 2026 08:00
Last Modified:	25 Jul 2026 08:00
URI:	http://repository.its.ac.id/id/eprint/138143

Actions (login required)

View Item