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

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

基本信息

批准号：
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完全）。另一方面，如上所述，将相关项目分类到同一类别的方法称为聚类。通过将聚类结果排列成一行，可以获得线性排列的近似解。然而，由于簇之间的所有顺序关系都没有定义，因此近似解还有改进的空间。在分层方法的情况下，可以利用树形图的分支的位置关系可以递归地反转的事实来改进近似解。此外，如果发现即使对一定深度或更多深度的边缘进行反转，解也没有改善，则可以对反转过程进行剪枝，从而加快计算速度。在本研究中，我们将这个问题称为树重排问题。通过叠加多个数据来改进分支重排的结果，可以整合遗传数据，并且还可以根据分支重排处理的结果可视化基因之间的关系。