| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-03-11 15:00 可変長圧縮基準によるテキストの頻出文字列検出 ○岡本勇人・井上真郷（早大）  NC2009-170 |
|
| 抄録 | （和） | 様々な生物種のゲノムDNA 配列やタンパク質のアミノ酸配列等から，頻出する部分を抽出し，遺伝暗号を解く手掛かりとすることは有用であると思われる．本研究では，長い一次元のシンボル列データから，頻出する部分シンボル列を抽出するという一般的なアルゴリズムを考案した．Huffman 符号や算術符号は，シンボルの出現頻度のみを手掛かりとして情報源符号化を行う．シンボルをk 個毎に纏めたk 次拡大情報源は，シンボルの並びが独立でなければ，拡大すればする程平均符号長は短くなることが期待される．一方，頻度テーブルの記述サイズは指数的に増大する．この拡大情報源は，独立な並びの部分でも一纏めにしてしまうという欠点や，先頭からk シンボル毎に纏められるため，フレームシフトに対応できないという欠点がある．提案手法ではこれらを解決し，隣り合う二つのシンボルを纏めて新しい一つのシンボルと見做すか否かを圧縮基準に基づき，逐次的，貪欲的に行うとした．この際に纏められたシンボル列を，有意に頻出する部分シンボル列と解釈することができる．本手法を，DNA 配列データ等に対して適用し，比較検証した． |
| （英） | Extracting frequently-appearing subsequences from genome DNA sequences or amino-acid sequences of proteins of various species would be useful for understanding their genetic codes. In this study, we have developed a general algorithm that extracts frequent-appearing subsequences from a given long symbol sequence. The algorithm is based on the Huffman code or the arithmetic code, which utilize only the probability distribution of symbols for compression. It also utilizes the idea of k-th order extended sources. Specifically, the algorithm puts consecutive two frequent-appearing symbols together and registers them as a new symbol. Such registrations are done iteratively and in greedy manner based on compressed file size. Finally, the combined symbol sequences can be considered as frequent subsequences. We applied this algorithm to real DNA sequence and validated it. |
|
| キーワード | （和） | 頻出文字列 / 算術符号 / 頻出パターンマイニング / 可変長圧縮 / / / / |
| （英） | Frequent strings / Arithmetic code / Frequent pattern mining / Variable-length coding / / / / | |
| 文献情報 | 信学技報, vol. 109, no. 461, NC2009-170, pp. 485-489, 2010年3月. | |
| 資料番号 | NC2009-170 | |
| 発行日 | 2010-03-02 (NC) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NC2009-170 |
|
| 研究会情報 | |
| 研究会 | NC MBE |
| 開催期間 | 2010-03-09 - 2010-03-11 |
| 開催地（和） | 玉川大学 |
| 開催地（英） | Tamagawa University |
| テーマ（和） | 一般 |
| テーマ（英） | General |
| 講演論文情報の詳細 | |
| 申込み研究会 | NC |
| 会議コード | 2010-03-NC-MBE |
| 本文の言語 | 日本語 |
| タイトル（和） | 可変長圧縮基準によるテキストの頻出文字列検出 |
| サブタイトル（和） | |
| タイトル（英） | Frequent String Detection by Variable Length Coding |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 頻出文字列 / Frequent strings |
| キーワード(2)（和/英） | 算術符号 / Arithmetic code |
| キーワード(3)（和/英） | 頻出パターンマイニング / Frequent pattern mining |
| キーワード(4)（和/英） | 可変長圧縮 / Variable-length coding |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 岡本 勇人 / Hayato Okamoto / オカモト ハヤト |
| 第1著者 所属（和/英） | 早稲田大学 (略称： 早大) Waseda University (略称： Waseda Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 井上 真郷 / Masato Inoue / イノウエ マサト |
| 第2著者 所属（和/英） | 早稲田大学 (略称： 早大) Waseda University (略称： Waseda Univ.) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2010-03-11 15:00:00 |
| 発表時間 | 25分 |
| 申込先研究会 | NC |
| 資料番号 | NC2009-170 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.461 |
| ページ範囲 | pp.485-489 |
| ページ数 | 5 |
| 発行日 | 2010-03-02 (NC) |
[研究会発表申込システムのトップページに戻る]