Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Improving the tracking capability of adaptive filters via convex combination

As is well known, Hessian-based adaptive filters (such as the recursive-least squares algorithm (RLS) for supervised adaptive filtering, or the Shalvi-Weinstein algorithm (SWA) for blind equalization) converge much faster than gradient-based algorithms [such as the least-mean-squares algorithm (LMS) or the constant-modulus algorithm (CMA)]. However, when the problem is tracking a time-variant filter, the issue is not so clear-cut: there are environments for which each family presents better performance. Given this, we propose the use of a convex combination of algorithms of different families to obtain an algorithm with superior tracking capability. We show the potential of this combination and provide a unified theoretical model for the steady-state excess mean-square error for convex combinations of gradient- and Hessian-based algorithms, assuming a random-walk model for the parameter variations. The proposed model is valid for algorithms of the same or different families, and for supervised (LMS and RLS) or blind (CMA and SWA) algorithms.

Noninvasive Evaluation of Oral Lesions Using Depth-sensitive Optical Spectroscopy

BACKGROUND: Optical spectroscopy is a noninvasive technique with potential applications for diagnosis of oral dysplasia and early cancer. In this study, we evaluated the diagnostic performance of a depth-sensitive optical spectroscopy (DSOS) system for distinguishing dysplasia and carcinoma from non-neoplastic oral mucosa. METHODS: Patients with oral lesions and volunteers without any oral abnormalities were recruited to participate. Autofluorescence and diffuse reflectance spectra of selected oral sites were measured using the DSOS system. A total of 424 oral sites in 124 subjects were measured and analyzed, including 154 sites in 60 patients with oral lesions and 270 sites in 64 normal volunteers. Measured optical spectra were used to develop computer-based algorithms to identify the presence of dysplasia or cancer. Sensitivity and specificity were calculated using a gold standard of histopathology for patient sites and clinical impression for normal volunteer sites. RESULTS: Differences in oral spectra were observed in: (1) neoplastic versus nonneoplastic sites, (2) keratinized versus nonkeratinized tissue, and (3) shallow versus deep depths within oral tissue. Algorithms based on spectra from 310 nonkeratinized anatomic sites (buccal, tongue, floor of mouth, and lip) yielded an area under the receiver operating characteristic curve of 0.96 in the training set and 0.93 in the validation set. CONCLUSIONS: The ability to selectively target epithelial and shallow stromal depth regions appeared to be diagnostically useful. For nonkeratinized oral sites, the sensitivity and specificity of this objective diagnostic technique were comparable to that of clinical diagnosis by expert observers. Thus, DSOS has potential to augment oral cancer screening efforts in community settings. Cancer 2009;115:1669-79. (C) 2009 American Cancer Society.

Merluccius hubbsi (Teleostei: Merlucciidae): stock identification based on reproductive biology in the south-southeast brazilian region

The Argentine hake, Merluccius hubbsi, a demersal-pelagic species found from Rio de Janeiro, Brazil to the Tierra del Fuego, Argentina, has become an important target of the Brazilian bottom-trawler fleet since 2001. Earlier studies focusing on the species have suggested that more than one stock might occur off the Brazilian coast, in accordance with environmental features. In order to evaluate this hypothesis, fish were collected from four different areas in the Brazilian waters in which the hake is distributed, during the summers and winters of 1996-2001 and 2004, the females being used to analyze and compare spatial-temporal variations in ovarian maturation. Gonad indexes were also applied for the same purpose. Results indicate a north-south spawning gradient occurring as from summer at around 21°S to winter near 34°S, leading to the identification of two distinct stocks: one located between 21°S and 29°S (Southeastern stock) and the other between 29°S and 34°S (Southern stock), this latter shared with Uruguay and Argentina. Brazilian stocks present clear signs of overexploitation, the situation calling for an urgent solution.

Species determination of Brazilian mammals implicated in the epidemiology of rabies based on the control region of mitochondrial DNA

Identification of animals that are decomposing or have been run over or burnt and cannot be visually identified is a problem in the surveillance and control of infectious diseases. Many of these animals are wild and represent a valuable source of information for epidemiologic research as they may be carriers of an infectious agent. This article discusses the results obtained using a method for identifying mammals genetically by sequencing their mitochondrial DNA control region. Fourteen species were analyzed and identified. These included the main reservoirs and transmitters of rabies virus, namely, canids, chiroptera and primates. The results prove that this method of genetic identification is both efficient and simple and that it can be used in the surveillance of infectious diseases which includes mammals in their epidemiologic cycle, such as rabies.

Spectral Region Optimization for Raman-Based Optical Biopsy of Inflammatory Lesions

