Fingerprint Recognition: Enhancement, Feature Extraction and Automatic Evaluation of Algorithms

The identification of people by measuring some traits of individual anatomy or physiology has led to a specific research area called biometric recognition. This thesis is focused on improving fingerprint recognition systems considering three important problems: fingerprint enhancement, fingerprint orientation extraction and automatic evaluation of fingerprint algorithms. An effective extraction of salient fingerprint features depends on the quality of the input fingerprint. If the fingerprint is very noisy, we are not able to detect a reliable set of features. A new fingerprint enhancement method, which is both iterative and contextual, is proposed. This approach detects high-quality regions in fingerprints, selectively applies contextual filtering and iteratively expands like wildfire toward low-quality ones. A precise estimation of the orientation field would greatly simplify the estimation of other fingerprint features (singular points, minutiae) and improve the performance of a fingerprint recognition system. The fingerprint orientation extraction is improved following two directions. First, after the introduction of a new taxonomy of fingerprint orientation extraction methods, several variants of baseline methods are implemented and, pointing out the role of pre- and post- processing, we show how to improve the extraction. Second, the introduction of a new hybrid orientation extraction method, which follows an adaptive scheme, allows to improve significantly the orientation extraction in noisy fingerprints. Scientific papers typically propose recognition systems that integrate many modules and therefore an automatic evaluation of fingerprint algorithms is needed to isolate the contributions that determine an actual progress in the state-of-the-art. The lack of a publicly available framework to compare fingerprint orientation extraction algorithms, motivates the introduction of a new benchmark area called FOE (including fingerprints and manually-marked orientation ground-truth) along with fingerprint matching benchmarks in the FVC-onGoing framework. The success of such framework is discussed by providing relevant statistics: more than 1450 algorithms submitted and two international competitions.

Metaheuristics for Search Problems in Genomics - New Algorithms and Applications

In this thesis we made the first steps towards the systematic application of a methodology for automatically building formal models of complex biological systems. Such a methodology could be useful also to design artificial systems possessing desirable properties such as robustness and evolvability. The approach we follow in this thesis is to manipulate formal models by means of adaptive search methods called metaheuristics. In the first part of the thesis we develop state-of-the-art hybrid metaheuristic algorithms to tackle two important problems in genomics, namely, the Haplotype Inference by parsimony and the Founder Sequence Reconstruction Problem. We compare our algorithms with other effective techniques in the literature, we show strength and limitations of our approaches to various problem formulations and, finally, we propose further enhancements that could possibly improve the performance of our algorithms and widen their applicability. In the second part, we concentrate on Boolean network (BN) models of gene regulatory networks (GRNs). We detail our automatic design methodology and apply it to four use cases which correspond to different design criteria and address some limitations of GRN modeling by BNs. Finally, we tackle the Density Classification Problem with the aim of showing the learning capabilities of BNs. Experimental evaluation of this methodology shows its efficacy in producing network that meet our design criteria. Our results, coherently to what has been found in other works, also suggest that networks manipulated by a search process exhibit a mixture of characteristics typical of different dynamical regimes.

Ecological genetics and conservation genomics of wolf (Canis lupus)

In the present work, we apply both traditional and Next Generation Sequencing (NGS) tools to investigate some of the most important adaptive traits of wolves (Canis lupus). In the first part, we analyze the variability of three Major Histocompatibility Complex (MHC) class II genes in the Italian wolf population, also studying their possible role in mating choice and their influence on fitness traits. In the second section, as part of a larger canid genome project, we will exploit NGS data to investigate the transcript-level differences between the wolf and the dog genome that can be correlated to domestication.

Novel tools for conservation genetics in marine fish: population structure and evolution of the European hake (Merluccius merluccius) inferred by SNP variation and applications to traceability

