劣線形時間アルゴリズムグループ

ビッグデータを対象とする劣線形時間アルゴリズムの基盤創出

本研究拠点では，ビッグデータに向けた新しい計算パラダイム，「劣線形時間アルゴリズム」パラダイムを提唱し，その理論的基礎となるアルゴリズムとデータ 構造設計技術を構築し，ビッグデータ時代に向けた革新的アルゴリズム基盤として整備する．特に，様々な実問題を解く際にサブルーチンとして頻出する基礎的 な探索問題，最適化問題，列挙問題に対して，確率，近似，サンプリングなどの既知の技法をビッグデータ用に深化させることにより，線形，あるいは，劣線形 時間のアルゴリズム開発をおこなう．さらに，これらのアルゴリズムを最速避難計画や避難所への割り当てなどの避難計画問題，組合せ剛性理論によるたんぱく 質の機能解明の研究を中心とした実問題に対し適用する．

線形時間アルゴリズムの開発

本研究では，組合せ最適化の問題の中で多項式時間アルゴリズムの存在が知られている基本問題に対して，確率的アプローチ，近似の概念を用いて線形時間̃ Õ(n) (=O(npolylogn)) のアルゴリズムを構築する．なかでも，最大流問題，最小費用流問題などのネットワーク問題，劣モジュラー関数最小化問題などの離散最適化問題や，剛性理論に応用のある (k，l)-疎グラフ認識問題などに焦点を当て，アルゴリズムを開発する．より実用性を高めるために，ヒューリスティックアルゴリズムの適用も含めてアルゴリズムの高速化を図る．たとえば，劣モジュラー関数最大化問題はNP困難であるが，近似比 (1-1/e) の貪欲アルゴリズムが知られており，このアルゴリズムは高速なのでビッグデータにも対応できる．一方で，劣モジュラー関数最小化問題は組合せ問題の基本問題として応用も数多くあり，多項式時間アルゴリズムが知られているが，時間計算量は O(n⁶) で，複雑で実装も難しく，ビッグデータに対応できない．本研究の重要な応用課題である避難計画に現れる最速避難問題が，劣モジュラー最小化問題に帰着され ることもあり，劣モジュラー関数最小化問題に対する線形時間アルゴリズムの開発は，理論上，応用上重要な問題である．

劣線形・定数時間アルゴリズムの開発

劣線形・定数時間アルゴリズムは，データのほんの一部，すなわち o(n) あるいは定数だけの量のデータを見るだけで問題を解こうという枠組みである．特に定数時間アルゴリズムは，対象物がいかに巨大でも一定量のデータしか見な いのであるから，ビッグデータを扱うのに理想的な手法である．しかし，これまでの研究は黎明期でもあり，理論的な興味に基づくものがほとんどであったた め，計算時間も定数とはいっても，定数パラメータによる指数のタワーといった非現実的なものが多く見られた．定数時間アルゴリズムの計算量が近似パラメー タに対しどのような関数で表現されるかが，定数時間アルゴリズムの実用化を考える際重要であるが，系統的，網羅的な研究はこれまで行われていない．

本研究では，ビッグデータ応用という実用的視点から，定数パラメータの多項式で表現される計算時間を持つアルゴリズムを開発し，このようなアルゴリズムの 可能性とその限界について明らかにしていく．具体的には，ネットワークの特性を利用した高速定数時間アルゴリズムを開発し，定数時間アルゴリズムの実用可 能性を実験的に検証を行う．

漸進型アルゴリズム

ビッグデータを扱うために，最初は少ないデータからおおよその性質を算出し，そして徐々にデータ量を増やしながら段々と結果の精度を上げていく，という手法が考えられる．すなわち，まず定数個のデータを読み込んで大まかな性質を計算し，次に O(logn)個，さらに O(√n) 個，といった具合にデータの量を増やしていき，時間的・資源的余裕に応じて正確な結果を得るのである．我々はこの手法を漸進型アルゴリズム (progressive algorithms) と呼び，本研究では漸進型アルゴリズムの理論基盤を構築し，その有効性を実験的に示すとともに，漸進型アルゴリズムの設計方法を開発する．

避難計画問題

災害発生時にできるだけ混雑を起こさないように，多くの人々をできるだけ安全な場所に早く逃がすことが避難計画における最大の目標である．現在，スマート フォンやカーナビ等の携帯端末が普及しており，情報通信技術を積極的に活用した避難誘導手法が模索・実践される動きがある．現在の方法は，携帯電話等の位 置情報デバイスから最寄りの避難場所をガイドする，といったごく簡単な仕組みであり，適切な避難経路・場所の選択の問題が解消できていない．全体的に効率 的な避難を達成するためには，どこにどれだけの避難者が存在するのか，さらにどの経路が安全なのかといった情報を大規模かつリアルタイムに収集・加工し， 集められたビッグデータをネットワークモデルなどに置き換えて，理論的に裏付けのある方法で高速に解き，最適な避難経路や避難場所を決定する必要がある．

