0

因此，我目前正在开发一个快速而肮脏的 Python 项目，该项目支持由字典构成的数据结构，其键是来自开放生物本体格式的 GOID。它散列到另一个字典，其中包含父节点或术语和子节点或术语的列表，帮助我形成本体中给定节点的所有子节点或所有祖先的列表（使用 GO .obo 文件，如果这对任何人都有帮助）。

我的问题是我一直在寻找一种算法，它可以帮助我返回与给定节点 id 在同一级别上的所有相同节点，该节点 id 必须是相对的，因为可能有多个路径到节点（它是有向的无环图，但每个节点可以有多个父节点）。我基本上需要查找节点的父节点，将父节点的子节点全部存储在一个公共列表中，然后在添加的每个节点上重复此过程，而不会重复节点或显着减慢计算速度。

我认为这可以很容易地使用一组来防止重复条目，并且只跟踪我访问过的父母，直到所有兄弟姐妹的父母都被访问过而无法添加新的父母，但我怀疑这可能非常低效。如果有人对这种算法有经验，我们将不胜感激！希望这足够清楚，可以做出回应。

谢谢！

4

1 回答 1

0

好的，这就是我到目前为止所开发的，但由于某些奇怪的原因，它似乎一直给我错误的值。是否有任何人可以看到我意外未正确终止的小错误？

  # A helper function to find generations of a given node
  def getGenerationals(self,goid):
    quit = False
    visitedParents = set()
    generation = set()
    tempGen = set()
    generation.add(goid)
    while not quit:
      quit = True
      generation |= tempGen
      tempGen = set()
      print "TEMP GEN:",tempGen
      for g in generation:
        parents = set(self._terms[g]['p'])
        for p in parents:
          if p not in visitedParents:
            visitedParents.add(p)
            print "Parent:",p
            quit = False
            tempGen |= set(self._terms[p]['c'])
    raw_input("Break")
    return generation

  # Working function
  def getGeneration(self,goid):
    generation = list(self.getGenerationals(goid))
    generation.remove(goid)
    return list(generation)
于 2013-01-11T23:54:54.577 回答