URD, simulated diffusion, branching - 物理医学数学の日記

scRNAの点群データから、細胞の分化の様子を、木グラフで表現するアルゴリズム、URD、の論文。

まず、k近傍グラフを構成して、ある点を根として、そこからグラフ上で拡散(確率的な遷移、ランダムウォーク)させる。

その時に、各点について、何手で辿り着くかをメモしておく。

何回かシミュレーションしたら、何手で辿り着けるかの期待値を得る。

それをPseudotimeとすることで、根からの近さ、生物学的には分化元からどれくらい離れているかという尺度を得る。

その後、一番遠い点、tip、からpseudotimeが若い方向へ、逆に確率的な遷移をさせる。この拡散シミュレーションは有向グラフ上の拡散なので、非対称である。

何回かすると、別々のtipからの流れが混ざる場所が同定できる。

それを一つ一つまとめていくと、

巨視的な木グラフが完成する。

あとは、グラフを可視化すれば良い。可視化については以前の記事で触れた。

グラフのクラスタリングをしてからこの処理を噛ませることもできる。代表的なクラスタリング手法、Louvainクラスタリングについてはこちら。