Objective: The biochemical alterations between inflammatory fibrous hyperplasia (IFH) and normal tissues of buccal mucosa were probed by using the FT-Raman spectroscopy technique. The aim was to find the minimal set of Raman bands that would furnish the best discrimination. Background: Raman-based optical biopsy is a widely recognized potential technique for noninvasive real-time diagnosis. However, few studies had been devoted to the discrimination of very common subtle or early pathologic states as inflammatory processes that are always present on, for example, cancer lesion borders. Methods: Seventy spectra of IFH from 14 patients were compared with 30 spectra of normal tissues from six patients. The statistical analysis was performed with principal components analysis and soft independent modeling class analogy cross-validated, leave-one-out methods. Results: Bands close to 574, 1,100, 1,250 to 1,350, and 1,500 cm(-1) (mainly amino acids and collagen bands) showed the main intragroup variations that are due to the acanthosis process in the IFH epithelium. The 1,200 (C-C aromatic/DNA), 1,350 (CH(2) bending/collagen 1), and 1,730 cm(-1) (collagen III) regions presented the main intergroup variations. This finding was interpreted as originating in an extracellular matrix-degeneration process occurring in the inflammatory tissues. The statistical analysis results indicated that the best discrimination capability (sensitivity of 95% and specificity of 100%) was found by using the 530-580 cm(-1) spectral region. Conclusions: The existence of this narrow spectral window enabling normal and inflammatory diagnosis also had useful implications for an in vivo dispersive Raman setup for clinical applications.

Phylogenetic relationships in Solanaceae and related species based on cpDNA sequence from plastid trnE-trnT region

Intergenic spacers of chloroplast DNA (cpDNA) are very useful in phylogenetic and population genetic studies of plant species, to study their potential integration in phylogenetic analysis. The non-coding trnE-trnT intergenic spacer of cpDNA was analyzed to assess the nucleotide sequence polymorphism of 16 Solanaceae species and to estimate its ability to contribute to the resolution of phylogenetic studies of this group. Multiple alignments of DNA sequences of trnE-trnT intergenic spacer made the identification of nucleotide variability in this region possible and the phylogeny was estimated by maximum parsimony and rooted with Convolvulaceae Ipomoea batalas, the most closely related family. Besides, this intergenic spacer was tested for the phylogenetic ability to differentiate taxonomic levels. For this purpose, species from four other families were analyzed and compared with Solanaceae species. Results confirmed polymorphism in the trnE-trnT region at different taxonomic levels.

Development of Hepatitis C Virus Genotyping by Real-Time PCR Based on the NS5B Region

Background: Hepatitis C virus (HCV) genotyping is the most significant predictor of the response to antiviral therapy. The aim of this study was to develop and evaluate a novel real-time PCR method for HCV genotyping based on the NS5B region. Methodology/Principal Findings: Two triplex reaction sets were designed, one to detect genotypes 1a, 1b and 3a; and another to detect genotypes 2a, 2b, and 2c. This approach had an overall sensitivity of 97.0%, detecting 295 of the 304 tested samples. All samples genotyped by real-time PCR had the same type that was assigned using LiPA version 1 (Line in Probe Assay). Although LiPA v. 1 was not able to subtype 68 of the 295 samples (23.0%) and rendered different subtype results from those assigned by real-time PCR for 12/295 samples (4.0%), NS5B sequencing and real-time PCR results agreed in all 146 tested cases. Analytical sensitivity of the real-time PCR assay was determined by end-point dilution of the 5000 IU/ml member of the OptiQuant HCV RNA panel. The lower limit of detection was estimated to be 125 IU/ml for genotype 3a, 250 IU/ml for genotypes 1b and 2b, and 500 IU/ml for genotype 1a. Conclusions/Significance: The total time required for performing this assay was two hours, compared to four hours required for LiPA v. 1 after PCR-amplification. Furthermore, the estimated reaction cost was nine times lower than that of available commercial methods in Brazil. Thus, we have developed an efficient, feasible, and affordable method for HCV genotype identification.

Genotypic Characteristics of HIV Type 1 Based on gp120 Hypervariable Region 3 of Isolates from Southern Brazil

The aim of this study was to investigate HIV-1 molecular diversity and the epidemiological profile of HIV-1-infected patients from Ribeirao Preto, Brazil. A nested PCR followed by sequencing of a 302-base pair fragment of the env gene (C2-V3 region) was performed in samples from HIV-1-positive patients. A total of 45 sequences were aligned with final manual adjustments. The phylogenetic analyses showed a higher prevalence of HIV-1 subtype B in the studied population (97.8%) with only one sample yielding an F1 subtype. The viral genotyping prediction showed that CCR5 tropism was the most prevalent in the studied cohort. Geno2pheno analysis showed that R5 and CXCR4 prediction were 69% and 31%, respectively. There was no statistical significance, either in viral load or in CD4(+) T cell count when R5 and X4 prediction groups were compared. Moreover, the GPGR tetramer was the most common V3 loop core motif identified in the HIV-1 strains studied (34.1%) followed by GWGR, identified in 18.1% of the samples. The high level of B subtype in this Brazilian population reinforces the nature of the HIV epidemic in Brazil, and corroborates previous data obtained in the Brazilian HIV-infected population.

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.

GOOAL: A routine based on Genetic Algorithms to track harmonics in electric power systems