The research presented in my PhD thesis is part of a wider European project, FishPopTrace, focused on traceability of fish populations and products. My work was aimed at developing and analyzing novel genetic tools for a widely distributed marine fish species, the European hake (Merluccius merluccius), in order to investigate population genetic structure and explore potential applications to traceability scenarios. A total of 395 SNPs (Single Nucleotide Polymorphisms) were discovered from a massive collection of Expressed Sequence Tags, obtained by high-throughput sequencing, and validated on 19 geographic samples from Atlantic and Mediterranean. Genome-scan approaches were applied to identify polymorphisms on genes potentially under divergent selection (outlier SNPs), showing higher genetic differentiation among populations respect to the average observed across loci. Comparative analysis on population structure were carried out on putative neutral and outlier loci at wide (Atlantic and Mediterranean samples) and regional (samples within each basin) spatial scales, to disentangle the effects of demographic and adaptive evolutionary forces on European hake populations genetic structure. Results demonstrated the potential of outlier loci to unveil fine scale genetic structure, possibly identifying locally adapted populations, despite the weak signal showed from putative neutral SNPs. The application of outlier SNPs within the framework of fishery resources management was also explored. A minimum panel of SNP markers showing maximum discriminatory power was selected and applied to a traceability scenario aiming at identifying the basin (and hence the stock) of origin, Atlantic or Mediterranean, of individual fish. This case study illustrates how molecular analytical technologies have operational potential in real-world contexts, and more specifically, potential to support fisheries control and enforcement and fish and fish product traceability.

Heuristic algorithms for the Capacitated Location-Routing Problem and the Multi-Depot Vehicle Routing Problem

The Capacitated Location-Routing Problem (CLRP) is a NP-hard problem since it generalizes two well known NP-hard problems: the Capacitated Facility Location Problem (CFLP) and the Capacitated Vehicle Routing Problem (CVRP). The Multi-Depot Vehicle Routing Problem (MDVRP) is known to be a NP-hard since it is a generalization of the well known Vehicle Routing Problem (VRP), arising with one depot. This thesis addresses heuristics algorithms based on the well-know granular search idea introduced by Toth and Vigo (2003) to solve the CLRP and the MDVRP. Extensive computational experiments on benchmark instances for both problems have been performed to determine the effectiveness of the proposed algorithms. This work is organized as follows: Chapter 1 describes a detailed overview and a methodological review of the literature for the the Capacitated Location-Routing Problem (CLRP) and the Multi-Depot Vehicle Routing Problem (MDVRP). Chapter 2 describes a two-phase hybrid heuristic algorithm to solve the CLRP. Chapter 3 shows a computational comparison of heuristic algorithms for the CLRP. Chapter 4 presents a hybrid granular tabu search approach for solving the MDVRP.

Low Correlated Sequences & Architectures and Algorithms for Analog-to-Information Converters: Theory, Design, Implementation and Applications.

Most electronic systems can be described in a very simplified way as an assemblage of analog and digital components put all together in order to perform a certain function. Nowadays, there is an increasing tendency to reduce the analog components, and to replace them by operations performed in the digital domain. This tendency has led to the emergence of new electronic systems that are more flexible, cheaper and robust. However, no matter the amount of digital process implemented, there will be always an analog part to be sorted out and thus, the step of converting digital signals into analog signals and vice versa cannot be avoided. This conversion can be more or less complex depending on the characteristics of the signals. Thus, even if it is desirable to replace functions carried out by analog components by digital processes, it is equally important to do so in a way that simplifies the conversion from digital to analog signals and vice versa. In the present thesis, we have study strategies based on increasing the amount of processing in the digital domain in such a way that the implementation of analog hardware stages can be simplified. To this aim, we have proposed the use of very low quantized signals, i.e. 1-bit, for the acquisition and for the generation of particular classes of signals.

Epidemiology and population genetics of Podosphaera fusca and Golovinomyces orontii, causal agents of cucurbit powdery mildew

