ゲノム配列からの高次圧縮・クラスタリングによる知識発見
ゲノム配列からの高次圧縮・クラスタリングによる知識発見
通过基因组序列的高阶压缩和聚类发现知识
批准号：
12208012
负责人：
稲葉 真理
金额：
$0.0万
依托单位：
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas (C)
财政年份：
2000
资助国家：
日本
项目状态：
已结题
起止时间：
2000 至 --
中文摘要
翻译
DNA配列,たんぱく質配列に対する高圧縮率な圧縮アルゴリズムを開発した.既存の手法ではLZ77圧縮法を元にし,配列中のあいまい一致や回文構造を利用したものが用いられていたが,これと文脈木重み付け法を組み合わせることでDNAに対する圧縮率を改善できた.またたんぱく質に関しては既存の手法ではほとんど圧縮できていなかったが,文脈木重み付け法とあいまい一致を考慮したLZ77法を組み合わせることで高い圧縮率を達成できた.またLZ77圧縮のためのハッシュや接尾辞配列を用いた高速なアルゴリズムも考案した.ゲノム配列データベースは巨大になっているが,これを圧縮したまま高速に検索するデータ構造を考案した.これは接尾辞配列を圧縮したものを用いており,データベース全体を走査することなく任意の文字列を検索できる.またデータベース中の任意の部分を高速に復元するアルゴリズムや,データマイニングで用いられる索引をコンパクトに格納する方法を考案した.実験により,圧縮された配列や文書と,検索のための索引のサイズの合計を元の文書のサイズより小さくできることを示した.このデータ構造を用いてゲノム配列中のあいまい一致を高速に求めるアルゴリズムなどを実現できるため,類似配列の検索などのさまざまな演算を効率よく行うことができる.
英文摘要
DNA配列,たんぱく質配列に対する高圧縮率な圧縮アルゴリズムを開発した.既存の手法ではLZ77圧縮法を元にし,配列中のあいまい一致や回文構造を利用したものが用いられていたが,これと文脈木重み付け法を組み合わせることでDNAに対する圧縮率を改善できた.またたんぱく質に関しては既存の手法ではほとんど圧縮できていなかったが,文脈木重み付け法とあいまい一致を考慮したLZ77法を組み合わせることで高い圧縮率を達成できた.またLZ77圧縮のためのハッシュや接尾辞配列を用いた高速なアルゴリズムも考案した.ゲノム配列データベースは巨大になっているが,これを圧縮したまま高速に検索するデータ構造を考案した.これは接尾辞配列を圧縮したものを用いており,データベース全体を走査することなく任意の文字列を検索できる.またデータベース中の任意の部分を高速に復元するアルゴリズムや,データマイニングで用いられる索引をコンパクトに格納する方法を考案した.実験により,圧縮された配列や文書と,検索のための索引のサイズの合計を元の文書のサイズより小さくできることを示した.このデータ構造を用いてゲノム配列中のあいまい一致を高速に求めるアルゴリズムなどを実現できるため,類似配列の検索などのさまざまな演算を効率よく行うことができる.
期刊论文(6)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
K.Sadakane: "Compressed Text Databases with Efficient Query Algorithms based on the Compressed Suffix Array"Proceedings of ISAAC'00, Lecture Notes in Computer Science. 1969. 410-421 (2000)
K.Sadakane：“基于压缩后缀数组的具有高效查询算法的压缩文本数据库”ISAAC00 会议记录，计算机科学讲义。
K.Sadakane：“基于压缩后缀数组的具有高效查询算法的压缩文本数据库”ISAAC00 会议记录，计算机科学讲义。
DOI：
--
发表时间：
期刊：
影响因子：
--
作者：
[]
通讯作者：
T.Matsumoto,K.Sadakane and H.Imai: "Biological Sequence Compression Algorithms"Genome Informatics 2000. 43-52 (2000)
T.Matsumoto、K.Sadakane 和 H.Imai：“生物序列压缩算法”基因组信息学 2000. 43-52 (2000)
T.Matsumoto、K.Sadakane 和 H.Imai：“生物序列压缩算法”基因组信息学 2000. 43-52 (2000)
DOI：
--
发表时间：
期刊：
影响因子：
--
作者：
[]
通讯作者：
定兼邦彦: "圧縮接尾辞配列に関する考察"情報処理学会SIGDBS. (2000)
Kunihiko Sadakane：“压缩后缀数组的研究”日本信息处理协会 SIGDBS（2000）。
Kunihiko Sadakane：“压缩后缀数组的研究”日本信息处理协会 SIGDBS（2000）。
DOI：
--
发表时间：
期刊：
影响因子：
--
作者：
[]
通讯作者：
K.Sadakane: "Algorithms on Strings based on the Compressed Suffix Arrays"情報処理学会SIGAL. (2000)
K. Sadakane：“基于压缩后缀数组的字符串算法”日本信息处理协会 SIGAL (2000)。
K. Sadakane：“基于压缩后缀数组的字符串算法”日本信息处理协会 SIGAL (2000)。
DOI：
--
发表时间：
期刊：
影响因子：
--
作者：
[]
通讯作者：
M.Inaba,N.Katoh and H.Imai: "Variance-Based κ-Clustering Algorithms by Voronoi Diagrams and Randomization"IEICE Trans.Information and Systems. E83-D,6. 1199-1206 (2000)
M.Inaba、N.Katoh 和 H.Imai：“Voronoi 图和随机化的基于方差的 κ 聚类算法”IEICE Trans.Information and Systems，1199-1206 (2000)。
M.Inaba、N.Katoh 和 H.Imai：“Voronoi 图和随机化的基于方差的 κ 聚类算法”IEICE Trans.Information and Systems，1199-1206 (2000)。
DOI：
--
发表时间：
期刊：
影响因子：
--
作者：
[]
通讯作者：
共 6 条
SAT(充足可能性)問題の並列局所探索アルゴリズムの研究と超並列計算機への実装
-
批准号：11F01807
-
项目类别：Grant-in-Aid for JSPS Fellows
-
资助金额：$1.28万
-
财政年份：2011
-
负责人：稲葉 真理
-
依托单位：
ゲノム配列からの高次圧縮・クラスタリングによる知識発見
-
批准号：13208002
-
项目类别：Grant-in-Aid for Scientific Research on Priority Areas (C)
-
资助金额：$2.56万
-
财政年份：2000
-
负责人：稲葉 真理
-
依托单位：
幾可構造を利用した高次クラスタリングアルゴリズムの研究およびその応用
-
批准号：09780247
-
项目类别：Grant-in-Aid for Encouragement of Young Scientists (A)
-
资助金额：$1.28万
-
财政年份：1997
-
负责人：稲葉 真理
-
依托单位：
海外基金