An all-substrings common subsequence algorithm

Given two strings A and B of lengths n(a) and n(b), n(a) <= n(b), respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring B` of B, the length of the longest string that is a subsequence of both A and B. The ALCS problem has many applications, such as finding approximate tandem repeats in strings, solving the circular alignment of two strings and finding the alignment of one string with several others that have a common substring. We present an algorithm to prepare the basic data structure for ALCS queries that takes O(n(a)n(b)) time and O(n(a) + n(b)) space. After this preparation, it is possible to build that allows any LCS length to be retrieved in constant time. Some trade-offs between the space required and a matrix of size O(n(b)(2)) the querying time are discussed. To our knowledge, this is the first algorithm in the literature for the ALCS problem. (C) 2007 Elsevier B.V. All rights reserved.

Estimating HIV-1 incidence using the serologic testing algorithm for recent HIV infections at HIV counseling and testing centers in the city of São Paulo, Brazil

The network of HIV counseling and testing centers in São Paulo, Brazil is a major source of data used to build epidemiological profiles of the client population. We examined HIV-1 incidence from November 2000 to April 2001, comparing epidemiological and socio-behavioral data of recently-infected individuals with those with long-standing infection. A less sensitive ELISA was employed to identify recent infection. The overall incidence of HIV-1 infection was 0.53/100/year (95% CI: 0.31-0.85/100/year): 0.77/100/year for males (95% CI: 0.42-1.27/100/year) and 0.22/100/ year (95% CI: 0.05-0.59/100/year) for females. Overall HIV-1 prevalence was 3.2% (95% CI: 2.8-3.7%), being 4.0% among males (95% CI: 3.3-4.7%) and 2.1% among females (95% CI: 1.6-2.8%). Recent infections accounted for 15% of the total (95% CI: 10.2-20.8%). Recent infection correlated with being younger and male (p = 0.019). Therefore, recent infection was more common among younger males and older females.

A Vaccine Encoding Conserved Promiscuous HIV CD4 Epitopes Induces Broad T Cell Responses in Mice Transgenic to Multiple Common HLA Class II Molecules

Current HIV vaccine approaches are focused on immunogens encoding whole HIV antigenic proteins that mainly elicit cytotoxic CD8+ responses. Mounting evidence points toward a critical role for CD4+ T cells in the control of immunodeficiency virus replication, probably due to cognate help. Vaccine-induced CD4+ T cell responses might, therefore, have a protective effect in HIV replication. In addition, successful vaccines may have to elicit responses to multiple epitopes in a high proportion of vaccinees, to match the highly variable circulating strains of HIV. Using rational vaccine design, we developed a DNA vaccine encoding 18 algorithm-selected conserved, ""promiscuous"" ( multiple HLA-DR-binding) B-subtype HIV CD4 epitopes - previously found to be frequently recognized by HIV-infected patients. We assessed the ability of the vaccine to induce broad T cell responses in the context of multiple HLA class II molecules using different strains of HLA class II-transgenic mice (-DR2, -DR4, -DQ6 and -DQ8). Mice displayed CD4+ and CD8+ T cell responses of significant breadth and magnitude, and 16 out of the 18 encoded epitopes were recognized. By virtue of inducing broad responses against conserved CD4+ T cell epitopes that can be recognized in the context of widely diverse, common HLA class II alleles, this vaccine concept may cope both with HIV genetic variability and increased population coverage. The vaccine may thus be a source of cognate help for HIV-specific CD8+ T cells elicited by conventional immunogens, in a wide proportion of vaccinees.

Scheduling in a two-machine flowshop for the minimization of the mean absolute deviation from a common due date

This paper addresses the minimization of the mean absolute deviation from a common due date in a two-machine flowshop scheduling problem. We present heuristics that use an algorithm, based on proposed properties, which obtains an optimal schedule fora given job sequence. A new set of benchmark problems is presented with the purpose of evaluating the heuristics. Computational experiments show that the developed heuristics outperform results found in the literature for problems up to 500 jobs. (C) 2007 Elsevier Ltd. All rights reserved.

The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm

This paper addresses the single machine scheduling problem with a common due date aiming to minimize earliness and tardiness penalties. Due to its complexity, most of the previous studies in the literature deal with this problem using heuristics and metaheuristics approaches. With the intention of contributing to the study of this problem, a branch-and-bound algorithm is proposed. Lower bounds and pruning rules that exploit properties of the problem are introduced. The proposed approach is examined through a computational comparative study with 280 problems involving different due date scenarios. In addition, the values of optimal solutions for small problems from a known benchmark are provided.

Combining Legendre's Polynomials and Genetic Algorithm in the Solution of Nonlinear Initial-Value Problems

This work develops a method for solving ordinary differential equations, that is, initial-value problems, with solutions approximated by using Legendre's polynomials. An iterative procedure for the adjustment of the polynomial coefficients is developed, based on the genetic algorithm. This procedure is applied to several examples providing comparisons between its results and the best polynomial fitting when numerical solutions by the traditional Runge-Kutta or Adams methods are available. The resulting algorithm provides reliable solutions even if the numerical solutions are not available, that is, when the mass matrix is singular or the equation produces unstable running processes.

Skewed Distribution of Circulating Activated Natural Killer T (NKT) Cells in Patients with Common Variable Immunodeficiency Disorders (CVID)

Common variable immunodeficiency disorder (CVID) is the commonest cause of primary antibody failure in adults and children, and characterized clinically by recurrent bacterial infections and autoimmune manifestations. Several innate immune defects have been described in CVID, but no study has yet investigated the frequency, phenotype or function of the key regulatory cell population, natural killer T (NKT) cells. We measured the frequencies and subsets of NKT cells in patients with CVID and compared these to healthy controls. Our results show a skewing of NKT cell subsets, with CD4+ NKT cells at higher frequencies, and CD8+ NKT cells at lower frequencies. However, these cells were highly activated and expression CD161. The NKT cells had a higher expression of CCR5 and concomitantly expression of CCR5+CD69+CXCR6 suggesting a compensation of the remaining population of NKT cells for rapid effector action.

Continental passive microwave-based rainfall estimation algorithm: Application to the Amazon Basin

This paper presents a new statistical algorithm to estimate rainfall over the Amazon Basin region using the Tropical Rainfall Measuring Mission (TRMM) Microwave Imager (TMI). The algorithm relies on empirical relationships derived for different raining-type systems between coincident measurements of surface rainfall rate and 85-GHz polarization-corrected brightness temperature as observed by the precipitation radar (PR) and TMI on board the TRMM satellite. The scheme includes rain/no-rain area delineation (screening) and system-type classification routines for rain retrieval. The algorithm is validated against independent measurements of the TRMM-PR and S-band dual-polarization Doppler radar (S-Pol) surface rainfall data for two different periods. Moreover, the performance of this rainfall estimation technique is evaluated against well-known methods, namely, the TRMM-2A12 [ the Goddard profiling algorithm (GPROF)], the Goddard scattering algorithm (GSCAT), and the National Environmental Satellite, Data, and Information Service (NESDIS) algorithms. The proposed algorithm shows a normalized bias of approximately 23% for both PR and S-Pol ground truth datasets and a mean error of 0.244 mm h(-1) ( PR) and -0.157 mm h(-1)(S-Pol). For rain volume estimates using PR as reference, a correlation coefficient of 0.939 and a normalized bias of 0.039 were found. With respect to rainfall distributions and rain area comparisons, the results showed that the formulation proposed is efficient and compatible with the physics and dynamics of the observed systems over the area of interest. The performance of the other algorithms showed that GSCAT presented low normalized bias for rain areas and rain volume [0.346 ( PR) and 0.361 (S-Pol)], and GPROF showed rainfall distribution similar to that of the PR and S-Pol but with a bimodal distribution. Last, the five algorithms were evaluated during the TRMM-Large-Scale Biosphere-Atmosphere Experiment in Amazonia (LBA) 1999 field campaign to verify the precipitation characteristics observed during the easterly and westerly Amazon wind flow regimes. The proposed algorithm presented a cumulative rainfall distribution similar to the observations during the easterly regime, but it underestimated for the westerly period for rainfall rates above 5 mm h(-1). NESDIS(1) overestimated for both wind regimes but presented the best westerly representation. NESDIS(2), GSCAT, and GPROF underestimated in both regimes, but GPROF was closer to the observations during the easterly flow.

Fast ray-tracing algorithm for circumstellar structures (FRACS) II. Disc parameters of the B[e] supergiant CPD-57 degrees 2874 from VLTI/MIDI data

Context. B[e] supergiants are luminous, massive post-main sequence stars exhibiting non-spherical winds, forbidden lines, and hot dust in a disc-like structure. The physical properties of their rich and complex circumstellar environment (CSE) are not well understood, partly because these CSE cannot be easily resolved at the large distances found for B[e] supergiants (typically greater than or similar to 1 kpc). Aims. From mid-IR spectro-interferometric observations obtained with VLTI/MIDI we seek to resolve and study the CSE of the Galactic B[e] supergiant CPD-57 degrees 2874. Methods. For a physical interpretation of the observables (visibilities and spectrum) we use our ray-tracing radiative transfer code (FRACS), which is optimised for thermal spectro-interferometric observations. Results. Thanks to the short computing time required by FRACS (<10 s per monochromatic model), best-fit parameters and uncertainties for several physical quantities of CPD-57 degrees 2874 were obtained, such as inner dust radius, relative flux contribution of the central source and of the dusty CSE, dust temperature profile, and disc inclination. Conclusions. The analysis of VLTI/MIDI data with FRACS allowed one of the first direct determinations of physical parameters of the dusty CSE of a B[e] supergiant based on interferometric data and using a full model-fitting approach. In a larger context, the study of B[e] supergiants is important for a deeper understanding of the complex structure and evolution of hot, massive stars.

Phylogeography of the common vampire bat (Desmodus rotundus): Marked population structure, Neotropical Pleistocene vicariance and incongruence between nuclear and mtDNA markers

Background: The common vampire bat Desmodus rotundus is an excellent model organism for studying ecological vicariance in the Neotropics due to its broad geographic range and its preference for forested areas as roosting sites. With the objective of testing for Pleistocene ecological vicariance, we sequenced a mitocondrial DNA (mtDNA) marker and two nuclear markers (RAG2 and DRB) to try to understand how Pleistocene glaciations affected the distribution of intraspecific lineages in this bat. Results: Five reciprocally monophyletic clades were evident in the mitochondrial gene tree, and in most cases with high bootstrap support: Central America (CA), Amazon and Cerrado (AMC), Pantanal (PAN), Northern Atlantic Forest (NAF) and Southern Atlantic Forest (SAF). The Atlantic forest clades formed a monophyletic clade with high bootstrap support, creating an east/west division for this species in South America. On the one hand, all coalescent and non-coalescent estimates point to a Pleistocene time of divergence between the clades. On the other hand, the nuclear markers showed extensive sharing of haplotypes between distant localities, a result compatible with male-biased gene flow. In order to test if the disparity between the mitochondrial and nuclear markers was due to the difference in mutation rate and effective size, we performed a coalescent simulation to examine the feasibility that, given the time of separation between the observed lineages, even with a gene flow rate close to zero, there would not be reciprocal monophyly for a neutral nuclear marker. We used the observed values of theta and an estimated mutation rate for the nuclear marker gene to perform 1000 iterations of the simulation. The results of this simulation were inconclusive: the number of iterations with and without reciprocal monophyly of one or more clades are similar. Conclusions: We therefore conclude that the pattern exhibited by the common vampire bat, with marked geographical structure for a mitochondrial marker and no phylogeographic structure for nuclear markers is compatible with a historical scenario of complete isolation of refuge-like populations during the Pleistocene. The results on demographic history on this species is compatible with the Carnaval-Moritz model of Pleistocene vicariance, with demographic expansions in the southern Atlantic forest.

Contribuition of nitrogen from biological nitrogen fixation, nitrogen fertilizer and soil nitrogen on the growth of the common bean and cowpea

Biological nitrogen fixation (BNF) constitutes a valuable source of this nutrient for the common bean Phaseolus vulgaris L and cowpea Vigna unguiculata (L.) Walp., being its avaibility affected by mineral N in the soil solution. The objectives of this work were to evaluate the effects of nitrogen rate, as urea, on symbiotic fixation of N(2) in common bean and cowpea plants, using the isotopic technique, and quantifying the relative contributions of N sources symbiotic N(2) fixation, soil native nitrogen and urea N on the growth of the common bean and cowpea. Non nodulating soybean plants were used as standard. The research was carried out in greenhouse, using pots with 5 kg of soil from a Typic Haplustox (Dystrophic Red Yellow Latosol). The experimental design was completely randomized blocks, with 30 treatments and three replications, arranged in 5x3x2 factorial outline. The treatments consisted of five N rates: 2, 15, 30, 45 and 60 mg N kg(-1) soil; three sampling times: 23, 40 and 76 days after sowing (DAS) and two crops: common bean and cowpea. The BNF decreased with increase N rates, varying from 81.5% to 55.6% for cowpea, and from 71.9% to 55.1% for common bean. The symbiotic N(2) fixation in cowpea can substitute totally the nitrogen fertilization. The nitrogen absorption from soil is not affected by nitrogen fertilizer rate. The N recovery from fertilizer at 76 DAS was of 60.7% by common bean, and 57.1% by cowpea. The symbiotic association in common bean needs the application of a starting dose (40 kg N ha(-1)) for economically acceptable yields.

Power Transformer Differential Protection Based on Clarke`s Transform and Fuzzy Systems