Voltage and current waveforms of a distribution or transmission power system are not pure sinusoids. There are distortions in these waveforms that can be represented as a combination of the fundamental frequency, harmonics and high frequency transients. This paper presents a novel approach to identifying harmonics in power system distorted waveforms. The proposed method is based on Genetic Algorithms, which is an optimization technique inspired by genetics and natural evolution. GOOAL, a specially designed intelligent algorithm for optimization problems, was successfully implemented and tested. Two kinds of representations concerning chromosomes are utilized: binary and real. The results show that the proposed method is more precise than the traditional Fourier Transform, especially considering the real representation of the chromosomes.

Most of the patients presenting myocardial infarction would not be eligible for intensive lipid-lowering based on clinical algorithms or plasma C-reactive protein

Objective: The study we assessed how often patients who are manifesting a myocardial infarction (MI) would not be considered candidates for intensive lipid-lowering therapy based on the current guidelines. Methods: In 355 consecutive patients manifesting ST elevation MI (STEMI), admission plasma C-reactive protein (CRP) was measured and Framingham risk score (FRS), PROCAM risk score, Reynolds risk score, ASSIGN risk score, QRISK, and SCORE algorithms were applied. Cardiac computed tomography and carotid ultrasound were performed to assess the coronary artery calcium score (CAC), carotid intima-media thickness (cIMT) and the presence of carotid plaques. Results: Less than 50% of STEMI patients would be identified as having high risk before the event by any of these algorithms. With the exception of FRS (9%), all other algorithms would assign low risk to about half of the enrolled patients. Plasma CRP was <1.0 mg/L in 70% and >2 mg/L in 14% of the patients. The average cIMT was 0.8 +/- 0.2 mm and only in 24% of patients was >= 1.0 mm. Carotid plaques were found in 74% of patients. CAC > 100 was found in 66% of patients. Adding CAC >100 plus the presence of carotid plaque, a high-risk condition would be identified in 100% of the patients using any of the above mentioned algorithms. Conclusion: More than half of patients manifesting STEMI would not be considered as candidates for intensive preventive therapy by the current clinical algorithms. The addition of anatomical parameters such as CAC and the presence of carotid plaques can substantially reduce the CVD risk underestimation. (C) 2010 Elsevier Ireland Ltd. All rights reserved.

MHM assay: molecular sexing based on the sex-specific methylation pattern of the MHM region in chickens

Bird sex determination using molecular methods has proved to be a valuable tool in different studies. Although it is possible to sex most birds by coupling the CHD assay with others available methods, no sex-determining gene like SRY in mammalians has been identified in birds. The male hypermethylated (MHM) region on the Z chromosome has been found to be hypermethylated in males and hypomethylated in females in birds of the order Galliformes. We analyzed the DNA from feathers of 50 adult chickens to verify the methylation pattern of the MHM region by PCR and the restriction enzyme HpaII (a method named MHM assay). The results, visualized in agarose gel, were compared with PCR amplification of the CHD-Z and CHD-W genes (polyacrylamide gel) and with the birds` phenotype. All males (25) showed hypermethylation of the MHM region, and all females (25) showed hypomethylation. The sexing by MHM assay was in according with phenotype and CHD sexing. To our knowledge, this is the first study that uses the MHM region for sexing birds. Although the real role of the MHM region in the sex determination is still unclear, this could be a universal marker for sexing birds and may be involved in sex determination by its influence on transcriptional processes. The MHM assay could be a good alternative for CHD assay in developmental studies.

Comparative analysis of rabies virus isolates from Brazilian canids and bats based on the G gene and G-L intergenic region

Rabies virus (RABV) isolates from two species of canids and three species of bats were analyzed by comparing the C-terminal region of the G gene and the G-L intergenic region of the virus genome. Intercluster identities for the genetic sequences of the isolates showed both regions to be poorly conserved. Phylogenetic trees were generated by the neighbor-joining and maximum parsimony methods, and the results were found to agree between the two methods for both regions. Putative amino acid sequences obtained from the G gene were also analyzed, and genetic markers were identified. Our results suggest that different genetic lineages of RABV are adapted to different animal species in Brazil.

A new species of the genus Pimelerodius Vanin from the Amazon Region, with notes on the geografic distribution of Pimelerodius motacilla (Boheman) (Coleoptera, Curculionidae, Otidocephalini)

Pimelerodius punctiventris sp. nov. (type locality Brazil, Amazonas, Itacoatiara) is described and illustrated. The new taxon is compared with similar species, being distinguished from the other 12 known species of the genus by the presence of punctures in ventrite I. The available published key for identification of species of Pimelerodius is adapted to include the new species. A modification of the generic description of the aedeagus of Pimelerodius is provided, a necessity due to the differences observed in the aedeagus of the new species. The occurrence of P. motacilla (Boheman, 1843) in the Amazon Region, recorded in sympatry with P. punctiventris in Itacoatiara, AM, is discussed and confirmed, based on the study of 41 available specimens.