In 2010, 2011 and 2012 growing seasons, the occurrence of the ascomycetes Podosphaera fusca and Golovinomyces orontii, causal agents of powdery mildew disease, was monitored on cultivated cucurbits located in Bologna and Mantua provinces to determine the epidemiology of the species. To identify the pathogens, both morphological and molecular identifications were performed on infected leaf samples and a Multiplex-PCR was performed to identify the mating type genes of P. fusca isolates. The investigations indicated a temporal succession of the two species with the earlier infections caused by G. orontii, that seems to be the predominant species till the middle of July when it progressively disappears and P. fusca becomes the main species infecting cucurbits till the end of October. The temporal variation is likely due to the different overwintering strategies of the two species instead of climatic conditions. Only chasmothecia of P. fusca were recorded and mating type alleles ratio tended to be 1:1. Considering that only chasmothecia of P. fusca were found, molecular-genetic analysis were carried out to find some evidence of recombination within this species by MLST and AFLP methods. Surprisingly, no variations were observed within isolates for the 8 MLST markers used. According to this result, AFLP analysis showed a high similarity within isolates, with SM similarity coefficient ranging between 0.91-1.00 and also, sequencing of 12 polymorphic bands revealed identity to some gene involved in mutation and selection. The results suggest that populations of P. fusca are likely to be a clonal population with some differences among isolates probably due to agricultural practices such as fungicides treatments and cultivated hosts. Therefore, asexual reproduction, producing a lot of fungal biomass that can be easily transported by wind, is the most common and useful way to the spread and colonization of the pathogen.

Spectrum Sensing Algorithms for Cognitive Radio Applications

Future wireless communications systems are expected to be extremely dynamic, smart and capable to interact with the surrounding radio environment. To implement such advanced devices, cognitive radio (CR) is a promising paradigm, focusing on strategies for acquiring information and learning. The first task of a cognitive systems is spectrum sensing, that has been mainly studied in the context of opportunistic spectrum access, in which cognitive nodes must implement signal detection techniques to identify unused bands for transmission. In the present work, we study different spectrum sensing algorithms, focusing on their statistical description and evaluation of the detection performance. Moving from traditional sensing approaches we consider the presence of practical impairments, and analyze algorithm design. Far from the ambition of cover the broad spectrum of spectrum sensing, we aim at providing contributions to the main classes of sensing techniques. In particular, in the context of energy detection we studied the practical design of the test, considering the case in which the noise power is estimated at the receiver. This analysis allows to deepen the phenomenon of the SNR wall, providing the conditions for its existence and showing that presence of the SNR wall is determined by the accuracy of the noise power estimation process. In the context of the eigenvalue based detectors, that can be adopted by multiple sensors systems, we studied the practical situation in presence of unbalances in the noise power at the receivers. Then, we shift the focus from single band detectors to wideband sensing, proposing a new approach based on information theoretic criteria. This technique is blind and, requiring no threshold setting, can be adopted even if the statistical distribution of the observed data in not known exactly. In the last part of the thesis we analyze some simple cooperative localization techniques based on weighted centroid strategies.

Agricultural Genetics and Plant Breeding in Early Twentieth-Century Italy

This thesis is about plant breeding in Early 20th-Century Italy. The stories of the two most prominent Italian plant-breeders of the time, Nazareno Strampelli and Francesco Todaro, are used to explore a fragment of the often-neglected history of Italian agricultural research. While Italy was not at the forefront of agricultural innovation, research programs aimed at varietal innovation did emerge in the country, along with an early diffusion of Mendelism. Using philosophical as well as historical analysis, plant breeding is analysed throughout this thesis as a process: a sequence of steps that lays on practical skills and theoretical assumptions, acting on various elements of production. Systematic plant-breeding programs in Italy started from small individual efforts, attracting more and more resources until they became a crucial part of the fascist regime's infamous agricultural policy. Hybrid varieties developed in the early 20th century survived World War II and are now ancestors of the varieties that are still cultivated today. Despite this relevance, the history of Italian wheat hybrids is today largely forgotten: this thesis is an effort to re-evaluate a part of it. The research did allow previously unknown or neglected facts to emerge, giving a new perspective on the infamous alliance between plant-breeding programs and the fascist regime. This thesis undertakes an analysis of Italian plant-breeding programs as processes. Those processes had a practical as well as a theoretical side, and involved various elements of production. Although a complete history of Italian plant breeding still remains to be written, the Italian case can now be considered along with the other case-studies that other scholars have developed in the history of plant breeding. The hope is that this historical and philosophical analysis will contribute to the on-going effort to understand the history of plants.

