Particle swarm design of digital circuits

Swarm Intelligence (SI) is the property of a system whereby the collective behaviors of (unsophisticated) agents interacting locally with their environment cause coherent functional global patterns to emerge. Particle swarm optimization (PSO) is a form of SI, and a population-based search algorithm that is initialized with a population of random solutions, called particles. These particles are flying through hyperspace and have two essential reasoning capabilities: their memory of their own best position and knowledge of the swarm's best position. In a PSO scheme each particle flies through the search space with a velocity that is adjusted dynamically according with its historical behavior. Therefore, the particles have a tendency to fly towards the best search area along the search process. This work proposes a PSO based algorithm for logic circuit synthesis. The results show the statistical characteristics of this algorithm with respect to number of generations required to achieve the solutions. It is also presented a comparison with other two Evolutionary Algorithms, namely Genetic and Memetic Algorithms.

An optimization approach for the job shop scheduling problem

This paper presents an optimization approach for the job shop scheduling problem (JSSP). The JSSP is a difficult problem in combinatorial optimization for which extensive investigation has been devoted to the development of efficient algorithms. The proposed approach is based on a genetic algorithm technique. The scheduling rules such as SPT and MWKR are integrated into the process of genetic evolution. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities and delay times of the operations are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained a local search heuristic is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed approach.

Discretization of complex-order algorithms for control applications

In this article we describe several methods for the discretization of the differintegral operator sa, where α = u + jv is a complex value. The concept of the conjugated-order differintegral is also introduced, which enables the use of complex-order differintegrals while still producing real-valued time responses and transfer functions. The performance of the resulting approximations is analysed in both the time and frequency domains. Several results are presented that demonstrate its utility in control system design.

Performance of fractional PID algorithms controlling nonlinear systems with saturation and backlash phenomena

The development of fractional-order controllers is currently one of the most promising fields of research. However, most of the work in this area addresses the case of linear systems. This paper reports on the analysis of fractional-order control of nonlinear systems. The performance of discrete fractional-order PID controllers in the presence of several nonlinearities is discussed. Some results are provided that indicate the superior robustness of such algorithms.

Dynamical modelling of a genetic algorithm

This work addresses the signal propagation and the fractional-order dynamics during the evolution of a genetic algorithm (GA). In order to investigate the phenomena involved in the GA population evolution, the mutation is exposed to excitation perturbations during some generations and the corresponding fitness variations are evaluated. Three distinct fitness functions are used to study their influence in the GA dynamics. The input and output signals are studied revealing a fractional-order dynamic evolution, characteristic of a long-term system memory.

A pattern language for parallelizing irregular algorithms

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Informática

Optimization of multi-stage amplifiers in deep-submicron CMOS using a distributed/parallel genetic algorithm

IEEE International Symposium on Circuits and Systems, pp. 724 – 727, Seattle, EUA

Algorithms and methodologies for decision support in energy efficiency on buildings

Dissertação apresentada na faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para a obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores

Task assignment algorithms for two-type heterogeneous multiprocessors

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising two different types of processors—such a platform is referred to as two-type platform. We present two low degree polynomial time-complexity algorithms, SA and SA-P, each providing the following guarantee. For a given two-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then (i) using SA, it is guaranteed to find such an assignment where the same restriction on task migration applies but given a platform in which processors are 1+α/2 times faster and (ii) SA-P succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which processors are 1+α times faster. The parameter 0<α≤1 is a property of the task set; it is the maximum of all the task utilizations that are no greater than 1. We evaluate average-case performance of both the algorithms by generating task sets randomly and measuring how much faster processors the algorithms need (which is upper bounded by 1+α/2 for SA and 1+α for SA-P) in order to output a feasible task assignment (intra-migrative for SA and non-migrative for SA-P). In our evaluations, for the vast majority of task sets, these algorithms require significantly smaller processor speedup than indicated by their theoretical bounds. Finally, we consider a special case where no task utilization in the given task set can exceed one and for this case, we (re-)prove the performance guarantees of SA and SA-P. We show, for both of the algorithms, that changing the adversary from intra-migrative to a more powerful one, namely fully-migrative, in which tasks can migrate between processors of any type, does not deteriorate the performance guarantees. For this special case, we compare the average-case performance of SA-P and a state-of-the-art algorithm by generating task sets randomly. In our evaluations, SA-P outperforms the state-of-the-art by requiring much smaller processor speedup and by running orders of magnitude faster.