本研究では，今後予想される南海地震により大きな津波被害が予想される近畿圏（大阪や和歌山など）を具体的な対象地域として選定し，避難計画で必要となる リアルタイムなデータ収集・加工の技術と理論的な避難計画モデルの開発・実装を行い，対象地域において検証を行う．

具体的には，地下街避難の問題および避 難所の地域への割り当ての問題，津波からの広域避難の問題に取り組む．地下街避難の問題では，時間拡大ネットワークの研究を発展させ，大規模なネットワー クモデルの開発と検証を行う．避難所割り当て問題に対しては，大規模な地域を対象とした割当のための近似解法を，劣線形モデリンググループと共同で開発する．津波からの広域避難の問題では，南 海トラフ地震による大阪湾沿岸地域への津波浸水の高精度なシミュレーションを行う．そして，そのデータを使って，時間と共に通行可能な箇所が変化する時間 拡大ネットワークを構築し，構築された大規模な時間拡大ネットワークを効率的に解くために，本プロジェクトで開発する最大流問題の改良型アルゴリズム等を 実装し，検証を行う．

組合せ剛性理論によるタンパク質の機能解明

たんぱく質の深い理解は，生物学・医学・創薬分野において非常に重要であるが，そのためには，たんぱく質の挙動を知る必要がある．タンパク質の挙動を知る ための実験は非常に大きなコストと時間がかかり，また，分子動力学に基づく計算手法は，非常に多くの計算時間を要し，実用的ではない．一方，剛性理論分野 における最近の進歩により，たんぱく質の柔軟性及び挙動について，非常に高速かつ正確に挙動予測をおこなうことができ，たんぱく質挙動解析の分野に多くの 進展がもたらされている．
本研究は，本グループで開発する劣線形時間アルゴリズムを基礎に，既存のアルゴリズムの改善をおこない，劣線形データ構造グループと連携しながら，巨大 スケールのたんぱく質の挙動を明らかにする手法の開発をおこなう．具体的には，剛性理論の手法を用いることにより，従来捉えることが困難であった，たんぱ く質アロステリ，GPCRの挙動解明を中心に焦点を当てて，たんぱく質の挙動と機能の関係性を調査する．

メンバー

氏名	所属	役割
加藤 直樹	兵庫県立大学　情報科学研究科	全体総括
東川 雄哉	兵庫県立大学　情報科学研究科	研究メンバー
笹嶋 宗彦	兵庫県立大学　情報科学研究科	研究メンバー
照山 順一	兵庫県立大学　情報科学研究科	研究メンバー
玉置 卓	兵庫県立大学　情報科学研究科	研究メンバー
Tsunehiko Kameda	Simon Fraser University	研究メンバー
大島 裕明	兵庫県立大学　情報科学研究科	研究メンバー
伊藤 大雄	電気通信大学　情報理工学研究科	研究メンバー
長尾 篤樹	お茶の水女子大学　基幹研究院自然科学系	研究メンバー
瀧澤 重志	大阪市立大学　生活科学研究科	研究メンバー
小林 祐貴	大阪市立大学　工学研究科	研究メンバー
牧野 和久	京都大学　数理解析研究所	研究メンバー
宇野 裕之	大阪府立大学　工学研究科	研究メンバー
斎藤 寿樹	九州工業大学　情報工学研究院	研究メンバー
宮野 英次	九州工業大学　情報工学研究院	研究メンバー
藤本 晶子	九州工業大学　情報工学研究院	研究メンバー
巳波 弘佳	関西学院大学　工学部	研究メンバー
土村 展之	関西学院大学　工学部	研究メンバー
Adnan Sljoka	理化学研究所	研究メンバー
Michael Williamson	Department of Molecular Biology and Biotechnology, University of Sheffield	研究メンバー
Shin Isogai	Center for Molecular Life Sciences, University of Basel	研究メンバー
高橋 克郎	兵庫県立大学	リサーチアシスタント
千葉 恭平	電気通信大学	リサーチアシスタント
馬場 崇仁	大阪市立大学	リサーチアシスタント
戸國 友貴	兵庫県立大学	リサーチアシスタント
増田 康佑	兵庫県立大学	リサーチアシスタント