The power transformer is a piece of electrical equipment that needs continuous monitoring and fast protection since it is very expensive and an essential element for a power system to perform effectively. The most common protection technique used is the percentage differential logic, which provides discrimination between an internal fault and different operating conditions. Unfortunately, there are some operating conditions of power transformers that can affect the protection behavior and the power system stability. This paper proposes the development of a new algorithm to improve the differential protection performance by using fuzzy logic and Clarke`s transform. An electrical power system was modeled using Alternative Transients Program (ATP) software to obtain the operational conditions and fault situations needed to test the algorithm developed. The results were compared to a commercial relay for validation, showing the advantages of the new method.

Node-Depth Encoding and Multiobjective Evolutionary Algorithm Applied to Large-Scale Distribution System Reconfiguration

The power loss reduction in distribution systems (DSs) is a nonlinear and multiobjective problem. Service restoration in DSs is even computationally hard since it additionally requires a solution in real-time. Both DS problems are computationally complex. For large-scale networks, the usual problem formulation has thousands of constraint equations. The node-depth encoding (NDE) enables a modeling of DSs problems that eliminates several constraint equations from the usual formulation, making the problem solution simpler. On the other hand, a multiobjective evolutionary algorithm (EA) based on subpopulation tables adequately models several objectives and constraints, enabling a better exploration of the search space. The combination of the multiobjective EA with NDE (MEAN) results in the proposed approach for solving DSs problems for large-scale networks. Simulation results have shown the MEAN is able to find adequate restoration plans for a real DS with 3860 buses and 632 switches in a running time of 0.68 s. Moreover, the MEAN has shown a sublinear running time in function of the system size. Tests with networks ranging from 632 to 5166 switches indicate that the MEAN can find network configurations corresponding to a power loss reduction of 27.64% for very large networks requiring relatively low running time.

An algorithm for computerized automatic tuning of power system stabilizers

The main objective of this paper is to relieve the power system engineers from the burden of the complex and time-consuming process of power system stabilizer (PSS) tuning. To achieve this goal, the paper proposes an automatic process for computerized tuning of PSSs, which is based on an iterative process that uses a linear matrix inequality (LMI) solver to find the PSS parameters. It is shown in the paper that PSS tuning can be written as a search problem over a non-convex feasible set. The proposed algorithm solves this feasibility problem using an iterative LMI approach and a suitable initial condition, corresponding to a PSS designed for nominal operating conditions only (which is a quite simple task, since the required phase compensation is uniquely defined). Some knowledge about the PSS tuning is also incorporated in the algorithm through the specification of bounds defining the allowable PSS parameters. The application of the proposed algorithm to a benchmark test system and the nonlinear simulation of the resulting closed-loop models demonstrate the efficiency of this algorithm. (C) 2009 Elsevier Ltd. All rights reserved.

A novel multiobjective optimization algorithm based on bacterial chemotaxis

In this article a novel algorithm based on the chemotaxis process of Echerichia coil is developed to solve multiobjective optimization problems. The algorithm uses fast nondominated sorting procedure, communication between the colony members and a simple chemotactical strategy to change the bacterial positions in order to explore the search space to find several optimal solutions. The proposed algorithm is validated using 11 benchmark problems and implementing three different performance measures to compare its performance with the NSGA-II genetic algorithm and with the particle swarm-based algorithm NSPSO. (C) 2009 Elsevier Ltd. All rights reserved.