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!
I had the same question - been trying to understand this for a while but can’t find anything :(