Task Assignment Algorithms for Heterogeneous Multiprocessors

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising a constant number (denoted by t) of distinct types of processors—such a platform is referred to as a t-type platform. We present two algorithms, LPGIM and LPGNM, each providing the following guarantee. For a given t-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet their deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then: (i) LPGIM succeeds in finding such an assignment where the same restriction on task migration applies (intra-migrative) but given a platform in which only one processor of each type is 1 + α × t-1/t times faster and (ii) LPGNM succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which every processor is 1 + α times faster. The parameter α is a property of the task set; it is the maximum of all the task utilizations that are no greater than one. To the best of our knowledge, for t-type heterogeneous multiprocessors: (i) for the problem of intra-migrative task assignment, no previous algorithm exists with a proven bound and hence our algorithm, LPGIM, is the first of its kind and (ii) for the problem of non-migrative task assignment, our algorithm, LPGNM, has superior performance compared to state-of-the-art.

Estrogen receptor dependent genetic and epigenetic factors of tamoxifen resistance

Resumo: A decisão da terapêutica hormonal no tratamento do cancro da mama baseiase na determinação do receptor de estrogénio alfa por imunohistoquímica (IHC). Contudo, a presença deste receptor não prediz a resposta em todas as situações, em parte devido a limitações do método IHC. Investigámos se a expressão dos genes ESR1 e ESR2, bem como a metilação dos respectivos promotores, pode estar relacionada com a evolução desfavorável de uma proporção de doentes tratados com tamoxifeno assim como com a perda dos receptores de estrogénio alfa (ERα) e beta (ERß). Amostras de 211 doentes com cancro da mama diagnosticado entre 1988 e 2004, fixadas em formalina e preservadas em parafina, foram utilizadas para a determinação por IHC da presença dos receptores ERα e ERß. O mRNA total do gene ESR1 e os níveis específicos do transcrito derivado do promotor C (ESR1_C), bem como dos transcritos ESR2_ß1, ESR2_ß2/cx, and ESR2_ß5 foram avaliados por Real-time PCR. Os promotores A e C do gene ESR1 e os promotores 0K e 0N do gene ESR2 foram investigados por análise de metilação dos dinucleotidos CpG usando bisulfite-PCR para análise com enzimas de restrição, ou para methylation specific PCR. Atendendo aos resultados promissores relacionados com a metilação do promotor do gene ESR1, complementamos o estudo com um método quantitativo por matrix-assisted laser desorption/ionization time-of-flight mass spectrometry (MALDI-TOF MS) suportado pelo software Epityper para a medição da metilação nos promotores A e C. Fez-se a avaliação da estabilidade do mRNA nas linhas celulares de cancro da mama MCF-7 e MDA-MB-231 tratadas com actinomicina D. Baixos níveis do transcrito ESR1_C associaram-se a uma melhor sobrevivência global (p = 0.017). Níveis elevados do transcrito ESR1_C associaram-se a uma resposta inferior ao tamoxifeno (HR = 2.48; CI 95% 1.24-4.99), um efeito mais pronunciado em doentes com tumores de fenótipo ERα/PgR duplamente positivo (HR = 3.41; CI 95% 1.45-8.04). A isoforma ESR1_C mostrou ter uma semi-vida prolongada, bem como uma estrutura secundária da região 5’UTR muito mais relaxada em comparação com a isoforma ESR1_A. A análise por Western-blot mostrou que ao nível da 21 proteína, a selectividade de promotores é indistinguivel. Não se detectou qualquer correlação entre os níveis das isoformas do gene ESR2 ou entre a metilação dos promotores do gene ESR2, e a detecção da proteína ERß. A metilação do promotor C do gene ESR1, e não do promotor A, foi responsável pela perda do receptor ERα. Estes resultados sugerem que os níveis do transcrito ESR1_C sejam usados como um novo potencial marcador para o prognóstico e predição de resposta ao tratamento com tamoxifeno em doentes com cancro da mama. Abstract: The decision of endocrine breast cancer treatment relies on ERα IHC-based assessment. However, ER positivity does not predict response in all cases in part due to IHC methodological limitations. We investigated whether ESR1 and ESR2 gene expression and respective promoter methylation may be related to non-favorable outcome of a proportion of tamoxifen treated patients as well as to ERα and ERß loss. Formalin-fixed paraffin-embedded breast cancer samples from 211 patients diagnosed between 1988 and 2004 were submitted to IHC-based ERα and ERß protein determination. ESR1 whole mRNA and promoter C specific transcript levels, as well as ESR2_ß1, ESR2_ß2/cx, and ESR2_ß5 transcripts were assessed by real-time PCR. ESR1 promoters A and C, and ESR2 promoters 0N and 0K were investigated by CpG methylation analysis using bisulfite-PCR for restriction analysis, or methylation specific PCR. Due to the promising results related to ESR1 promoter methylation, we have used a quantification method by matrixassisted laser desorption/ionization time-of-flight mass spectrometry (MALDITOF MS) together with Epityper software to measure methylation at promoters A and C. mRNA stability was assessed in actinomycin D treated MCF-7 and MDA-MB-231 cells. ERα protein was quantified using transiently transfected breast cancer cells. Low ESR1_C transcript levels were associated with better overall survival (p = 0.017). High levels of ESR1_C transcript were associated with non-favorable response in tamoxifen treated patients (HR = 2.48; CI 95% 1.24-4.99), an effect that was more pronounced in patients with ERα/PgR double-positive tumors (HR = 3.41; CI 95% 1.45-8.04). The ESR1_C isoform had a prolonged mRNA half-life and a more relaxed 5’UTR structure compared to ESR1_A isoform. Western-blot analysis showed that at protein level, the promoter selectivity is undistinguishable. There was no correlation between levels of ESR2 isoforms or ESR2 promoter methylation and ERß protein staining. ESR1 promoter C CpG methylation and not promoter A was responsible for ERα loss. We propose ESR1_C levels as a putative novel marker for breast cancer prognosis and prediction of tamoxifen response.

