In the post-genomic era, an exponential number of biological data are being produced at an accelerating pace by high-throughput technologies and avail- able via online databases on the Internet. Among these, binary relationship data that can be described as sets of elements and 1-to-1 associations (connections) between them have become increasingly common. Co-expressed gene pairs and protein-protein interactions exemplify this data type. Network (graph) visualization, where nodes and edges correspond to the elements and the connections respectively, is widely used for representing binary relationship data because it is expected to be more interpretable than a long list of associations. However, when network data are large and complicated (e.g., >100 edges), the. network representations often become cluttered with jumbles of nodes and edges, known as "hair-balls", and thus fail to convey information effectively. Therefore, one of the key challenges is how to develop network navigation approaches that can abstract data properly and interactively, and visualize the data insightfully at a right level of detail. By such methods, researchers would beable to explore and interpret their large-scale networks much more effectively. Until recently, many studies have used various methods to tackle the cluttered-visualization problem, but still cannot obtain satisfactory results-truly clean and intuitive visualizations.

Hierarchical clustering is a technique that meaningfully and recursively groups data elements based on a similarity measure, thereby, producing a hierarchy or tree of clusters. This method works with many types of data, including networks, to create groups of data elements in a multi-scale fashion. In the hierarchy, higher levels contain fewer, larger clusters with more data elements, or nodes it case of networks, than lower levels. Such a hierarchy can be applied to abstract the network visualization by showing only high- level clusters, thereby reducing the number of elements on the screen. By showing the actual members of each cluster at a certain level of the hierarchy, detailed information can be displayed at a particular scale. However, existing network visualization methods' that offer such multi-scale navigation still have some drawbacks that hinder scientists from effectively and interactively exploring large biological network data, namely, (1) uses of clustering that depends upon user-provided information about hierarchies, (2)long running time (e.g., minutes to hours) required to abstract large networks, (3) inflexibility in navigation beyondfixed cluster boundaries, and (4) insufficiency of data abstraction, which leads to still cluttered network drawings.

In this dissertation, I present the first interactive, multi-scale navigation method for large and complicated biological networks and demonstrate its application to two types of functional genomics data, a yeast protein net- work dataset and an Arabidopsis gene co- expression dataset. The method is mainly composed of an ultrafast graph clustering technique that rapidly abstracts networks of about 100,000 nodes by recursively grouping densely connected portions and a biological-property-based clustering technique that uses property information provided for biological entities (e.g., Gene Ontology (GO) terms). It can rapidly and automatically abstract any region of large network data and produce biologically meaningful visualization with a manageable amount of' information at all levels of detail. Apart from untangling large and complicated biological networks, it can be used to discoved hidden knowledge in the networks readily and effectively as well. The method was first implemented as a stand-alone Java Swing application named NaviCluster (http://navicluster.cb.k.u-tokyo.ac.jp) and then integrated with Cytoscape as a plug-in, named NaviClusterCS (http://navicluster.cb.k.u-tokyo.ac.jp/cs/), to gain benefits from its usability and abundant useful features. I believe that the presented method will aid modern biologists in discovering knowledge from massive binary-relationship datasets more efficiently. In the final chapter, I anticipate the prospects for this research as four main directions: (i) clustering and implementation optimization, (ii) enhancement of functionalities, visualization, and user experiences, (iii) application to multiple types of networks; and (iv) integration with text mining toward interactive, systematic knowledge discovery.

近年の生命科学分野においては、オーミクスという言葉に代表されるように巨大なデータを扱うことがごく一般的となっている。これらの巨大データには様々な形式のものが含まれるが、そのうち重要なものとして、遺伝子共発現やタンパク質相互作用など二項関係で記述されるデータが挙げられる。一般にこれらの二項関係データは、節点とそれを結ぶ枝からなるグラフ(ネットワーク)の形で可視化されてきたが、こういったグラフ表現は枝の数がおおよそ100を上回ると極度に複雑な外観を呈するようになり、そこから生命科学的な知識や仮説を引き出す上で効果的な表現手法とは言えなかった。

本論文は、このような背景のもと、グラフ構造の密な部分(モジュール)を階層的に発見する階層的グラフクラスタリング法と、生命科学データにしばしば見られる要素の性質に関する情報(遺伝子につけられるGene Ontologyデータなど)を用いた意味的クラスタリング法とを組み合わせることで、巨大な生命科学二項関係データをマルチスケールかつ対話的にナビゲーションする手法を世界で初めて開発したことを報告した論文である。さらに本論文中では、データ全体を表示する際には最も粒度の低いクラスタのみを表示し、データの一部分について表示する際にはより粒度の高いクラスタを表示することで、ウェブ上の地図サービスのような感覚でデータを可視化・解析できるソフトウェアを実装したことが報告されている。具体的には、独立型のJavaアプリケーションであるNaviCluster、およびネットワーク解析プラットフォームのデファクトスタンダードであるCytoscapeのプラグインであるNaviClusterCSの2つのプログラムを実装し、世界に向け公開を行っている。また、本論文において、開発した手法を実際の生命科学二項関係データ(出芽酵母のタンパク質相互作用データおよびシロイヌナズナの遺伝子共発現データ)に適用し、本手法の仮説生成における有効性を確認している。

ユーザ自身が階層構造を事前に与える必要が無く、かつ、ユーザが興味を持った任意の部分について二項関係データを自動的かつ高速に抽象化して可視化することを可能とした点が、本研究分野における先駆的な貢献と認められる。

なお、本論文は高木利久氏、岩崎 渉氏との共同研究であるが、論文提出者が主体となって研究を立案・実行したもので、論文提出者の寄与が十分であると判断する。

したがって、博士(科学)の学位を授与できると認める。