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.

Metabolismo di oligosaccaridi prebiotici in Bifidobacterium per il potenziale sviluppo di nuovi prodotti alimentari funzionali

The growth and the metabolism of Bifidobacterium adolescentis MB 239 fermenting GOS, lactose, galactose, and glucose were investigated. An unstructerd unsegregated model for growth of B. adolescentis MB 239 in batch cultures was developed and kinetic parameters were calculated with a Matlab algorithm. Galactose was the best carbon source; lactose and GOS led to lower growth rate and cellular yield, but glucose was the poorest carbon source. Lactate, acetate and ethanol yields allowed calculation of the carbon fluxes toward fermentation products. Similar distribution between 3- and 2-carbon products was observed on all the carbohydrates (45 and 55%, respectively), but ethanol production was higher on glucose than on GOS, lactose and galactose, in decreasing order. Based on the stoichiometry of the fructose 6-phosphate shunt and on the carbon distribution among the products, ATP yield was calculated on the different carbohydrates. ATP yield was the highest on galactose, while it was 5, 8, and 25% lower on lactose, GOS, and glucose, respectively. Therefore, a correspondance among ethanol production, low ATP yields, and low biomass production was established demonstrating that carbohydrate preferences may result from different sorting of carbon fluxes through the fermentative pathway. During GOS fermentation, stringent selectivity based on the degree of polymerization was exhibited, since lactose and the trisaccharide were first to be consumed, and a delay was observed until longer oligosaccharides were utilized. Throughout the growth on both lactose and GOS, galactose accumulated in the cultural broth, suggesting that β-(1-4) galactosides can be hydrolysed before they are taken up. The physiology of Bifidobacterium adolescentis MB 239 toward xylooligosaccharides (XOS) was also studied and our attention was focused on an extracellular glycosyl-hydrolase (β-Xylosidase) expressed by a culture of B. adolescentis grown on XOS as sole carbon source. The extracellular enzyme was purified from the the supernatant, which was dialyzed and concentrated by ultrafiltration. A two steps purification protocol was developed: the sample was loaded on a Mono-Q anion exchange chromatography and then, the active fractions were pooled and β-Xylosidase was purified by gel filtration chromatography on a Superdex-75. The enzyme was characterized in many aspects. β- Xylosidase was an homo-tetramer of 160 kDa as native molecular mass; it was a termostable enzyme with an optimum of temperature at 53 °C and an optimum of pH of 6.0. The kinetics parameter were calculated: km = 4.36 mM, Vmax = 0.93 mM/min. The substrate specificity with different di-, oligo- and polysaccharides was tested. The reactions were carried out overnight at pH 7 and at the optimum of temperature and the carbohydrates hydrolysis were analyzed by thin layer chromatography (TLC). Only glycosyl-hydrolase activities on XOS and on xylan were detected, whereas sucrose, lactose, cellobiose, maltose and raffinose were not hydrolyzed. It’s clearly shown that β-Xylosidase activity was higher than the Xylanase one. These studies on the carbohydrate preference of a strain of Bifidobacterium underlined the importance of the affinity between probiotics and prebiotics. On the basis of this concept, together with Barilla G&R f.lli SpA, we studied the possibility to develop a functional food containing a synbiotic. Three probiotic strains Lactobacillus plantarum BAR 10, Streptococcus thermophilus BAR 20, and Bifidobacterium lactis BAR 30 were studied to assess their suitability for utilization in synbiotic products on the basis of antioxidative activity, glutathione production, acid and bile tolerance, carbohydrates fermentation and viability in food matrices. Bile and human gastric juice resistance was tested in vitro to estimate the transit tolerance in the upper gastrointestinal tract. B. lactis and L. plantarum were more acid tolerant than S. thermophilus. All the strains resisted to bile. The growth kinetics on 13 prebiotic carbohydrates were determined. Galactooligosaccharides and fructo-oligosaccharides were successfully utilized by all the strains and could be considered the most appropriate prebiotics to be used in effective synbiotic formulations. The vitality of the three strains inoculated in different food matrices and maintained at room temperature was studied. The best survival of Lactobacillus plantarum BAR 10, Streptococcus thermophilus BAR 20, and Bifidobacterium lactis BAR 30 was found in food chocolate matrices. Then an in vivo clinical trial was carried out for 20 healthy volunteers. The increase in faecal bifidobacteria and lactobacilli populations and the efficacy of the pre-prototype was promising for the future develop of potential commercial products.