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.

FAST, PARALLEL AND SECURE CRYPTOGRAPHY ALGORITHM USING LORENZ`S ATTRACTOR

A novel cryptography method based on the Lorenz`s attractor chaotic system is presented. The proposed algorithm is secure and fast, making it practical for general use. We introduce the chaotic operation mode, which provides an interaction among the password, message and a chaotic system. It ensures that the algorithm yields a secure codification, even if the nature of the chaotic system is known. The algorithm has been implemented in two versions: one sequential and slow and the other, parallel and fast. Our algorithm assures the integrity of the ciphertext (we know if it has been altered, which is not assured by traditional algorithms) and consequently its authenticity. Numerical experiments are presented, discussed and show the behavior of the method in terms of security and performance. The fast version of the algorithm has a performance comparable to AES, a popular cryptography program used commercially nowadays, but it is more secure, which makes it immediately suitable for general purpose cryptography applications. An internet page has been set up, which enables the readers to test the algorithm and also to try to break into the cipher.

Recovery of p-TBC from a butadiene washing stream in a pilot plant

Results obtained in a pilot-scale unit designed for COD removal and p-TBC (p-tert-butylcatechol) recovery from a butadiene washing stream (pH 14, 200,000 mg COD L-1, highly toxic) at a petrochemical industry are presented. By adding H3PO4, phase separation is achieved and p-TBC is successfully recovered (88 g L-1 of washing stream). Information (time for phase separation and organic phase characterization) was gathered for designing a future industrial unit. The estimated heat generation rate was 990 kJ min-1 and 15 min were enough to promote phase separation for a liquid column of approximately 1.15 m.

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.

Land-Water interactions in the amazon

Biogeochemistry is hosting this special thematic issue devoted to studies of land-water interactions, as part of the Large-scale Biosphere-Atmosphere Experiment in Amaznia (LBA). This compilation of papers covers a broad range of topics with a common theme of coupling land and water processes, across pristine and impacted systems. Findings highlighted that hydrologic flowpaths are clearly important across basin size and structure in determining how water and solutes reach streams. Land-use changes have pronounced impacts on flowpaths, and subsequently, on stream chemistry, from small streams to large rivers. Carbon is produced and transformed across a broad array of fluvial environments and wetlands. Surface waters are not only driven by, but provide feedback to, the atmosphere.

Influence of land-use change on near-surface hydrological processes: Undisturbed forest to pasture

Soil compaction that follows the clearing of tropical forest for cattle pasture is associated with lower soil hydraulic conductivity and increased frequency and volume of overland flow. We investigated the frequency of perched water tables, overland flow and stormflow in an Amazon forest and in an adjacent 25-year-old pasture cleared from the same forest. We compared the results with the frequencies of these phenomena estimated from comparisons of rainfall intensity and soil hydraulic conductivity. The frequency of perched water tables based on rainfall intensity and soil hydraulic conductivity was expected to double in pasture compared with forest. This corresponded closely with an approximate doubling of the frequency of stormflow and overland flow in pasture. In contrast, the stormflow volume in pasture increased 17-fold. This disproportional increase of stormflow resulted from overland flow generation over large areas of pasture, while overland flow generation in the forest was spatially limited and was observed only very near the stream channel. In both catchments, stormflow was generated by saturation excess because of perched water tables and near-surface groundwater levels. Stormflow was occasionally generated in the forest by rapid return flow from macropores, while slow return flow from a continuous perched water table was more common in the pasture. These results suggest that deforestation for pasture alters fundamental mechanisms of stormflow generation and may increase runoff volumes over wide regions of Amazonia. (C) 2009 Elsevier B.V. All rights reserved.

Amazon deforestation alters small stream structure, nitrogen biogeochemistry and connectivity to larger rivers

Human activities that modify land cover can alter the structure and biogeochemistry of small streams but these effects are poorly known over large regions of the humid tropics where rates of forest clearing are high. We examined how conversion of Amazon lowland tropical forest to cattle pasture influenced the physical and chemical structure, organic matter stocks and N cycling of small streams. We combined a regional ground survey of small streams with an intensive study of nutrient cycling using (15)N additions in three representative streams: a second-order forest stream, a second-order pasture stream and a third-order pasture stream. These three streams were within several km of each other and on similar soils. Replacement of forest with pasture decreased stream habitat complexity by changing streams from run and pool channels with forest leaf detritus (50% cover) to grass-filled (63% cover) channel with runs of slow-moving water. In the survey, pasture streams consistently had lower concentrations of dissolved oxygen and nitrate (NO(3) (-)) compared with similar-sized forest streams. Stable isotope additions revealed that second-order pasture stream had a shorter NH(4) (+) uptake length, higher uptake rates into organic matter components and a shorter (15)NH(4) (+) residence time than the second-order forest stream or the third-order pasture stream. Nitrification was significant in the forest stream (19% of the added (15)NH(4) (+)) but not in the second-order pasture (0%) or third-order (6%) pasture stream. The forest stream retained 7% of added (15)N in organic matter compartments and exported 53% ((15)NH(4) (+) = 34%; (15)NO(3) (-) = 19%). In contrast, the second-order pasture stream retained 75% of added (15)N, predominantly in grasses (69%) and exported only 4% as (15)NH(4) (+). The fate of tracer (15)N in the third-order pasture stream more closely resembled that in the forest stream, with 5% of added N retained and 26% exported ((15)NH(4) (+) = 9%; (15)NO(3) (-) = 6%). These findings indicate that the widespread infilling by grass in small streams in areas deforested for pasture greatly increases the retention of inorganic N in the first- and second-order streams, which make up roughly three-fourths of total stream channel length in Amazon basin watersheds. The importance of this phenomenon and its effect on N transport to larger rivers across the larger areas of the Amazon Basin will depend on better evaluation of both the extent and the scale at which stream infilling by grass occurs, but our analysis suggests the phenomenon is widespread.