Monocle Algorithm - Constructing PQ trees
0
2
Entering edit mode
20 months ago
Aryan ▴ 30

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 • 504 views
ADD COMMENT
0
Entering edit mode

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

ADD REPLY

Login before adding your answer.

Traffic: 2127 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6