Graph {SMRUCC.genomics.Data.GeneOntology.DAG}

.NET clr documentation

Graph

Description

GO DAG graph

关于祖先/子孙索引的算法说明

GO 的本体是一个有向无环图(DAG)，一个子条目可能同时拥有多个父条目， 所以从任意一个条目出发向上的路径数量是指数级的。旧版本的 Graph.Family() 会枚举出所有的祖先路径，而 Builder.CreateClusterMembers() 又会对每一个条目都调用一次 该函数，导致在完整的 go.obo(约5万条目)上面构建时会直接卡死或者内存溢出。

这里改为：

1. 通过记忆化(memoization)的DFS计算出每一个条目的祖先集合(去重，不带路径信息)， 复杂度由指数级降低为 O(N * A)；
2. 子孙索引由祖先集合单次反查聚合得到，并且是惰性构建的，即只有真的 需要用到的时候才会去计算。

Declare

            
# namespace SMRUCC.genomics.Data.GeneOntology.DAG
export class Graph {
   header: header;
   # 获取得到当前的DAG图之中的所有的节点
   Terms: iterates(TermNode);
}

        

.NET clr type reference tree

1. use by property member header: header
2. use by property member Terms: iterates(TermNode)

---