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.

Ottimizzazione delle reti di distribuzione idrica tramite algoritmi genetici multi-obiettivo

Water distribution networks optimization is a challenging problem due to the dimension and the complexity of these systems. Since the last half of the twentieth century this field has been investigated by many authors. Recently, to overcome discrete nature of variables and non linearity of equations, the research has been focused on the development of heuristic algorithms. This algorithms do not require continuity and linearity of the problem functions because they are linked to an external hydraulic simulator that solve equations of mass continuity and of energy conservation of the network. In this work, a NSGA-II (Non-dominating Sorting Genetic Algorithm) has been used. This is a heuristic multi-objective genetic algorithm based on the analogy of evolution in nature. Starting from an initial random set of solutions, called population, it evolves them towards a front of solutions that minimize, separately and contemporaneously, all the objectives. This can be very useful in practical problems where multiple and discordant goals are common. Usually, one of the main drawback of these algorithms is related to time consuming: being a stochastic research, a lot of solutions must be analized before good ones are found. Results of this thesis about the classical optimal design problem shows that is possible to improve results modifying the mathematical definition of objective functions and the survival criterion, inserting good solutions created by a Cellular Automata and using rules created by classifier algorithm (C4.5). This part has been tested using the version of NSGA-II supplied by Centre for Water Systems (University of Exeter, UK) in MATLAB® environment. Even if orientating the research can constrain the algorithm with the risk of not finding the optimal set of solutions, it can greatly improve the results. Subsequently, thanks to CINECA help, a version of NSGA-II has been implemented in C language and parallelized: results about the global parallelization show the speed up, while results about the island parallelization show that communication among islands can improve the optimization. Finally, some tests about the optimization of pump scheduling have been carried out. In this case, good results are found for a small network, while the solutions of a big problem are affected by the lack of constraints on the number of pump switches. Possible future research is about the insertion of further constraints and the evolution guide. In the end, the optimization of water distribution systems is still far from a definitive solution, but the improvement in this field can be very useful in reducing the solutions cost of practical problems, where the high number of variables makes their management very difficult from human point of view.

The assessment of change in rural landscape and the analysis of the driving forces. Proposal of a spatial model for the rural built environment

The presented study carried out an analysis on rural landscape changes. In particular the study focuses on the understanding of driving forces acting on the rural built environment using a statistical spatial model implemented through GIS techniques. It is well known that the study of landscape changes is essential for a conscious decision making in land planning. From a bibliography review results a general lack of studies dealing with the modeling of rural built environment and hence a theoretical modelling approach for such purpose is needed. The advancement in technology and modernity in building construction and agriculture have gradually changed the rural built environment. In addition, the phenomenon of urbanization of a determined the construction of new volumes that occurred beside abandoned or derelict rural buildings. Consequently there are two types of transformation dynamics affecting mainly the rural built environment that can be observed: the conversion of rural buildings and the increasing of building numbers. It is the specific aim of the presented study to propose a methodology for the development of a spatial model that allows the identification of driving forces that acted on the behaviours of the building allocation. In fact one of the most concerning dynamic nowadays is related to an irrational expansion of buildings sprawl across landscape. The proposed methodology is composed by some conceptual steps that cover different aspects related to the development of a spatial model: the selection of a response variable that better describe the phenomenon under study, the identification of possible driving forces, the sampling methodology concerning the collection of data, the most suitable algorithm to be adopted in relation to statistical theory and method used, the calibration process and evaluation of the model. A different combination of factors in various parts of the territory generated favourable or less favourable conditions for the building allocation and the existence of buildings represents the evidence of such optimum. Conversely the absence of buildings expresses a combination of agents which is not suitable for building allocation. Presence or absence of buildings can be adopted as indicators of such driving conditions, since they represent the expression of the action of driving forces in the land suitability sorting process. The existence of correlation between site selection and hypothetical driving forces, evaluated by means of modeling techniques, provides an evidence of which driving forces are involved in the allocation dynamic and an insight on their level of influence into the process. GIS software by means of spatial analysis tools allows to associate the concept of presence and absence with point futures generating a point process. Presence or absence of buildings at some site locations represent the expression of these driving factors interaction. In case of presences, points represent locations of real existing buildings, conversely absences represent locations were buildings are not existent and so they are generated by a stochastic mechanism. Possible driving forces are selected and the existence of a causal relationship with building allocations is assessed through a spatial model. The adoption of empirical statistical models provides a mechanism for the explanatory variable analysis and for the identification of key driving variables behind the site selection process for new building allocation. The model developed by following the methodology is applied to a case study to test the validity of the methodology. In particular the study area for the testing of the methodology is represented by the New District of Imola characterized by a prevailing agricultural production vocation and were transformation dynamic intensively occurred. The development of the model involved the identification of predictive variables (related to geomorphologic, socio-economic, structural and infrastructural systems of landscape) capable of representing the driving forces responsible for landscape changes.. The calibration of the model is carried out referring to spatial data regarding the periurban and rural area of the study area within the 1975-2005 time period by means of Generalised linear model. The resulting output from the model fit is continuous grid surface where cells assume values ranged from 0 to 1 of probability of building occurrences along the rural and periurban area of the study area. Hence the response variable assesses the changes in the rural built environment occurred in such time interval and is correlated to the selected explanatory variables by means of a generalized linear model using logistic regression. Comparing the probability map obtained from the model to the actual rural building distribution in 2005, the interpretation capability of the model can be evaluated. The proposed model can be also applied to the interpretation of trends which occurred in other study areas, and also referring to different time intervals, depending on the availability of data. The use of suitable data in terms of time, information, and spatial resolution and the costs related to data acquisition, pre-processing, and survey are among the most critical aspects of model implementation. Future in-depth studies can focus on using the proposed model to predict short/medium-range future scenarios for the rural built environment distribution in the study area. In order to predict future scenarios it is necessary to assume that the driving forces do not change and that their levels of influence within the model are not far from those assessed for the time interval used for the calibration.

