線形配置アルゴリズムによる遺伝子データの統合の表示手法の開発

开发使用线性对齐算法整合遗传数据的显示方法

基本信息

批准号：
16014207
负责人：
中谷明弘
金额：
$ 3.2万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2004
资助国家：
日本
起止时间：
2004 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16014207/
关键词：
遺伝子データ統合階層型クラスタリング線形配置問題

项目摘要

複数の遺伝子データの統合を行うためのソフトウェアを作成し、実データの解析に使用できるようにした。近年、細胞形態のデータや遺伝子発現データなどの遺伝子情報はWWW上から簡単に取得できるようになっている。しかしながら、いざ自らのデータの解析に用いようとしても難しいことが多い。遺伝子情報それぞれが異なった構造(ネットワーク構造をはじめ、木構造、時系列的構造、階層構造など)を成しており、複数の遺伝子データの統合(比較・重ね合わせ・相互補完など)が生物学的にも情報科学的にも本質的に難しいことが理由のひとつである(そしてそのためのツールが整っていないのが現状である)。従来から使われているクラスタリングやネットワーク構造の特徴抽出などの手法と併せて、遺伝子間の関係の解析に線形配置アルゴリズムを適用することを試みた。この目的のために、階層型のクラスタリングツールを作成した。従来のツールとの違いは、クラスタリングの結果得られる樹形図の形状を最適化する機能を有する点である。この最適化は、クラスタ間の相関を示す行列に対して定義されたエネルギー関数が最小化するように行われる。未知データを既知の情報に結び付けて機能解明の手がかりとすることは基本的な手法であるが、この最適化されたクラスタリングによって、より多くの情報が得られるようになった。一般的に、より強く関係し合った物(例えば遺伝子)同士がなるべく近くなるように物(遺伝子)の順番を決定する問題は、線形配置(linear arrangement)と呼ばれ、問題サイズの増加時に効率のよい解法が存在しない難しい問題(NP完全)であることが知られている。一方、関係し合ったもの同士を同一のカテゴリに分類する手法は上述の通りクラスタリングと呼ばれる。クラスタリングの結果を一列に並べることによって、線形配置の近似的な解を得ることができる。しかしながら、クラスタ間の全ての順序関係が規定されていないために、近似解の改善を行う余地がある。階層的な手法の場合、樹形図の枝の位置関係は再帰的に反転しても良いことを利用して、近似解の改善を行うことができる。また、ある深さ以上の枝の反転を行っても解が改善しないことが判明した場合には、反転処理の枝刈を行うことができるので計算の高速化が行える。本研究では、この問題を分枝再配置(tree rearrangement)問題と呼ぶこととした。分枝再配置の結果が改善するように複数のデータの重ね合わせを行うことにより、遺伝子データの統合を可能とし、また、分枝再配置処理の結果に基いて、遺伝子間の関係を可視化する手法の開発も行った。

创建软件是为了整合多个遗传数据，使其可以将其用于分析实际数据。近年来，可以轻松地从www中获得遗传信息，例如细胞形态数据和基因表达数据。但是，通常很难将其用于分析您自己的数据。一个原因之一是，每个遗传信息都有不同的结构（网络结构，树结构，时间序列结构，分层结构等），并且整合多个遗传数据（比较，叠加，相互补充等）本质上是困难的，无论是生物学和信息学上还是很困难（当前的情况是没有可用的工具）。除了传统的方法（例如聚类和网络结构的特征提取）外，我们还尝试应用线性放置算法来分析基因之间的关系。为此，我们创建了一个分层聚类工具。与常规工具的不同之处在于，它具有优化因聚类而获得的树图的形状。进行此优化，以便将显示簇之间相关性的矩阵的定义能量函数最小化。基本技术是将未知数据链接到已知信息以提示功能，但是这种优化的聚类已启用了更多信息。通常，确定对象（基因）的顺序的问题，使得更密切相关的对象（基因）尽可能接近线性排列，并且是一个困难的问题（NP Perfect），而当问题大小增加时没有有效的解决方案。另一方面，将相关项目分类为同一类别的方法称为聚类，如上所述。通过排列聚类的结果，可以获得线性排列的大致解决方案。但是，由于未定义簇之间的所有有序关系，因此大约解决方案有改进的空间。在层次方法的情况下，可以递归倒置树图中的分支的位置关系，并且可以改善近似解决方案。此外，如果发现解决方案也不会改善，即使超过一定深度的分支被倒置，则可以修剪反转过程，从而可以更快地计算。在这项研究中，此问题称为树木重排问题。通过叠加多个数据来改善分支重排的结果，可以整合遗传数据，并且还开发了一种方法来根据分支重排的结果可视化基因之间的关系。