linearWalk

Performs a linear walk through a scaffold graph starting in startNode. A linear walk is a sequence of adjacent joins where no node is visited twice unless the graph is cyclic in which case the first node will appear twice. The implementation requires the graph to have linear components, ie. for every node the degree must be at most two. If the component of startNode is cyclic then the walk will in startNode and the isCyclic flag will be set.

The direction of the walk can be influenced by giving firstJoin.

**Note:** if one wants to read the isCyclic flag it is required to use std.range.refRange in most cases.

LinearWalk!T linearWalk(Scaffold!T scaffold, ContigNode startNode, Scaffold!T.IncidentEdgesCache incidentEdgesCache = Scaffold!T.IncidentEdgesCache.init)
LinearWalk!T
linearWalk
(
T
)
(
Scaffold!T scaffold
,
ContigNode startNode
,
Scaffold!T.IncidentEdgesCache incidentEdgesCache = Scaffold!T.IncidentEdgesCache.init
)
LinearWalk!T linearWalk(Scaffold!T scaffold, ContigNode startNode, Join!T firstJoin, Scaffold!T.IncidentEdgesCache incidentEdgesCache = Scaffold!T.IncidentEdgesCache.init)

1 alias Payload = int;
2 alias J = Join!Payload;
3 alias S = Scaffold!Payload;
4 alias CN = ContigNode;
5 alias CP = ContigPart;
6 //   contig 1      contig 2
7 //
8 //  o        o     o        o
9 //                         / e4
10 //    o -- o ------- o -- o
11 //              e3
12 //
13 //    o -- o         o -- o         o -- o
14 //                         \ e7 e8 /      \ e9
15 //  o        o     o        o     o        o
16 //
17 //   contig 5       contig 4      contig 3
18 //
19 auto joins1 = [
20     J(CN(1, CP.end), CN(2, CP.begin), 1), // e3
21     J(CN(2, CP.end), CN(2, CP.post ), 1), // e4
22     J(CN(4, CP.end), CN(4, CP.post ), 1), // e7
23     J(CN(3, CP.pre), CN(3, CP.begin), 1), // e8
24     J(CN(3, CP.end), CN(3, CP.post ), 1), // e9
25 ];
26 auto scaffold1 = buildScaffold!(sumPayloads!Payload, Payload)(5, joins1);
27 auto scaffold1Cache = scaffold1.allIncidentEdges();
28 auto walks1 = [
29     [
30         getDefaultJoin!Payload(1),
31         joins1[0],
32         getDefaultJoin!Payload(2),
33         joins1[1],
34     ],
35     [
36         getDefaultJoin!Payload(4),
37         joins1[2],
38     ],
39     [
40         joins1[3],
41         getDefaultJoin!Payload(3),
42         joins1[4],
43     ],
44 ];
45 
46 alias getWalkStart = (walk) => walk[0].source(walk[0].getConnectingNode(walk[1]));
47 
48 foreach (walk; walks1)
49 {
50     auto reverseWalk = walk.retro.array;
51     auto computedWalk = linearWalk!Payload(scaffold1, getWalkStart(walk));
52     auto computedReverseWalk = linearWalk!Payload(scaffold1, getWalkStart(reverseWalk));
53 
54     assert(equal(walk[], refRange(&computedWalk)));
55     assert(!computedWalk.isCyclic);
56     assert(equal(reverseWalk[], refRange(&computedReverseWalk)));
57     assert(!computedReverseWalk.isCyclic);
58 }
59 
60 foreach (walk; walks1)
61 {
62     auto reverseWalk = walk.retro.array;
63     auto computedWalk = linearWalk!Payload(scaffold1, getWalkStart(walk), scaffold1Cache);
64     auto computedReverseWalk = linearWalk!Payload(scaffold1, getWalkStart(reverseWalk), scaffold1Cache);
65 
66     assert(equal(walk[], refRange(&computedWalk)));
67     assert(!computedWalk.isCyclic);
68     assert(equal(reverseWalk[], refRange(&computedReverseWalk)));
69     assert(!computedReverseWalk.isCyclic);
70 }
71 
72 //   contig 1      contig 2
73 //
74 //  o        o     o        o
75 //
76 //              e1
77 //    o -- o ------- o -- o
78 //     \_________________/
79 //              e2
80 //
81 auto joins2 = [
82     J(CN(1, CP.end), CN(2, CP.begin), 1), // e1
83     J(CN(2, CP.end), CN(1, CP.begin ), 1), // e2
84 ];
85 auto scaffold2 = buildScaffold!(sumPayloads!Payload, Payload)(2, joins2);
86 auto scaffold2Cache = scaffold2.allIncidentEdges();
87 auto walk2 = [
88     getDefaultJoin!Payload(1),
89     joins2[0],
90     getDefaultJoin!Payload(2),
91     joins2[1],
92 ];
93 
94 {
95     auto computedWalk = linearWalk!Payload(scaffold2, getWalkStart(walk2), walk2[0]);
96     auto reverseWalk2 = walk2.retro.array;
97     auto computedReverseWalk2 = linearWalk!Payload(scaffold2,
98             getWalkStart(reverseWalk2), reverseWalk2[0]);
99 
100     assert(equal(walk2[], refRange(&computedWalk)));
101     assert(computedWalk.isCyclic);
102     assert(equal(reverseWalk2[], refRange(&computedReverseWalk2)));
103     assert(computedWalk.isCyclic);
104 }
105 
106 {
107     auto computedWalk = linearWalk!Payload(scaffold2, getWalkStart(walk2), walk2[0], scaffold2Cache);
108     auto reverseWalk2 = walk2.retro.array;
109     auto computedReverseWalk2 = linearWalk!Payload(scaffold2,
110             getWalkStart(reverseWalk2), reverseWalk2[0], scaffold2Cache);
111 
112     assert(equal(walk2[], refRange(&computedWalk)));
113     assert(computedWalk.isCyclic);
114     assert(equal(reverseWalk2[], refRange(&computedReverseWalk2)));
115     assert(computedWalk.isCyclic);
116 }

linearWalk

Return Value

Throws

Examples

Meta

Source