Detection and localization of GLUTs in spermatozoa from different domestic species

Sperm cells need hexoses as a substrate for their function, for both the maintenance of membrane homeostasis and the movement of the tail. These cells have a peculiar metabolism that has not yet been fully understood, but it is clear that they obtain energy from hexoses through glycolisis and/or oxidative phosphorylation. Spermatozoa are in contact with different external environments, beginning from the testicular and epididymal fluid, passing to the seminal plasma and finally to the female genital tract fluids; in addition, with the spread of reproductive biotechnologies, sperm cells are diluted and stored in various media, containing different energetic substrates. To utilize these energetic sources, sperm cells, as other eukaryotic cells, have a well-constructed protein system, that is mainly represented by the GLUT family proteins. These transporters have a membrane-spanning α-helix structure and work as an enzymatic pump that permit a fast gradient dependent passage of sugar molecules through the lipidic bilayer of sperm membrane. Many GLUTs have been studied in man, bull and rat spermatozoa; the presence of some GLUTs has been also demonstrated in boar and dog spermatozoa. The aims of the present study were - to determine the presence of GLUTs 1, 2, 3, 4 and 5 in boar, horse, dog and donkey spermatozoa and to describe their localization; - to study eventual changes in GLUTs location after capacitation and acrosome reaction in boar, stallion and dog spermatozoa; - to determine possible changes in GLUTs localization after capacitation induced by insulin and IGF stimulation in boar spermatozoa; - to evaluate changes in GLUTs localization after flow-cytometric sex sorting in boar sperm cells. GLUTs 1, 2, 3 and 5 presence and localization have been demonstrated in boar, stallion, dog and donkey spermatozoa by western blotting and immunofluorescence analysis; a relocation in GLUTs after capacitation has been observed only in dog sperm cells, while no changes have been observed in the other species examined. As for boar, the stimulation of the capacitation with insulin and IGF didn’t cause any change in GLUTs localization, as well as for the flow cytometric sorting procedure. In conclusion, this study confirms the presence of GLUTs 1, 2 ,3 and 5 in boar, dog, stallion and donkey spermatozoa, while GLUT 4 seems to be absent, as a confirmation of other studies. Only in dog sperm cells capacitating conditions induce a change in GLUTs distribution, even if the physiological role of these changes should be deepened.

Genetic Manipulation, Gene Silencing and Biomarker Development in Multiple Experimental Models.

The thesis is set in three different parts, according to the relative experimental models. First, the domestic pig (Sus scrofa) is part of the study on reproductive biotechnologies: the transgenesis technique of Sperm Mediated Gene Transfer is widely studied starting from the quality of the semen, through the study of multiple uptakes of exogenous DNA and lastly used in the production of multi-transgenic blastocysts. Finally we managed to couple the transgenesis pipeline with sperm sorting and therefore produced transgenic embryos of predetermined sex. In the second part of the thesis the attention is on the fruit fly (Drosophila melanogaster) and on its derived cell line: the S2 cells. The in vitro and in vivo models are used to develop and validate an efficient way to knock down the myc gene. First an efficient in vitro protocol is described, than we demonstrate how the decrease in myc transcript remarkably affects the ribosome biogenesis through the study of Polysome gradients, rRNA content and qPCR. In vivo we identified two optimal drivers for the conditional silencing of myc, once the flies are fed with RU486: the first one is throughout the whole body (Tubulin), while the second is a head fat body driver (S32). With these results we present a very efficient model to study the role of myc in multiple aspects of translation. In the third and last part, the focus is on human derived lung fibroblasts (hLF-1), mouse tail fibroblasts and mouse tissues. We developed an efficient assay to quantify the total protein content of the nucleus on a single cell level via fluorescence. We coupled the protocol with classical immunofluorescence so to have at the same time general and particular information, demonstrating that during senescence nuclear proteins increase by 1.8 fold either in human cells, mouse cells and mouse tissues.

