2024-03-29T00:16:53Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000588922023-04-27T10:00:04Z01164:05352:05353:05356
Neighborhood hashing for enumerating all frequent patterns allowing errors近傍ハッシュ法によるエラー許容頻出パターン列挙enghttp://id.nii.ac.jp/1001/00058892/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=58892&item_no=1&attribute_id=1&file_no=1Copyright (c) 2008 by the Information Processing Society of Japan京都大学九州大学情報学研究所筑波大学名古屋大学橋本, 英樹小野, 廣隆宇野, 毅明漆原, 秀子柳浦睦憲ゲノム配列から,ある機能発現に関わる遺伝子を発見したいという要望がある.このような遺伝子は対象となるゲノム配列集合においてエラーを含んだ形で頻出する配列パターンの形をとることがしばしばある.本研究では,エラーを含む文字列集合から,ある長さの頻出部分文字列パターンを高速に全列挙するアルゴリズムを提案する.エラーの影響から通常のパターン列挙と異なり,入力文字列には現れないパターンも列挙の対象となる.提案手法ではパターン頻出性の必要条件を利用して最小限の候補パターンをハッシュ格納することにより,高速な全列挙を実現する.We propose a practically fast algorithm that enumerates all m-length substring patterns appearing in at least θ sequences among a given set of string sequences, where at most k errors are allowed for each appearance. The problem of enumerating such substring patterns is derived from the genome science, where frequent substring patterns allowing errors are candidates of a gene related to a certain function. From this context, some pattern should be enumerated even if it does not appear in any sequence, because it may match a sufficient number of sequences by allowing errors. In order to prevent overlooking such potential patterns, we propose a hash-based enumeration algorithm. The algorithm stores not only a substring pattern appearing in a sequence but also its neighboring patterns. By using several techniques/conditions to exclude non-frequent patterns, our algorithm achieves an efficient enumeration of frequent substring patterns allowing errors.AA12055912情報処理学会研究報告バイオ情報学(BIO)200858(2008-BIO-013)63662008-06-192009-06-30