Permutation classes, sorting algorithms, and lattice paths

A permutation is said to avoid a pattern if it does not contain any subsequence which is order-isomorphic to it. Donald Knuth, in the first volume of his celebrated book "The art of Computer Programming", observed that the permutations that can be computed (or, equivalently, sorted) by some particular data structures can be characterized in terms of pattern avoidance. In more recent years, the topic was reopened several times, while often in terms of sortable permutations rather than computable ones. The idea to sort permutations by using one of Knuth’s devices suggests to look for a deterministic procedure that decides, in linear time, if there exists a sequence of operations which is able to convert a given permutation into the identical one. In this thesis we show that, for the stack and the restricted deques, there exists an unique way to implement such a procedure. Moreover, we use these sorting procedures to create new sorting algorithms, and we prove some unexpected commutation properties between these procedures and the base step of bubblesort. We also show that the permutations that can be sorted by a combination of the base steps of bubblesort and its dual can be expressed, once again, in terms of pattern avoidance. In the final chapter we give an alternative proof of some enumerative results, in particular for the classes of permutations that can be sorted by the two restricted deques. It is well-known that the permutations that can be sorted through a restricted deque are counted by the Schrӧder numbers. In the thesis, we show how the deterministic sorting procedures yield a bijection between sortable permutations and Schrӧder paths.

Addressing tumor heterogeneity in esophageal adenocarcinoma through different molecular approaches

Several studies have shown epidemiologic, clinical, immune-histochemical and molecular differences among esophageal adenocarcinomas (EAC). Since pathogenesis and biology of this tumor are far to be well defined, our study aimed to examine intra- and inter-tumor heterogeneity and to solve crucial controversies through different molecular approaches. Target sequencing was performed for sorted cancer subpopulations from formalin embedded material obtained from 38 EACs, not treated with neoadjuvant therapy. 35 out 38 cases carried at least one somatic mutation, not present in the corresponding sorted stromal cells. 73.7% of cases carried mutations in TP53 and 10.5% in CDKN2A. Mutations in other genes occurred at lower frequency, including HNF1A, not previously associated with EAC. Sorting allowed us to isolate clones with different mutational loads and/or additional copy number amplifications, confirming the high intra-tumor heterogeneity of these cancers. In our cohort TP53 gene abnormalities correlated with a better survival (P = 0.028); conversely, loss of SMAD4 protein expression was associated with a higher recurrence rate (P = 0.015). Shifting the focus on the epigenetic characterization of EAC, miR-221 and miR-483-3p resulted upregulated from the MicroRNA Array card analysis and confirmed with further testing. The up-regulation of both miRNAs correlated with clinical outcomes, in particular with a reduced cancer-specific survival (miR483-3p P=0.0293; miR221 P=0.0059). In vitro analyses demonstrated an increase for miR-483-3p (fold-change=2.7) that appear to be inversely correlated with SMAD4 expression in FLO-1 cell-line. In conclusion, selective sorting allowed to define the real mutation status and to isolate different cancer subclones. MiRNA expression analysis revealed a significant up-regulation of miR-221 and miR-483-3p, which correlated with worst prognosis, implying that they can be considered oncogenic factors in EAC. Therefore, cell sorting technologies, coupled with next generation sequencing, and the analysis of microRNA profiles seem to be promising strategies to guide treatment and help classify cancer prognosis.