Maximum Series-Parallel Subgraph

Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n-1 edges and any series-parallel graph on n vertices has at most 2n-3 edges. We present a 7/12 -approximation for this problem and results showing the limits of our approach.

Genetic variation of the Ananas genus with ornamental potential

Brazil is one of the main centers of origin of pineapple species presenting the largest genetic variation of the Ananas genus. Embrapa Cassava and Fruits is a Brazilian Agricultural Research Corporation and has an ex-situ collection of 678 accessions of the Ananas genus and some other Bromeliaceae. The use of ornamental pineapple has increased in the last years demanding new varieties, mainly for the external market, due to the originality and colors of its tiny fruits. The main aim of the present study was describing accessions from the pineapple gene bank in order to quantify their genetic variation and identify possible progenitors to be used in breeding programs of ornamental pineapples. Eighty-nine accessions of Ananas comosus var. comosus, A. comosus var. bracteatus (Lindl.) Coppens et Leal, A. comosus var. ananassoides (Baker) Coppens et Leal, A. comosus var. erectifolius (L. B. Smith) Coppens et Leal, A. comosus var. parguasensis (Camargo et L. B. Smith) Coppens et Leal and A. macrodontes Morren were evaluated with 25 morphological descriptors. According to the results, the evaluated accessions were separated into the following categories: landscape plants, cut flower, potted plants, minifruits, foliage and hedge. The genetic distance among accessions was determined using the combined qualitative and quantitative data by the Gower algorithm. The pre-selected accessions presented genetic variation and ornamental potential for different uses. The multicategory analysis formed seven clusters through a classification method based on the average Euclidean distance between all accessions using the cut-point of genetic dissimilarity (D dg = 0.35). The genotypes A. comosus var. erectifolius were selected to be used as landscape plants, cut flower, minifruits and potted plants. Accessions of A. comosus var. bracteatus and A. macrodontes were selected as landscape plants and hedge. The highest variation was observed in A. comosus var. ananassoides genotypes, which presented high potential for use as cut flowers.

A multi-objective adaptive immune algorithm for multi-application NoC mapping

Current SoC design trends are characterized by the integration of larger amount of IPs targeting a wide range of application fields. Such multi-application systems are constrained by a set of requirements. In such scenario network-on-chips (NoC) are becoming more important as the on-chip communication structure. Designing an optimal NoC for satisfying the requirements of each individual application requires the specification of a large set of configuration parameters leading to a wide solution space. It has been shown that IP mapping is one of the most critical parameters in NoC design, strongly influencing the SoC performance. IP mapping has been solved for single application systems using single and multi-objective optimization algorithms. In this paper we propose the use of a multi-objective adaptive immune algorithm (M(2)AIA), an evolutionary approach to solve the multi-application NoC mapping problem. Latency and power consumption were adopted as the target multi-objective functions. To compare the efficiency of our approach, our results are compared with those of the genetic and branch and bound multi-objective mapping algorithms. We tested 11 well-known benchmarks, including random and real applications, and combines up to 8 applications at the same SoC. The experimental results showed that the M(2)AIA decreases in average the power consumption and the latency 27.3 and 42.1 % compared to the branch and bound approach and 29.3 and 36.1 % over the genetic approach.

IDM - A New Parallel Methodology to Calculate the Determinant of Matrices of the Order n, with Computational Complexity O(n)

This paper presents a new parallel methodology for calculating the determinant of matrices of the order n, with computational complexity O(n), using the Gauss-Jordan Elimination Method and Chio's Rule as references. We intend to present our step-by-step methodology using clear mathematical language, where we will demonstrate how to calculate the determinant of a matrix of the order n in an analytical format. We will also present a computational model with one sequential algorithm and one parallel algorithm using a pseudo-code.

Genetic and environmental factors associated with the risk of cognitive decline and dementia

AD is the most common age related neurodegenerative disease in the industrialized world. Clinically AD is defined as a progressing decline of cognitive functions. Neuropathologically, AD is characterized by the aggregation of b-amyloid (Ab) peptide in the form of extracellular senile plaques, and hyperphosphorlylated tau protein in the form of intracellular neurofibrillary tangles. These neuropathological hallmarks are often accompanied by abundant microvascular damage and pronounced inflammation of the affected brain regions. In this thesis we investigated several aspects of AD focusing on the genetic aspect. We confirmed that Alpha 1 antichymotrypsin (ACT), an acute phase protein, was associated to AD subjects, being plasma levels higher in AD cases than controls. In addition, in a GWA study we demonstrated that two different gene, Clusterin and CR1 were strongly associated to AD. A single gene association not explain such a complex disease like AD. The goal should be to created a network of genetic, phenotypic and clinical data associated to AD. We used a new algorithm, the ANNs, aimed to map variables and search for connectivity among variables. We found specific variables associated to AD like cholesterol levels, the presence of variation in HMGCR enzyme and the age. Other factors such as the BMI, the amount of HDL and blood folate levels were also associated with AD. Pathogen infections, above all viral infections, have been previously associated to AD. The hypothesis suggests that virus and in particular herpes virus could enter the brain when an individual becomes older, perhaps because of a decline in the immune system. Our new hypothesis is that the presence of SNPs in our GWA gene study results in a genetic signature that might affect individual brain susceptibility to infection by herpes virus family during aging.

