Oded Margalit

The authors have solved the all pairs shortest distances (APSD) problem for graphs with integer edge lengths. Our algorithm is subcubic for edge lengths of small (⩽M) absolute value. In this paper we show how to transform these algorithms to solve the all pairs shortest paths (APSP), in the same time complexity, up to a polylogarithmic factor. Forn=|V| the number of vertices,Mthe bound on edge length, andωthe exponent of matrix multiplication, we get the following results: 1. A directed nonnegative APSP(n, M) algorithm which runs inÕ(T(n, M)) time, where T(n, m)=\big\{\begin{align}M^{\omega -1)/2} n^{3+\omega )/2}, & 1\le M\le n^{3-\omega )/(\omega +1)}\\ Mn^{5\omega -3)/(\omega +1)}, & n^{(3-\omega )/(\omega +1)}\le M\le n^2(3-\omega )/(\omega +1)}.\end{align} 2. An undirected APSP(n, M) algorithm which runs inÕ(M(ω+1)/2nω log(Mn)) time. 3. A general APSP(n, M) algorithm which runs inÕ((Mn)(3+ω)/2).

The subcubic (O(n/sup w/) for w(3) algorithms to multiply Boolean matrices do not provide the witnesses; namely, they compute C=A.B but if C/sub ij/=1 they do not find an index k (a witness) such that A/sub ik/=B/sub kj/=1. The authors design a deterministic algorithm for computing the matrix of witnesses that runs in O(n/sup w/) time, where here O(n/sup w/) denotes O(n/sup w/(log n)/sup O(1)/). The subcubic methods to compute the shortest distances between all pairs of vertices also do not provide for witnesses; namely they compute the shortest distances but do not generate information for computing quickly the paths themselves. A witness for a shortest path from v/sub i/ to v/sub j/ is an index k such that v/sub k/ is the first vertex on such a path. They describe subcubic methods to compute such witnesses for several versions of the all pairs shortest paths problem. As a result, they derive shortest paths algorithms that provide characterization of the shortest paths in addition to the shortest distances in the same time (up to a polylogarithmic factor) needed for computing the distances; namely O(n/sup (3+w)/2/) time in the directed case and O(n/sup w/) time in the undirected case. They also design an algorithm that computes witnesses for the transitive closure in the same time needed to compute witnesses for Boolean matrix multiplication.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

•POLE/D1pd is associated with male sex, younger age, right-sided primary tumor, and uncommon KRAS mutations in mCRC.•A significantly higher ORR is observed for POLE/D1pd compared to dMMR/MSI-H mCRC treated with ICIs.•POLE/D1pd mCRC exposed to ICIs have a higher PFS and OS than dMMR/MSI-H.•POLE/D1pd mCRCs are enriched in single nucleotide variant while dMMR/MSI-H are enriched in frameshift mutations.•Non-responder POLEpd mCRCs have lower TMB than responders and lower intensity of the POLE signature. BackgroundPOLE and POLD1 proofreading deficiency (POLE/D1pd) define a rare subtype of ultramutated metastatic colorectal cancer (mCRC; over 100 mut/Mb). Disease-specific data about the activity and efficacy of immune checkpoint inhibitors (ICIs) in POLE/D1pd mCRC are lacking and it is unknown whether outcomes may be different from mismatch repair-deficient (dMMR)/microsatellite instability-high (MSI-H) mCRCs treated with ICIs.Patients and methodsIn this global study, we collected 27 patients with mCRC harboring POLE/D1 mutations leading to proofreading deficiency and treated with anti-programmed cell death-ligand 1 alone +/− anti-cytotoxic T-lymphocyte antigen-4 agents. We collected clinicopathological and genomic characteristics, response, and survival outcomes after ICIs of POLE/D1pd mCRC and compared them with a cohort of 610 dMMR/MSI-H mCRC patients treated with ICIs. Further genomic analyses were carried out in an independent cohort of 7241 CRCs to define POLE and POLD1pd molecular profiles and mutational signatures.ResultsPOLE/D1pd was associated with younger age, male sex, fewer RAS/BRAF driver mutations, and predominance of right-sided colon cancers. Patients with POLE/D1pd mCRC showed a significantly higher overall response rate (ORR) compared to dMMR/MSI-H mCRC (89% versus 54%; P = 0.01). After a median follow-up of 24.9 months (interquartile range: 11.3-43.0 months), patients with POLE/D1pd showed a significantly superior progression-free survival (PFS) compared to dMMR/MSI-H mCRC [hazard ratio (HR) = 0.24, 95% confidence interval (CI) 0.08-0.74, P = 0.01] and superior overall survival (OS) (HR = 0.38, 95% CI 0.12-1.18, P = 0.09). In multivariable analyses including the type of DNA repair defect, POLE/D1pd was associated with significantly improved PFS (HR = 0.17, 95% CI 0.04-0.69, P = 0.013) and OS (HR = 0.24, 95% CI 0.06-0.98, P = 0.047). Molecular profiling showed that POLE/D1pd tumors have higher tumor mutational burden (TMB). Responses were observed in both subtypes and were associated with the intensity of POLE/D1pd signature.ConclusionsPatients with POLE/D1pd mCRC showed more favorable outcomes compared to dMMR/MSI-H mCRC to treatment with ICIs in terms of tumor response and survival. POLE and POLD1 proofreading deficiency (POLE/D1pd) define a rare subtype of ultramutated metastatic colorectal cancer (mCRC; over 100 mut/Mb). Disease-specific data about the activity and efficacy of immune checkpoint inhibitors (ICIs) in POLE/D1pd mCRC are lacking and it is unknown whether outcomes may be different from mismatch repair-deficient (dMMR)/microsatellite instability-high (MSI-H) mCRCs treated with ICIs. In this global study, we collected 27 patients with mCRC harboring POLE/D1 mutations leading to proofreading deficiency and treated with anti-programmed cell death-ligand 1 alone +/− anti-cytotoxic T-lymphocyte antigen-4 agents. We collected clinicopathological and genomic characteristics, response, and survival outcomes after ICIs of POLE/D1pd mCRC and compared them with a cohort of 610 dMMR/MSI-H mCRC patients treated with ICIs. Further genomic analyses were carried out in an independent cohort of 7241 CRCs to define POLE and POLD1pd molecular profiles and mutational signatures. POLE/D1pd was associated with younger age, male sex, fewer RAS/BRAF driver mutations, and predominance of right-sided colon cancers. Patients with POLE/D1pd mCRC showed a significantly higher overall response rate (ORR) compared to dMMR/MSI-H mCRC (89% versus 54%; P = 0.01). After a median follow-up of 24.9 months (interquartile range: 11.3-43.0 months), patients with POLE/D1pd showed a significantly superior progression-free survival (PFS) compared to dMMR/MSI-H mCRC [hazard ratio (HR) = 0.24, 95% confidence interval (CI) 0.08-0.74, P = 0.01] and superior overall survival (OS) (HR = 0.38, 95% CI 0.12-1.18, P = 0.09). In multivariable analyses including the type of DNA repair defect, POLE/D1pd was associated with significantly improved PFS (HR = 0.17, 95% CI 0.04-0.69, P = 0.013) and OS (HR = 0.24, 95% CI 0.06-0.98, P = 0.047). Molecular profiling showed that POLE/D1pd tumors have higher tumor mutational burden (TMB). Responses were observed in both subtypes and were associated with the intensity of POLE/D1pd signature. Patients with POLE/D1pd mCRC showed more favorable outcomes compared to dMMR/MSI-H mCRC to treatment with ICIs in terms of tumor response and survival.