著者
阿久津 達也 深川 大路 高須 淳宏
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
巻号頁・発行日
vol.106, no.63, pp.17-24, 2006-05-17

木の類似度の尺度として、木の編集距離が20年以上前に提案され、それ以来、多くの研究が行われてきた。順序木に対する編集距離計算アルゴリズムとしては(入力の木のサイズをO(n)として)O(n^3 logn)のものが現時点で最速であるが、文字列の編集距離がO(n^2)時間で計算できることが知られている。そこで本研究では、木を文字列に変換して文字列の編集距離を計算することにより、木の編集距離を近似する方法を提案する。そして、入力される木の次数が限定されており、かつ、編集操作には単位コストがかかるという場合には、木の編集距離が変換後の文字列の編集距離の1/6以上かつ、O(n^<3/4>)以下となることを示す。
著者
阿久津 達也 永持 仁 細川 浩
出版者
京都大学
雑誌
基盤研究(A)
巻号頁・発行日
2018-04-01

今年度は以下の研究を行った。(1) ニューラルネットワークについての原像問題に取り組み、学習した階層型ニューラルネットワークに対し、出力ベクトルから入力ベクトルを求める問題を混合整数線形問題(MILP)として定式化し、MILPソルバーを用いて入力ベクトルを計算する手法を開発した。この手法を実装し、Core i5 1.8GHz CPU上でCPLEXソルバーを用いた予備的な計算機実験を行った結果、入力層が200頂点、中間層(一層)が200頂点、出力層が1頂点の場合に2秒以内で計算結果を得ることができた。(2) ニューラルネットワークの応用面についても研究を行い、遺伝子発現データと他の情報を統合して解析するための2種類の手法を開発した。一つは遺伝子発現データとタンパク質相互作用ネットワークデータを統合して解析する手法であり、タンパク質相互作用ネットワークデータをグラフらプラシアンを用いて2次元点集合に変換し、遺伝子発現データを対応する点の強度とすることにより、各サンプルのデータを画像データとして扱えるようにし、それに対し深層学習による画像解析技法を適用することにより腫瘍細胞の分類を行う。もう一つは遺伝子発現データと遺伝子間の進化的距離を統合して解析する手法であり、進化的距離データに多次元尺度構成法を適用することにより各遺伝子を2次元点集合に変換し、前者と同様の手法を適用することにより、腫瘍細胞のサブタイプの分類を行う。いずれも公開データから取得した遺伝子発現データを用いた計算機実験により、その有用性を示した。(3) 木構造に対する離散原像問題に取り組む事前研究として、無順序木の包含問題(Unordered Tree Inclusion)問題の計算量改善に取り組み、最大次数に関する指数時間依存性を改良することに成功した。
著者
阿久津 達也 ホセ・カルロス ナチェル・ディエズ
出版者
一般社団法人 日本生物物理学会
雑誌
生物物理 (ISSN:05824052)
巻号頁・発行日
vol.47, no.2, pp.086-092, 2007 (Released:2007-03-31)
参考文献数
17

Many real systems can be described as networks, composed of a set of nodes and a set of edges connecting the nodes. Interestingly, it has been found that most real networks have a common architecture, termed scale-free or broad-tail topology. Here we review key well-established concepts in network science: small world, scale-free network and network motif, with special emphasis on biological networks. Key mechanisms responsible for the emergence of the scale-free property are discussed along with a simple evolutionary model of protein-protein interaction networks.
著者
熊野 颯 阿久津 達也
出版者
一般社団法人 人工知能学会
雑誌
人工知能学会全国大会論文集 第33回全国大会(2019)
巻号頁・発行日
pp.3K3J202, 2019 (Released:2019-06-01)

従来から、機械学習モデルの表現能力に関する研究が行われてきた。例えば、ニューラルネットワークにおいては、ネットワークの深さによってノード数の観点から効率よく関数を表現できる場合があることが知られている。一方、ランダムフォレストにおけるノード数に関する効率性の有無は不明である。そこで、本研究ではランダムフォレストにおけるノード数に関する効率性の有無について考察する。まず、ランダムフォレストはニューラルネットワークと全く同種の効率性は持たないことを示す。次に、ランダムフォレストを構成する決定木の本数からノード数に関する効率性が生じる場合があることを示す。
著者
百武 稔郎 阿久津 達也
雑誌
全国大会講演論文集
巻号頁・発行日
vol.48, pp.395-396, 1994-03-07

人間の遺伝子のDNA配列を全て解析し、そこに書かれている情報の意味を明らかにしようとするヒトゲノム計画が現在進められている。DNA配列の意味を解明する上で、DNA配列パターンとDNA配列がコード化するタンパク質立体構造パターンの関係を調べることは重要な役割を果たす。そこで、本研究では、タンパク質立体構造の解析を支援するために、強力なパターンマッチング機能やグラフィック表示機能を備えたタンパク質データベース・システムであるPROTEIX(PROTEIn database system on uniX)を開発している。本稿では、複雑なコマンドなどを覚えなくても種々の操作が容易に行えるユーザインターフェース部を開発したので報告する。このユーザインターフェース部は、GUIであるOSF/Motifを用いて構築を行い、タンパク質データの選択、立体構造の拡大縮小、部分構造の表示、マッチング情報の表示などの操作がマウスのみを用いて行えるようになっている。
著者
Jindalertudomdee Jira 林田 守広 趙 楊 阿久津 達也
出版者
公益社団法人 日本化学会・情報化学部会
雑誌
ケモインフォマティクス討論会予稿集 第37回情報化学討論会 豊橋
巻号頁・発行日
pp.O12, 2014 (Released:2014-11-20)
参考文献数
3