Parallelization of the algorithm WHAM with NVIDIA CUDA.

The aim of my thesis is to parallelize the Weighting Histogram Analysis Method (WHAM), which is a popular algorithm used to calculate the Free Energy of a molucular system in Molecular Dynamics simulations. WHAM works in post processing in cooperation with another algorithm called Umbrella Sampling. Umbrella Sampling has the purpose to add a biasing in the potential energy of the system in order to force the system to sample a specific region in the configurational space. Several N independent simulations are performed in order to sample all the region of interest. Subsequently, the WHAM algorithm is used to estimate the original system energy starting from the N atomic trajectories. The parallelization of WHAM has been performed through CUDA, a language that allows to work in GPUs of NVIDIA graphic cards, which have a parallel achitecture. The parallel implementation may sensibly speed up the WHAM execution compared to previous serial CPU imlementations. However, the WHAM CPU code presents some temporal criticalities to very high numbers of interactions. The algorithm has been written in C++ and executed in UNIX systems provided with NVIDIA graphic cards. The results were satisfying obtaining an increase of performances when the model was executed on graphics cards with compute capability greater. Nonetheless, the GPUs used to test the algorithm is quite old and not designated for scientific calculations. It is likely that a further performance increase will be obtained if the algorithm would be executed in clusters of GPU at high level of computational efficiency. The thesis is organized in the following way: I will first describe the mathematical formulation of Umbrella Sampling and WHAM algorithm with their apllications in the study of ionic channels and in Molecular Docking (Chapter 1); then, I will present the CUDA architectures used to implement the model (Chapter 2); and finally, the results obtained on model systems will be presented (Chapter 3).

Displacement Analysis of Under-Constrained Cable-Driven Parallel Robots

This dissertation studies the geometric static problem of under-constrained cable-driven parallel robots (CDPRs) supported by n cables, with n ≤ 6. The task consists of determining the overall robot configuration when a set of n variables is assigned. When variables relating to the platform posture are assigned, an inverse geometric static problem (IGP) must be solved; whereas, when cable lengths are given, a direct geometric static problem (DGP) must be considered. Both problems are challenging, as the robot continues to preserve some degrees of freedom even after n variables are assigned, with the final configuration determined by the applied forces. Hence, kinematics and statics are coupled and must be resolved simultaneously. In this dissertation, a general methodology is presented for modelling the aforementioned scenario with a set of algebraic equations. An elimination procedure is provided, aimed at solving the governing equations analytically and obtaining a least-degree univariate polynomial in the corresponding ideal for any value of n. Although an analytical procedure based on elimination is important from a mathematical point of view, providing an upper bound on the number of solutions in the complex field, it is not practical to compute these solutions as it would be very time-consuming. Thus, for the efficient computation of the solution set, a numerical procedure based on homotopy continuation is implemented. A continuation algorithm is also applied to find a set of robot parameters with the maximum number of real assembly modes for a given DGP. Finally, the end-effector pose depends on the applied load and may change due to external disturbances. An investigation into equilibrium stability is therefore performed.

Molecular genetics of inherited cystic kidney diseases: new diagnostic approaches

Background. Hhereditary cystic kidney diseases are a heterogeneous spectrum of disorders leading to renal failure. Clinical features and family history can help to distinguish the recessive from dominant diseases but the differential diagnosis is difficult due the phenotypic overlap. The molecular diagnosis is often the only way to characterize the different forms. A conventional molecular screening is suitable for small genes but is expensive and time-consuming for large size genes. Next Generation Sequencing (NGS) technologies enables massively parallel sequencing of nucleic acid fragments. Purpose. The first purpose was to validate a diagnostic algorithm useful to drive the genetic screening. The second aim was to validate a NGS protocol of PKHD1 gene. Methods. DNAs from 50 patients were submitted to conventional screening of NPHP1, NPHP5, UMOD, REN and HNF1B genes. 5 patients with known mutations in PKHD1 were submitted to NGS to validate the new method and a not genotyped proband with his parents were analyzed for a diagnostic application. Results. The conventional molecular screening detected 8 mutations: 1) the novel p.E48K of REN in a patient with cystic nephropathy, hyperuricemia, hyperkalemia and anemia; 2) p.R489X of NPHP5 in a patient with Senior Loken Syndrome; 3) pR295C of HNF1B in a patient with renal failure and diabetes.; 4) the NPHP1 deletion in 3 patients with medullar cysts; 5) the HNF1B deletion in a patient with medullar cysts and renal hypoplasia and in a diabetic patient with liver disease. The NGS of PKHD1 detected all known mutations and two additional variants during the validation. The diagnostic NGS analysis identified the patient’s compound heterozygosity with a maternal frameshift mutation and a paternal missense mutation besides a not transmitted paternal missense mutation. Conclusions. The results confirm the validity of our diagnostic algorithm and suggest the possibility to introduce this NGS protocol to clinical practice.