Genetic structure of Neisseria meningitidis serogroup C epidemic strains in South Brazil

In the present study we report the results of an analysis, based on serotyping, multilocus enzyme electrophoresis (MEE), and ribotyping of N. meningitidis serogroup C strains isolated from patients with meningococcal disease (MD) in Rio Grande do Sul (RS) and Santa Catarina (SC) States, Brazil, as the Center of Epidemiology Control of Ministry of Health detected an increasing of MD cases due to this serogroup in the last two years (1992-1993). We have demonstrated that the MD due to N.meningitidis serogroup C strains in RS and SC States occurring in the last 4 years were caused mainly by one clone of strains (ET 40), with isolates indistinguishable by serogroup, serotype, subtype and even by ribotyping. One small number of cases that were not due to an ET 40 strains, represent closely related clones that probably are new lineages generated from the ET 40 clone referred as ET 11A complex. We have also analyzed N.meningitidis serogroup C strains isolated in the greater São Paulo in 1976 as representative of the first post epidemic year in that region. The ribotyping method, as well as MEE, could provide useful information about the clonal characteristics of those isolates and also of strains isolated in south Brazil. The strains from 1976 have more similarity with the actual endemic than epidemic strains, by the ribotyping, sulfonamide sensitivity, and MEE results. In conclusion, serotyping with monoclonal antibodies (C:2b:P1.3), MEE (ET 11 and ET 11A complex), and ribotyping by using ClaI restriction enzyme (Rb2), were useful to characterize these epidemic strains of N.meningitidis related to the increased incidence of MD in different States of south Brazil. It is mostly probable that these N.meningitidis serogroup C strains have poor or no genetic corelation with 1971-1975 epidemic serogroup C strains. The genetic similarity of members of the ET 11 and ET 11A complex were confirmed by the ribotyping method by using three restriction endonucleases.

Genetic relationships of Corynebacterium diphtheriae strains isolated from a diphtheria case and carriers by restriction fragment length polymorphism of rRNA genes

In the present study we report the results of an analysis, based on ribotyping of Corynebacterium diphtheriae intermedius strains isolated from a 9 years old child with clinical diphtheria and his 5 contacts. Quantitative analysis of RFLPs of rRNA was used to determine relatedness of these 7 C.diphtheriae strains providing support data in the diphtheria epidemiology. We have also tested those strains for toxigenicity in vitro by using the Elek's gel diffusion method and in vivo by using cell culture method on cultured monkey kidney cell (VERO cells). The hybridization results revealed that the 5 C.diphtheriae strains isolated from contacts and one isolated from the clinical case (nose case strain) had identical RFLP patterns with all 4 restriction endonucleases used, ribotype B. The genetic distance from this ribotype and ribotype A (throat case strain), that we initially assumed to be responsible for the illness of the patient, was of 0.450 showing poor genetic correlation among these two ribotypes. We found no significant differences concerned to the toxin production by using the cell culture method. In conclusion, the use of RFLPs of rRNA gene was successful in detecting minor differences in closely related toxigenic C.diphtheriae intermedius strains and providing information about genetic relationships among them.

Algorithms for time series clustering applied to biomedical signals

Thesis submitted in the fulfillment of the requirements for the Degree of Master in Biomedical Engineering

Genetic diversity of arginine catabolic mobile element in Staphylococcus epidermidis

PLos One, 4(11): ARTe7722