本研究ではこれまで開発してきた幅優先探索順の列挙手法を拡張し,各原子の数とナフタレン環の数を入力として,ナフタレン環を一つのノードに縮約したときに木構造となる化学構造を重複なくすべて列挙する手法を提案する.よく知られた列挙ツールであるMOLGENといくつかの入力に対して実行時間を比較し,閉路としてナフタレン環のみを含む場合に提案手法の実行効率が優れていることを示す.
著者
林田守広 阮佩穎 阿久津達也
雑誌
研究報告数理モデル化と問題解決(MPS)
巻号頁・発行日
vol.2014-MPS-100, no.11, pp.1-2, 2014-09-18

生物は進化の過程において,突然変異や組み換えなどによって DNA の塩基配列情報を変化させながらも自らの生命を維持させてきた.生物の持つ情報を DNA の塩基配列とすると,この配列を圧縮することによって大体の情報量を知ることができる.本研究では塩基配列の代わりにタンパク質ドメイン構成に基づき,個体の持つすべてのタンパク質について圧縮する.遺伝子重複や遺伝子融合などの進化現象により同じドメイン構成を持つタンパク質が複数生成されるとすると,複製元のタンパク質を参照することでデータ量を減らすことができる.このような参照によるネットワークは有向ハイパーグラフとなり,多数の参照候補を持つグラフから最小大域木を見つけることで圧縮する.しかし現実的な時間での,ハイパーグラフからの最小大域木の抽出は困難であるので,前処理としてハイパーエッジを削減する発見的な手法を提案する.本手法を数種の生物種に適用した結果,タンパク質進化における遺伝子融合の重要性が示唆された.
著者
阿久津 達也
出版者
一般社団法人情報処理学会
雑誌
情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)
巻号頁・発行日
vol.1993, no.88, pp.27-34, 1993-10-01
被引用文献数
1

文字列の近似マッチング・アルゴリズムとしてLandauとVishkinによるアルゴリズムが良く知られている。本稿では彼らのアルゴリズムを基に開発した、Don't Care記号付き文字列に対する逐次および並列の近似マッチング・アルゴリズムを示す。なお、nをテキスト文字列の長さ、mをパターン文字列の長さ、Σを文字集合、kを許容誤差とした場合に、逐次アルゴリズムはO(√<km> n log|Σ|log^2 m/k log log m/) 時間で動作し、並列アルゴリズムはCRCW?PRAM上でO(√<m/k> n log|Σ|log m/k log log m/)個のプロセッサを用いてO( log )時間で動作する。さらに、より拡張した文字列パターンに対する近似マッチング・アルゴリズムも示す。This paper presents parallel and serial approximate matching algorithms for strings with don't care characters. They are based on the approximate string matching algorithm developed by Landau and Vishkin. The serial algorithm works in O(√<km> n log|Σ|log^2 m/k log log m/k) time and the parallel algorithm works in O(k log m) time using O(√<m/k> n log|Σ|log m/k log log m/k)processors on a CRCW-PRAM, where n denotes the length of a text string, m denotes the length of a pattern string k denotes the maximum number of differences and Σ denotes the alphabet (i.e. the set of characters). Several extensions of algorithms are described, too.
著者
ジェービー・ブラウン 阿久津 達也
出版者
一般社団法人情報処理学会
雑誌
情報処理学会研究報告バイオ情報学(BIO) (ISSN:09196072)
巻号頁・発行日
vol.2007, no.89, pp.49-56, 2007-09-14

DNA 修復とは、紫外線や複製ミスなどの細胞損傷を修復するプロセスである。細胞の機能を維持する役割は大切だと思われているが、以前の DNA 修復研究はバイオインフォマティクスでほとんど行われていない。そこで、我々は機械学習を用いて、DNA 修復タンパク質の識別と分類という基本的な問題に取り組む。結果として機械学習によってうまく識別と分類ができるということを示す。DNA repair is a critical process in cells, repairing internal and external damage resulting from UV radiation and DNA replication errors, to name only a few. Despite its important role, bioinformatics research on DNA repair is limited. In this talk, we examine two basic problems for the application of bioinformatics to DNA repair: detection of DNA repair-related proteins, and subsequent classification. Results will show that machine learning techniques are highly capable in these two tasks.
著者
プンサップ・アンヤーニー 加藤有己 阿久津 達也
出版者
一般社団法人情報処理学会
雑誌
情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)
巻号頁・発行日
vol.2007, no.128, pp.137-142, 2007-12-21

生体高分子の機能の解明にはその折り畳み構造を理解する必要があるとされている.特に,機能的非コード RNA が注目を集めている.RNA の立体構造を予測することは困難であるため,シュードノットを含む,または含まない2次構造を予測する研究が行われてきた.本稿では,整数計画法を2次構造予測に適用する手法を提案する.ここで,シュードノットを含まない構造と,任意の平面的シュードノット構造を予測するための2つの定式化を導入する.さらに,提案手法を使った構造予測に関するいくつかの実験結果を示す.Understanding the function of biological molecules requires knowledge of their folded structures. In particular, noncoding functional RNAs have received much attention. Due to the difficulty in predicting the three dimensional structure of RNA, research efforts have shifted to the prediction of secondary structure both with and without pseudoknots. In this paper, we present a method of applying integer programming (IP) to RNA secondary structure prediction. We introduce respective IP formulations for predicting pseudoknot-free structure as well as arbitrary planar pseudoknotted structure. Furthermore, we show some experimental results on structure prediction using the proposed method.