Implementation of network entropy algorithms on hpc machines, with application to high-dimensional experimental data

Network Theory is a prolific and lively field, especially when it approaches Biology. New concepts from this theory find application in areas where extensive datasets are already available for analysis, without the need to invest money to collect them. The only tools that are necessary to accomplish an analysis are easily accessible: a computing machine and a good algorithm. As these two tools progress, thanks to technology advancement and human efforts, wider and wider datasets can be analysed. The aim of this paper is twofold. Firstly, to provide an overview of one of these concepts, which originates at the meeting point between Network Theory and Statistical Mechanics: the entropy of a network ensemble. This quantity has been described from different angles in the literature. Our approach tries to be a synthesis of the different points of view. The second part of the work is devoted to presenting a parallel algorithm that can evaluate this quantity over an extensive dataset. Eventually, the algorithm will also be used to analyse high-throughput data coming from biology.

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.

Landscape ecology and genetics of the wolf in Italy

This PhD Thesis includes five main parts on diverse topics. The first two parts deal with the trophic ecology of wolves in Italy consequently to a recent increase of wild ungulates abundance. Data on wolf diet across time highlighted how wild ungulates are important food resource for wolves in Italy. Increasing wolf population, increasing numbers of wild ungulates and decreasing livestock consume are mitigating wolf-man conflicts in Italy in the near future. In the third part, non-invasive genetic sampling techniques were used to obtain genotypes and genders of about 400 wolves. Thus, wolf packs were genetically reconstructed using diverse population genetic and parentage software. Combining the results on pack structure and genetic relatedness with sampling locations, home ranges of wolf packs and dispersal patterns were identified. These results, particularly important for the conservation management of wolves in Italy, illustrated detailed information that can be retrieved from genetic identification of individuals. In the fourth part, wolf locations were combined with environmental information obtained as GIS-layers. Modern species distribution models (niche models) were applied to infer potential wolf distribution and predation risk. From the resulting distribution maps, information pastures with the highest risk of depredation were derived. This is particularly relevant as it allows identifying those areas under danger of carnivore attack on livestock. Finally, in the fifth part, habitat suitability models were combined with landscape genetic analysis. On one side landscape genetic analyses on the Italian wolves provided new information on the dynamics and connectivity of the population and, on the other side, a profound analysis of the effects that habitat suitability methods had on the parameterization of landscape genetic analyses was carried out to contributed significantly to landscape genetic theory.

Multilevel Domain Decomposition Algorithms for Monolithic Fluid-Structure Interaction Problems with Application to Haemodynamics

Finite element techniques for solving the problem of fluid-structure interaction of an elastic solid material in a laminar incompressible viscous flow are described. The mathematical problem consists of the Navier-Stokes equations in the Arbitrary Lagrangian-Eulerian formulation coupled with a non-linear structure model, considering the problem as one continuum. The coupling between the structure and the fluid is enforced inside a monolithic framework which computes simultaneously for the fluid and the structure unknowns within a unique solver. We used the well-known Crouzeix-Raviart finite element pair for discretization in space and the method of lines for discretization in time. A stability result using the Backward-Euler time-stepping scheme for both fluid and solid part and the finite element method for the space discretization has been proved. The resulting linear system has been solved by multilevel domain decomposition techniques. Our strategy is to solve several local subproblems over subdomain patches using the Schur-complement or GMRES smoother within a multigrid iterative solver. For validation and evaluation of the accuracy of the proposed methodology, we present corresponding results for a set of two FSI benchmark configurations which describe the self-induced elastic deformation of a beam attached to a cylinder in a laminar channel flow, allowing stationary as well as periodically oscillating deformations, and for a benchmark proposed by COMSOL multiphysics where a narrow vertical structure attached to the bottom wall of a channel bends under the force due to both viscous drag and pressure. Then, as an example of fluid-structure interaction in biomedical problems, we considered the academic numerical test which consists in simulating the pressure wave propagation through a straight compliant vessel. All the tests show the applicability and the numerical efficiency of our approach to both two-dimensional and three-dimensional problems.