Industrial ecology applied to ELV management. Material and energy recovery from ASR

This PhD thesis reports on car fluff management, recycling and recovery. Car fluff is the residual waste produced by car recycling operations, particularly from hulk shredding. Car fluff is known also as Automotive Shredder Residue (ASR) and it is made of plastics, rubbers, textiles, metals and other materials, and it is very heterogeneous both in its composition and in its particle size. In fact, fines may amount to about 50%, making difficult to sort out recyclable materials or exploit ASR heat value by energy recovery. This 3 years long study started with the definition of the Italian End-of-Life Vehicles (ELVs) recycling state of the art. A national recycling trial revealed Italian recycling rate to be around 81% in 2008, while European Community recycling target are set to 85% by 2015. Consequently, according to Industrial Ecology framework, a life cycle assessment (LCA) has been conducted revealing that sorting and recycling polymers and metals contained in car fluff, followed by recovering residual energy, is the route which has the best environmental perspective. This results led the second year investigation that involved pyrolysis trials on pretreated ASR fractions aimed at investigating which processes could be suitable for an industrial scale ASR treatment plant. Sieving followed by floatation reported good result in thermochemical conversion of polymers with polyolefins giving excellent conversion rate. This factor triggered ecodesign considerations. Ecodesign, together with LCA, is one of the Industrial Ecology pillars and it consists of design for recycling and design for disassembly, both aimed at the improvement of car components dismantling speed and the substitution of non recyclable material. Finally, during the last year, innovative plants and technologies for metals recovery from car fluff have been visited and tested worldwide in order to design a new car fluff treatment plant aimed at ASR energy and material recovery.

Conservazione del seme sortato di suino

Gli spermatozoi di suino sottoposti alla procedura di sessaggio mediante citofluorimetria presentano una serie di modificazioni morfo-funzionali che compromettono nel tempo la loro sopravvivenza e la capacità fecondante. Questi spermatozoi, inoltre, a causa della sensibilità ai danni indotti dalla crioconservazione, vengono solitamente conservati allo stato liquido a 15-17°C, con conseguente ulteriore peggioramento nel tempo della qualità delle cellule spermatiche sessate. Lo scopo della ricerca è stato quello di valutare le modificazioni di alcune caratteristiche morfo-funzionali degli spermatozoi in seguito a sex-sorting e conseguente conservazione. Successivamente si è cercato di migliorare i parametri qualitativi del seme sessato mediante l’aggiunta di sostanze antiossidanti e la messa a punto di una nuova metodica di conservazione. I risultati ottenuti hanno evidenziato che la procedura di sessaggio e la conseguente conservazione per 24-26 ore a 15°C hanno indotto un peggioramento significativo delle caratteristiche morfo-funzionali (vitalità, integrità acrosomiale, quantità e distribuzione dell’Hsp70, capacità fecondante). Mentre l’azione degli antiossidanti non si è rivelata efficace nel miglioramento della qualità degli spermatozoi durante le fasi di colorazione e passaggio attraverso il citofluorimetro, l’azione congiunta del plasma seminale e degli antiossidanti superossido-dismutasi ed epigallocatechina-3-gallato ha indotto un miglioramento significativo della vitalità degli spermatozoi. Per la conservazione del seme di suino è stata testata la tecnica di incapsulazione in membrane di alginato di bario che permette, durante l’inseminazione artificiale, un rilascio graduale degli spermatozoi e l’utilizzo di un quantitativo inferiore di materiale seminale. L’applicazione di tale tecnica per la conservazione degli spermatozoi di suino sessati non sembra provocare un calo significativo della vitalità, dell’integrità acrosomiale e dell’efficienza totale di fecondazione rispetto al seme sortato e conservato diluito suggerendo futuri studi in vivo. Una migliore conoscenza dei danni indotti da queste tecnologie e la loro minimizzazione potrà stimolare in futuro l’utilizzo su vasta scala del seme sessato nel suino.

Taxonomy, phylogeny and reproductive ecology of Gentiana lutea L.

