An Exact Hypergraph Matching algorithm for posture identification in embryonic C. elegans
Fig 9
EHGM applied to the sample image depicted in Fig 1A.
A: Two points are selected at the initial branch for TL and TR, respectively. Candidates for the successive pair, V6L and V6R, are queued based on hypergraphical relationships between the established cell identities TL and TR and each hypothesized V6 pair (lower costs are green to higher costs in red). B: The leading hypothesis at branch m=2 given the initial branch pair is chosen. The recursion continues to queue V5 pair choices at branch m=3. Black arrows within branch m specify the ordering of the branch given established cell assignments. Each branch creates a new subproblem of completing the posture given partially assigned identities. C: The tree continuing from the V5 pair hypothesis is fully explored according to the established recursion. D: The next leading V5 hypothesis is initiated upon exhaustion of the subtree formed at panel C. E: Implicit enumeration of the subtree formed at panel B causes the search to progress to the second leading V6 hypothesis.