Brain-Computer Interfaces for augmented communication: Asynchronous and adaptive algorithms and evaluation with end users

This thesis aimed at addressing some of the issues that, at the state of the art, avoid the P300-based brain computer interface (BCI) systems to move from research laboratories to end users’ home. An innovative asynchronous classifier has been defined and validated. It relies on the introduction of a set of thresholds in the classifier, and such thresholds have been assessed considering the distributions of score values relating to target, non-target stimuli and epochs of voluntary no-control. With the asynchronous classifier, a P300-based BCI system can adapt its speed to the current state of the user and can automatically suspend the control when the user diverts his attention from the stimulation interface. Since EEG signals are non-stationary and show inherent variability, in order to make long-term use of BCI possible, it is important to track changes in ongoing EEG activity and to adapt BCI model parameters accordingly. To this aim, the asynchronous classifier has been subsequently improved by introducing a self-calibration algorithm for the continuous and unsupervised recalibration of the subjective control parameters. Finally an index for the online monitoring of the EEG quality has been defined and validated in order to detect potential problems and system failures. This thesis ends with the description of a translational work involving end users (people with amyotrophic lateral sclerosis-ALS). Focusing on the concepts of the user centered design approach, the phases relating to the design, the development and the validation of an innovative assistive device have been described. The proposed assistive technology (AT) has been specifically designed to meet the needs of people with ALS during the different phases of the disease (i.e. the degree of motor abilities impairment). Indeed, the AT can be accessed with several input devices either conventional (mouse, touchscreen) or alterative (switches, headtracker) up to a P300-based BCI.

Conservation genetics of European wildcat (Felis silvestris silvestris): a wide and integrating analysis protocol for admixture inferences and population structure

Introgression of domestic cat genes into European wildcat (Felis silvestris silvestris) populations and reduction of wildcats’ range in Europe, leaded by habitat loss and fragmentation, are considered two of the main conservation problems for this endangered feline. This thesis addressed the questions related with the artificial hybridization and populations’ fragmentation, using a conservation genetics perspective. We combined the use of highly polymorphic loci, Bayesian statistical inferences and landscape analyses tools to investigate the origin of the geographic-genetic substructure of European wildcats (Felis silvestris silvestris) in Italy and Europe. The genetic variability of microsatellites evidenced that European wildcat populations currently distributed in Italy differentiated in, and expanded from two distinct glacial refuges during the Last Glacial Maximum. The genetic and geographic substructure detected between the eastern and western sides of the Apennine ridge, resulted by adaptation to specific ecological conditions of the Mediterranean habitats. European wildcat populations in Europe are strongly structured into 5 geographic-genetic macro clusters corresponding to: the Italian peninsular & Sicily; Balkans & north-eastern Italy; Germany eastern; central Europe; and Iberian Peninsula. Central European population might have differentiated in the extra-Mediterranean Würm ice age refuge areas (Northern Alps, Carpathians, and the Bulgarian mountain systems), while the divergence among and within the southern European populations might have resulted by the Pleistocene bio geographical framework of Europe, with three southern refugia localized in the Balkans, Italian Peninsula and Iberia Peninsula. We further combined the use of most informative autosomal SNPs with uniparental markers (mtDNA and Y-linked) for accurately detecting parental genotypes and levels of introgressive hybridization between European wild and domestic cats. A total of 11 hybrids were identified. The presence of domestic mitochondrial haplotypes shared with some wild individuals led us to hypnotize the possibility that ancient introgressive events might have occurred and that further investigation should be recommended.