最適化手法の分子系統樹推定への応用

优化方法在分子系统发育树估计中的应用

基本信息

批准号：
07680331
负责人：
長谷川政美
金额：
$ 1.41万
依托单位：
The Institute of Statistical Mathematics
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1995
资助国家：
日本
起止时间：
1995 至无数据
项目状态：
已结题

项目摘要

分子系統樹の推定において、現在の最尤法の欠点は他の方法に比べて計算時間がかかることである。これは、トポロジーを仮定した系統樹の尤度を計算する際に、最尤なパラメータ(各枝の長さ)をNewton法で最適化する必要があるため計算量が多いことによる。本研究では、最適化手法を用いて、最尤法のこの欠点をある程度まで克服した。まず、各2種間の距離を最尤法で推定しておいて、トポロジーを固定した際に、各枝の長さを、その距離行列に関する最小2乗法を行なって近似的に求めると、その残差平方和の値は最尤法を行なった時の尤度の値と相関が高いことが分かった。従って、このような簡便法で有望であるようなトポロジーを予めスクリーニングしておいて、残差平方和の小さいトポロジーについてのみ、きちんした最尤法で解析を行なうことが有効である。この場合、より正確には枝の長さが正であることを考慮する必要がある。ところが、このような制約をつけた場合の最小2乗法は、正確に解けるものの、制約がない場合に比してかなり計算時間がかかる。そこで、この困難を解決するために、残差平方和を最小化する代わりに残差の絶対偏差和(L1ノルム)を最小化することを考えた。この問題は、線形計画問題に帰着でき、枝の長さが正であるという条件をつけくわえても簡単に解ける。そこで、絶対偏差をスクリーニングに使う評価関数とし、これを正確に最小化するようなトポロジーを見つけ、その後で絶対偏差が小さいいくつかのトポロジーに関して尤度を最大化し、そのなかで最大のものをもっともらしい系統樹であると推定することを考えた。この問題に対し、組合せ最適化についてよく使われる定石の一つである分岐限定法を適用し、効率的なトポロジー探索法を開発した。

在估计分子系统发育树时，当前最大似然方法的缺点是，它们比其他方法需要更长的时间来计算。这是因为在计算假设拓扑结构的系统发育树的可能性时，有必要使用牛顿方法优化最大似然参数（每个分支的长度），这是大量计算。在这项研究中，使用优化技术在某种程度上克服了最大似然方法的这一缺点。首先，当使用最大似然法估算两种类型之间的距离时，当拓扑固定时，当使用最小二乘法对距离矩阵近似每个分支的长度近似时，则发现在使用最大可能性方法时，平方的残留物值与可能的可能性值高度相关。因此，预先筛选以这种简单的方法有希望的拓扑，并使用精确的最大似然方法仅用于拓扑，并使用少量残留方形进行分析。在这种情况下，有必要更准确地说，分支长度为正。但是，尽管可以准确地求解具有此类约束的最小二乘方法，但比没有约束时要计算的时间要长得多。因此，为了解决这一难度，我们考虑了将残差的绝对偏差和（L1规范）最小化，而不是最大程度地减少正方形的总和。这个问题可以简化为线性编程问题，并且可以通过分支长度为正的条件轻松解决。因此，我们考虑使用绝对偏差作为筛选的评估函数，找到一种准确最小化的拓扑，然后最大程度地提高某些具有较小绝对偏差的拓扑的可能性，并将其中最大的拓扑成绩估计为合格的系统发育树。对于这个问题，我们应用了分支限制方法，这是组合优化的最常用策略之一，以开发有效的拓扑搜索方法。