Efficient algorithms for accurate hierarchical clustering of huge datasets: tackling the entire protein space

Yaniv Loewenstein1,∗, Elon Portugaly1, Menachem Fromer1 and Michal Linial2,

蛋白を階層クラスタリング。

ポイントは距離がすべての蛋白の間に定義されるわけではないこと。

また、三角形の1辺は2辺の和より短い、という法則が成り立たないこと。

この前提ではcentroidが定義できない。kmeansのような方法も使えなさそう。。。

メモリに乗る範囲で何とかやる方法を提案している。

距離でソートして、短いほうからメモリに乗る範囲で載せて、上限と下限でしばりながら

クラスタリングを行う。これをなんどか繰り返す。

並列化は非常に難しそう。簡単に出来る方法は思いつかない。