This research focuses on taxonomy, phylogeny and reproductive ecology of Gentiana lutea. L.. Taxonomic analysis is a critical step in botanical studies, as it is necessary to recognize taxonomical unit. Herbarium specimens were observed to assess the reliability of several subspecies-diagnostic characters. The analysis of G. lutea genetic variability and the comparison with that of the other species of sect. Gentiana were performed to elucidate phylogenetic relationships among G. lutea subspecies and to propose a phylogenetic hypothesis for the evolution and the colonization dynamics of the section. Appropriate scientific information is critical for the assessment of species conservation status and for effective management plans. I carried out field work on five natural populations and performed laboratory analyses on specific critical aspects, with special regard to G. lutea breeding system and type and efficiency of plant-pollinator system. Bracts length is a reliable character to identify subsp. vardjanii, however it is not exclusive, hence to clearly identify subsp. vardjanii, other traits have to be considered. The phylogenetic hypotheses obtained from nuclear and chloroplast data are not congruent. Nuclear markers show a monophyly of sect. Gentiana, a strongly species identity of G. lutea and clear genetic identity of subsp. vardjanii. The little information emerging from plastid markers indicate a weak signal of hybridization and incomplete sorting of ancestral lineages. G. lutea shows a striking variation in intra-floral dichogamy probably evolved to reduce pollen-stigma interference. Although the species is partially self-compatible, pollen vectors are necessary for a successful reproduction, and moreover it shows a strong inbreeding depression. G. lutea is a generalist species: within its spectrum of visitors is possible to recognize "nectar thieves" and pollinators with sedentary or dynamic behaviour. Pollen limitation is frequent and it could be mainly explained by poor pollen quality.

Continuos Flow Single Cell Separation into Open Microwell Arrays

A novel design based on electric field-free open microwell arrays for the automated continuous-flow sorting of single or small clusters of cells is presented. The main feature of the proposed device is the parallel analysis of cell-cell and cell-particle interactions in each microwell of the array. High throughput sample recovery with a fast and separate transfer from the microsites to standard microtiter plates is also possible thanks to the flexible printed circuit board technology which permits to produce cost effective large area arrays featuring geometries compatible with laboratory equipment. The particle isolation is performed via negative dielectrophoretic forces which convey the particles’ into the microwells. Particles such as cells and beads flow in electrically active microchannels on whose substrate the electrodes are patterned. The introduction of particles within the microwells is automatically performed by generating the required feedback signal by a microscope-based optical counting and detection routine. In order to isolate a controlled number of particles we created two particular configurations of the electric field within the structure. The first one permits their isolation whereas the second one creates a net force which repels the particles from the microwell entrance. To increase the parallelism at which the cell-isolation function is implemented, a new technique based on coplanar electrodes to detect particle presence was implemented. A lock-in amplifying scheme was used to monitor the impedance of the channel perturbed by flowing particles in high-conductivity suspension mediums. The impedance measurement module was also combined with the dielectrophoretic focusing stage situated upstream of the measurement stage, to limit the measured signal amplitude dispersion due to the particles position variation within the microchannel. In conclusion, the designed system complies with the initial specifications making it suitable for cellomics and biotechnology applications.

Cell death mechanisms triggered by monoclonal antibodies against CD99 in Ewing sarcoma: Cross-talk between MDM2, IGF-1R and Ras/MAPK

CD99 is a 32 kDa transmembrane protein whose high expression characterizes Ewing sarcoma (ES), a very aggressive pediatric bone tumor. In addition to its diagnostic value, CD99 has therapeutic potential since it leads to rapid and massive ES cell death when engaged with specific antibodies. Here a novel mechanism of cell death triggered via CD99 is shown, leading, ultimately, to the appearance of macropinocytotic vescicles. Anti-CD99 mAb 0662 induces MDM2 ubiquitination and degradation, which causes not only a p53 reactivation but also the IGF-1R induction and its subsequent internalization; CD99 results internalized together with IGF-1R inside endosomes, but then the two molecules display a different sorting: CD99 is degraded, while IGF-1R is recycled on the surface, causing, as a final step, the up-regulation of RAS-MAPK. High-expressing CD99 mesenchymal stem cells show mild Ras induction but no p53 activation and escape cell death, but in presence of EWS/FLI1 mesenchymal stem cells expressing CD99 show a stronger Ras induction and a p53 reactivation, leading to a significant cell death rate. We propose that CD99 triggering in a EWS/FLI1-driven oncogenetic context creates a synergy between RAS upregulation and p53 activation in ES cells, leading to cell death. Moreover, our data rule out possible concerns on toxicity related to the broad CD99 expression in normal tissues and provide the rationale for the therapeutic use of anti-CD99 MAbs in the clinic.