Monocle Algorithm - Constructing PQ trees
0
1
Entering edit mode
6 weeks ago
Aryan ▴ 20

I was trying to understand the algorithm behind Monocle, which is frequently used to do trajectory analysis for scRNA data. I was mainly looking at the first paper's online methods. which led me to the original method they utilize - it involves producing what is called the PQ-graph of a minimal spanning tree (MST). The method is in this paper. I seem to have found inconsistencies in the method described and the suggested output in the paper.

Specifically, I was unsure whether the PQ tree constructed in the paper for an example (Figure 3 in paper, image attached below post for ease) is what the given algorithm produces (the algorithm is short and described in Section: Representing temporal orderings using PR-trees - pg. 4-5 of the second paper).

Following the algorithm above strictly, I deduced the PQ-tree to be, It is quite different from the one in the paper. The differences arise because (definitions are in the algorithm section above):

(a) the algorithm doesn't mention what to do with decisive vertices that are in the main diameter path of the MST but not in the indecisive backbone - see point (5) of the algorithm in the above paper.

(b) there seem to be two vertices, 8 and 9, in the first P-node in the paper's graph. However, I suspect that 9 should belong to a Q-node that is a child of the P_8 node, as I have drawn.

This is the figure from the paper:

(from left to right) top row: figure of the data; the MST and the "diameter path" (longest path in MST)

bottom row: the corresponding PQ tree (constructed by the algorithm given above, _allegedly_); last figure doesn't matter. With respect to my above two doubts, where am I (or the paper) going wrong? I realize my question is lengthy, but I cannot for the life of me figure it out after having spend hours on it, and will appreciate any help at all. Thank you!

scRNA algorithm graph-theory monocle graphs • 184 views
0
Entering edit mode

I had the same question - been trying to understand this for a while but can’t find anything :(