Selective and incremental re-computation in reaction to changes: an exercise in metadata analytics

Editor's Notes

• #8: M \rightarrow \mathit{sim}(M) = F
• #9: M \rightarrow \mathit{sim}(M) = F \Delta_F(F,F') \Delta_M(M,M') \Delta_F(F,F') > \theta_O
• #10: \mathit{imp}(M,F, M') = f(\Delta_M(M,M'), F) \mathit{ReComp}(M' | M,F) =  \begin{cases}    \text{True if } \mathit{imp}(M,F, M') > \theta \\   \text{False otherwise} \end{cases} \Delta_F(F,F') > \theta_0, \mathit{imp}(M,F, M') < \theta \Delta_F(F,F') < \theta_0, \mathit{imp}(M,F, M') > \theta
• #11: \Delta_M(M,M') = \{ B^+, B^-, L^+, L^-\} \begin{aligned} & B^- = B_{\text{old}} \setminus B_{\text{new}} \hspace{0.5cm} & B^+ = B_{\text{new}} \setminus B_{\text{old}} \\ & L^- = L_{\text{old}} \setminus L_{\text{new}} & L^+ = L_{\text{new}} \setminus L_{\text{old}} \end{aligned} \label{eq:diff-output} \begin{aligned} & (B \rightarrow L) = B^- \cap L^+ \hspace{.4cm} & (B \rightarrow H) = B^- \setminus L^+ \\ & (L \rightarrow B) = L^- \cap B^+      & (L \rightarrow H) = L^- \setminus B^+ \\ & (H \rightarrow B) = B^+ \setminus L^- & (H \rightarrow L) = L^+ \setminus B^- \end{aligned} \Delta_F(F,F')
• #12: \langle M_i, M_j, F_i, F_j \rangle \rightarrow \langle \Delta_F(F_i,F_j), \mathit{imp}(M_i, M_j, F_j) \rangle \langle 1/0, 1/0 \rangle
• #16: Genomics is a form of data-intensive / computation-intensive analysis
• #19: Each sample included 2-lane, pair-end raw sequence reads (4 files per sample).The average size of compressed files was nearly 15 GiB per sample; file decompression was included in the pipeline as one of the initial tasks.
• #20: Changes in the reference databases have an impact on the classification
• #21: returns updates in mappings to genes that have changed between the two versions (including possibly new mappings): $\diffOM(\OM^t, \OM^{t'}) = \{\langle t, genes(\dt) \rangle | genes(\dt) \neq genes'(\dt) \} $\\ where $genes'(\dt)$ is the new mapping for $\dt$ in $\OM^{t'}$. \begin{align*} \diffCV&(\CV^t, \CV^{t'}) = \\ &\{ \langle v, \varst(v) | \varst(v) \neq \varst'(v) \} \\ & \cup \CV^{t'} \setminus \CV^t \cup \CV^t \setminus \CV^{t'} \label{eq:diff-cv} \end{align*} where $\varst'(v)$ is the new class associate to $v$ in $\CV^{t'}$.
• #22: Point of slide: sparsity of impact demands better than blind recomp. Table 1 summarises the results. We recorded four types of outcomes. Firstly, confirming the current diagnosis (� ), which happens when additional variants are added to the Red class. Secondly, retracting the diagnosis, which may happen (rarely) when all red variants are retracted, de-noted ❖. Thirdly, changes in the amber class which do not alter the diagnosis (� ), and finally, no change at all ( ). `Table reports results from nearly 500 executions, concern-ing a cohort of 33 patients, for a total runtime of about 58.7 hours. As merely 14 relevant output changes were de-tected, this is about 4.2 hours of computation per change: a steep cost, considering that the actual execution time of SVI takes a little over 7 minutes.
• #24: our recommendation is the use of BWA-MEM and Samtools pipeline for SNP calls and BWA-MEM and GATK-HC pipeline for indel calls. 
• #26: In four cases change in the caller version changes the classification
• #27: Changes can be frequent or rare, disruptive or marginal
• #28: Changes can be frequent or rare, disruptive or marginal
• #31: How to make computational experiments reusable, all or in part, through a combination of data and code sharing and re-purposing (reusable Research Objects) and virtualisation mechanisms
• #33: \diff{X}(X^t, X^{t'}), \quad \diff{Y}(Y^t, Y^{t'}), \quad \diff{D}(D^t,D^{t'})  C = \{\update{D^{t'}}{D^t},  \quad  \update{X^{t'}}{X^t} \} y^{t'} &= \exec(P, x^{t'}, d^{t'}) \\ \impact_{P}(C,y) &= f_{Y}( \diff{Y}(y^t, t^{t'})) \imp_{SVI} (C,X} = f_{SVI}( \diff{Y}(Y^t, Y^{t'})) \in \{ \texttt{None}, \texttt{Low}, \texttt{High} \}
• #34: \impact_{P}( \{\update{x^{t'}}{x^t} \},y) &= f_{Y}( \diff{Y}(y^t, \exec(P, x^{t'}, d^{t}) )) \impact_{P}( \{\update{d^{t'}}{d^t} \},y) &= f_{Y}( \diff{Y}(y^t, \exec(P, x^t, d^{t'}) ))
• #35: \text{let } v \in \diff{Y}(Y^t, Y^{t'}): \\ \text{for any $X$: } \impact_{P}(C,X) = \texttt{High} \text{ if }\\ v.\texttt{status:} \begin{cases} * \rightarrow \texttt{red} \\ \texttt{red} \rightarrow *  \end{cases}
• #36: Firstly, if we can analyse the structure and semantics of process P , to recompute an instance of P more effec-tively we may be able to reduce re-computation to only those parts of the process that are actually involved in the processing of the changed data. For this, we are in-spired by techniques for smart rerun of workflow-based applications [6, 7], as well as by more general approaches to incremental computation [8, 9].
• #37: Firstly, if we can analyse the structure and semantics of process P , to recompute an instance of P more effec-tively we may be able to reduce re-computation to only those parts of the process that are actually involved in the processing of the changed data. For this, we are in-spired by techniques for smart rerun of workflow-based applications [6, 7], as well as by more general approaches to incremental computation [8, 9].
• #38: Firstly, if we can analyse the structure and semantics of process P , to recompute an instance of P more effec-tively we may be able to reduce re-computation to only those parts of the process that are actually involved in the processing of the changed data. For this, we are in-spired by techniques for smart rerun of workflow-based applications [6, 7], as well as by more general approaches to incremental computation [8, 9].
• #41: Experimental setup for our study of ReComp techniques: SVI workflow with automated provenance recording Cohort of about 100 exomes (neurological disorders) Changes in ClinVar and OMIM GeneMap
• #48: Firstly, if we can analyse the structure and semantics of process P , to recompute an instance of P more effec-tively we may be able to reduce re-computation to only those parts of the process that are actually involved in the processing of the changed data. For this, we are in-spired by techniques for smart rerun of workflow-based applications [6, 7], as well as by more general approaches to incremental computation [8, 9].
• #49: y^t = \mathit{exec}(P,x,D^t) y^{t'}_+ = \mathit{exec}(P,x,\delta^+)
• #50: This is only a small selection of rows and a subset of columns. In total there was 30 columns, 349074 rows in the old set, 543841 rows in the new set, 200746 of the added rows, 5979 of the removed rows, 27662 of the changed rows. As on the previous slide, you may want to highlight that the selection of key-columns and where-columns is very important. For example, using #AlleleID, Assembly and Chromosome as the key columns, we have entry #AlleleID 15091 which looks very similar in both added (green) and removed (red) sets. They differ, however, in the Chromosome column. Considering the where-columns, using only ClinicalSignificance returns blue rows which differ between versions only in that columns. Changes in other columns (e.g. LastEvaluated) are not reported, which may have ramifications if such a difference is used to produce the new output.
• #51: This is only a small selection of rows and a subset of columns. In total there was 30 columns, 349074 rows in the old set, 543841 rows in the new set, 200746 of the added rows, 5979 of the removed rows, 27662 of the changed rows. As on the previous slide, you may want to highlight that the selection of key-columns and where-columns is very important. For example, using #AlleleID, Assembly and Chromosome as the key columns, we have entry #AlleleID 15091 which looks very similar in both added (green) and removed (red) sets. They differ, however, in the Chromosome column. Considering the where-columns, using only ClinicalSignificance returns blue rows which differ between versions only in that columns. Changes in other columns (e.g. LastEvaluated) are not reported, which may have ramifications if such a difference is used to produce the new output.
• #52: y^t = \mathit{exec}(P,x,D^t) y^{t'}_+ = \mathit{exec}(P,x,\delta^+) \delta^- \cup \delta^+
• #54: Also, as in Tab. 2 and 3 in the paper, I’d mention whether this reduction was possible with generic diff function or specific function tailored to SVI. What is also interesting and what I would highlight is that even if the reduction is very close to 100% but below, the cost of recomputation of the process may still be significant because of some constant-time overheads related to running a process (e.g. loading data into memory). e-SC workflows suffer from exactly this issue (every block serializes and deserializes data) and that’s why Fig. 6 shows increase in runtime for GeneMap executed with 2 \deltas even if the reduction is 99.94% (cf. Tab. 2 and Fig. 6 for GeneMap diff between 16-10-30 –> 16-10-31).
• #55: Firstly, if we can analyse the structure and semantics of process P , to recompute an instance of P more effec-tively we may be able to reduce re-computation to only those parts of the process that are actually involved in the processing of the changed data. For this, we are in-spired by techniques for smart rerun of workflow-based applications [6, 7], as well as by more general approaches to incremental computation [8, 9].
• #56: v \in (\delta^- \cup \delta^+) \cap \mathit{used}(p_j, v) \Rightarrow p_j \text{ in scope } v.\mathit{phenotype} == p_j.\mathit{phenotype} \Rightarrow p_j \text{ in scope }
• #57: Regarding the algorithm, you show the simplified version (Alg. 1). But please take also look on Alg. 2 and mention that you can only run the loop if the distributiveness holds for all P in the downstream graph. Otherwise, you need to break and re-execute on full inputs just after first non-distributive task produces a non-empty output. But, obviously, the hope is that with a well tailored diff function the output will be empty for majority of cases.
• #63: er = \langle P, X^{t}, D^{t}, Y^{t}, c^{t}, T \rangle   \HDB = \{  er_1, er_2 \dots er_N \} {\cal X} = \{ er.X | er \in \HDB\}
• #64: \impact_{P}( \{\update{x^{t'}}{x^t} \},y) &= f_{Y}( \diff{Y}(y^t, \exec(P, x^{t'}, d^{t}) )) \impact_{P}( \{\update{d^{t'}}{d^t} \},y) &= f_{Y}( \diff{Y}(y^t, \exec(P, x^t, d^{t'}) ))
• #65: C = \update{D^{t'}}{D^t}, \update{X^{t'}}{X^t} X \in {\cal X} \imphat_P(C,y) \costhat(C,y) \recomp_P(C,y) \impact_{P}(C,y) \langle X^{t}, D^{t}, Y^{t}, c^{t} \rangle \qquad \langle X^{t'}, D^{t'}, Y^{t'}, c^{t'} \rangle  \recomp_{SVI}(C,X) = \begin{cases} \text{True} & \text{if } \imphat_{SVI}(C,y) \neq \texttt{None} \\ \text{False} & \text{otherwise} \end{cases}
• #66: \begin{equation*} \langle y_i^t, c_i^t \rangle = \exec(P, x_i^t, \{ d_1^t \dots d_m^t\}) \end{equation*} \widehat{f}(x) = f(x) + \epsilon \begin{equation*} y = P(x) \end{equation*} $\update{x’}{x}$ $\diff{Y}(f(x), f(x'))$ $f'()$ such that $f'(x) = f(x) + \epsilon$ $ \diff{Y}(f(x), f(x')) \rightarrow \diff{Y}(f'(x), f'(x')) $
• #67: er = \langle X^{t}, D^{t}, Y^{t}, c^{t} \rangle \qquad er' = \langle X^{t'}, D^{t'}, Y^{t'}, c^{t'} \rangle  \dr = \langle \diff_X(X^{t}, X^{t'}), \diff_D(D^{t}, D^{t'}), \diff_Y(, Y^{t},Y^{t'}, \imp{C,X} \rangle \DDB = \{ \dr_1, \dr_2 \dots \dr_M \}
• #68: \begin{algorithm}[H] \SetCustomAlgoRuledWidth{\textwidth}  \KwData{Evidence $E = \{ \mathit{HDB}, \mathit{DDB} \}$, Population ${\cal X}$, change $C$}   \KwResult{Updated outcomes for a subset ${\cal X}' \subseteq {\cal X}$, updated Evidence}   $\mathit{dv} = \mathbf{1}$\;  \While{ $\mathit{dv} != \mathbf{0}$}     {     $\mathit{dv} = \mathit{select}(E,C)$ \tcc{ binary \textit{decision vector} of size $|{\cal X}|$}     $[Y_i^{t'}]_{i:1 \dots k} = \mathit{execAll}(dv, {\cal X})$ \tcc{Re-comp all $k$ selected $X \in {\cal X}$}     $I = [ \imp{Y_i^{t}, Y_i^{t'}}]_{i:1 \dots k}$ \tcc{calculate impact from the new outcomes}     $E = \mathit{updateEvidence}(E,I)$ \tcc{update evidence adding new impact}     }        \end{algorithm}