0

そのため、私は現在、オープンな生物学的オントロジー形式のGOIDであるキーを持つ辞書から作成されたデータ構造をサポートする迅速で汚いPythonプロジェクトに取り組んでいます。これは、親ノードまたは用語と子ノードまたは用語のリストを含む別の辞書にハッシュされ、オントロジー内の特定のノードのすべての子またはすべての祖先のリストを作成するのに役立ちます（GO .oboファイルを使用すると、誰かに役立ちます）。

私の問題は、ノードへのパスが複数ある可能性があるため、相対的である必要がある特定のノード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 に答える