Quantum algorithm for position weight matrix matching

• Item type: SIG Technical Reports(1)
• 公開日: 2023-03-06
• タイトル: Quantum algorithm for position weight matrix matching
• タイトル / 言語: en
• タイトル: Quantum algorithm for position weight matrix matching
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Center for Quantum Information and Quantum Biology, Osaka University
• 著者所属: Department of Applied Physics and Physico-Informatics, Keio University／Quantum Computing Center, Keio University
• 著者所属: Department of Biosciences and Informatics, Keio University／Quantum Computing Center, Keio University
• 著者所属(英): en
• 著者所属(英): Center for Quantum Information and Quantum Biology, Osaka University
• 著者所属(英): en
• 著者所属(英): Department of Applied Physics and Physico-Informatics, Keio University / Quantum Computing Center, Keio University
• 著者所属(英): en
• 著者所属(英): Department of Biosciences and Informatics, Keio University / Quantum Computing Center, Keio University
• 著者名: Koichi, Miyamoto; Naoki, Yamamoto; Yasubumi, Sakakibara
• 著者名(英): Koichi, Miyamoto; Naoki, Yamamoto; Yasubumi, Sakakibara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We propose two quantum algorithms for a problem in bioinformatics, position weight matrix (PWM) matching, which aims to find segments (sequence motifs) in a biological sequence such as DNA and protein that have high scores defined by the PWM and are thus of informational importance related to biological function. The two proposed algorithms, the naive iteration method and the Monte-Carlo-based method, output matched segments, given the oracular accesses to the entries in the biological sequence and the PWM. The former uses quantum amplitude amplification (QAA) for sequence motif search, resulting in the query complexity scaling on the sequence length n, the sequence motif length m and the number of the PWMs K as O(m√Kn), which means speedup over existing classical algorithms with respect to n and K. The latter also uses QAA, and further, quantum Monte Carlo integration (QMCI) for segment score calculation instead of iterative arithmetic operations in the naive iteration method; then it provides the additional speedup with respect to m in some situation. As a drawback, these algorithms use quantum random access memories and their initialization takes O(n) time. Nevertheless, our algorithms keep the advantage especially when we search matches in a sequence for many PWMs in parallel.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose two quantum algorithms for a problem in bioinformatics, position weight matrix (PWM) matching, which aims to find segments (sequence motifs) in a biological sequence such as DNA and protein that have high scores defined by the PWM and are thus of informational importance related to biological function. The two proposed algorithms, the naive iteration method and the Monte-Carlo-based method, output matched segments, given the oracular accesses to the entries in the biological sequence and the PWM. The former uses quantum amplitude amplification (QAA) for sequence motif search, resulting in the query complexity scaling on the sequence length n, the sequence motif length m and the number of the PWMs K as O(m√Kn), which means speedup over existing classical algorithms with respect to n and K. The latter also uses QAA, and further, quantum Monte Carlo integration (QMCI) for segment score calculation instead of iterative arithmetic operations in the naive iteration method; then it provides the additional speedup with respect to m in some situation. As a drawback, these algorithms use quantum random access memories and their initialization takes O(n) time. Nevertheless, our algorithms keep the advantage especially when we search matches in a sequence for many PWMs in parallel.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12894105
• 書誌情報: 研究報告量子ソフトウェア（QS）; 巻 2023-QS-8, 号 32, p. 1-10, 発行日 2023-03-06
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2435-6492
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会