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.

Digital frequency relaying based on the modified least mean square method

This research presents a method for frequency estimation in power systems using an adaptive filter based on the Least Mean Square Algorithm (LMS). In order to analyze a power system, three-phase voltages were converted into a complex signal applying the alpha beta-transform and the results were used in an adaptive filtering algorithm. Although the use of the complex LMS algorithm is described in the literature, this paper deals with some practical aspects of the algorithm implementation. In order to reduce computing time, a coefficient generator was implemented. For the algorithm validation, a computing simulation of a power system was carried Out using the ATP software. Many different situations were Simulated for the performance analysis of the proposed methodology. The results were compared to a commercial relay for validation, showing the advantages of the new method. (C) 2009 Elsevier Ltd. All rights reserved.

Structural matching of 2D electrophoresis gels using deformed graphs

2D electrophoresis is a well-known method for protein separation which is extremely useful in the field of proteomics. Each spot in the image represents a protein accumulation and the goal is to perform a differential analysis between pairs of images to study changes in protein content. It is thus necessary to register two images by finding spot correspondences. Although it may seem a simple task, generally, the manual processing of this kind of images is very cumbersome, especially when strong variations between corresponding sets of spots are expected (e.g. strong non-linear deformations and outliers). In order to solve this problem, this paper proposes a new quadratic assignment formulation together with a correspondence estimation algorithm based on graph matching which takes into account the structural information between the detected spots. Each image is represented by a graph and the task is to find a maximum common subgraph. Successful experimental results using real data are presented, including an extensive comparative performance evaluation with ground-truth data. (C) 2010 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.

Percutaneous vertebroplasty for multiple myeloma of the cervical spine

Spinal involvement is a common presentation of multiple myeloma (MM); however, the cervical spine is the least common site of myelomatous involvement. Few studies evaluate the results of percutaneous vertebroplasty (PV) in the treatment of MM of the spine. The purpose of this series is to report on the use of PV in the treatment of MM of the cervical spine and to review the literature. From January 1994 to October 2007, four patients (three men and one woman; mean age, 45 years) who underwent five PV for painful MM in the cervical spine were retrospectively reviewed. The pain was estimated by the patient on a verbal analogic scale. Clinical follow-up was available for all patients (mean, 27.5 months; range, 1-96 months). The mean volume of cement injected per vertebral body was 2.3 +/- 0.8 mL (range, 1.0-4.0 mL) with a mean vertebral filling of 55.0 +/- 12.0% (range, 40.0-75.0%). Analgesic efficacy was achieved in all patients. One patient had a spinal instability due to a progression of spinal deformity noted on follow-up radiographs, without clinical symptoms. Cement leakage was detected in three (60%) of the five treated vertebrae. There was no clinical complication. The present series suggests that PV for MM of the cervical spine is safe and effective for pain control; nonetheless, the detrimental impact of the disease on bone quality should prompt close radiological follow-up after PV owing to the risk of spinal instability.

An Array Recursive Least-Squares Algorithm With Generic Nonfading Regularization Matrix

We present a novel array RLS algorithm with forgetting factor that circumvents the problem of fading regularization, inherent to the standard exponentially-weighted RLS, by allowing for time-varying regularization matrices with generic structure. Simulations in finite precision show the algorithm`s superiority as compared to alternative algorithms in the context of adaptive beamforming.

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.

Characterization of subgraph relationships and distribution in complex networks

A network can be analyzed at different topological scales, ranging from single nodes to motifs, communities, up to the complete structure. We propose a novel approach which extends from single nodes to the whole network level by considering non-overlapping subgraphs (i.e. connected components) and their interrelationships and distribution through the network. Though such subgraphs can be completely general, our methodology focuses on the cases in which the nodes of these subgraphs share some special feature, such as being critical for the proper operation of the network. The methodology of subgraph characterization involves two main aspects: (i) the generation of histograms of subgraph sizes and distances between subgraphs and (ii) a merging algorithm, developed to assess the relevance of nodes outside subgraphs by progressively merging subgraphs until the whole network is covered. The latter procedure complements the histograms by taking into account the nodes lying between subgraphs, as well as the relevance of these nodes to the overall subgraph interconnectivity. Experiments were carried out using four types of network models and five instances of real-world networks, in order to illustrate how subgraph characterization can help complementing complex network-based studies.

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.

Distributed Estimation Over an Adaptive Incremental Network Based on the Affine Projection Algorithm

We study the problem of distributed estimation based on the affine projection algorithm (APA), which is developed from Newton`s method for minimizing a cost function. The proposed solution is formulated to ameliorate the limited convergence properties of least-mean-square (LMS) type distributed adaptive filters with colored inputs. The analysis of transient and steady-state performances at each individual node within the network is developed by using a weighted spatial-temporal energy conservation relation and confirmed by computer simulations. The simulation results also verify that the proposed algorithm provides not only a faster convergence rate but also an improved steady-state performance as compared to an LMS-based scheme. In addition, the new approach attains an acceptable misadjustment performance with lower computational and memory cost, provided the number of regressor vectors and filter length parameters are appropriately chosen, as compared to a distributed recursive-least-squares (RLS) based method.

Stochastic stability analysis for the constant-modulus algorithm

We derive an easy-to-compute approximate bound for the range of step-sizes for which the constant-modulus algorithm (CMA) will remain stable if initialized close to a minimum of the CM cost function. Our model highlights the influence, of the signal constellation used in the transmission system: for smaller variation in the modulus of the transmitted symbols, the algorithm will be more robust, and the steady-state misadjustment will be smaller. The theoretical results are validated through several simulations, for long and short filters and channels.

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.

A spectral clustering algorithm for manufacturing cell formation

A graph clustering algorithm constructs groups of closely related parts and machines separately. After they are matched for the least intercell moves, a refining process runs on the initial cell formation to decrease the number of intercell moves. A simple modification of this main approach can deal with some practical constraints, such as the popular constraint of bounding the maximum number of machines in a cell. Our approach makes a big improvement in the computational time. More importantly, improvement is seen in the number of intercell moves when the computational results were compared with best known solutions from the literature. (C) 2009 Elsevier Ltd. All rights reserved.

CD4+T cells from HIV-1-infected patients recognize wild-type and mutant human immunodeficiency virus-1 protease epitopes

P>Human immunodeficiency virus (HIV)-1 protease is a known target of CD8+ T cell responses, but it is the only HIV-1 protein in which no fully characterized HIV-1 protease CD4 epitopes have been identified to date. We investigated the recognition of HIV-1 protease by CD4+ T cells from 75 HIV-1-infected, protease inhibitor (PI)-treated patients, using the 5,6-carboxyfluorescein diacetate succinimidyl ester-based proliferation assay. In order to identify putative promiscuous CD4+ T cell epitopes, we used the TEPITOPE algorithm to scan the sequence of the HXB2 HIV-1 protease. Protease regions 4-23, 45-64 and 73-95 were identified; 32 sequence variants of the mentioned regions, encoding frequent PI-induced mutations and polymorphisms, were also tested. On average, each peptide bound to five of 15 tested common human leucocyte antigen D-related (HLA-DR) molecules. More than 80% of the patients displayed CD4+ as well as CD8+ T cell recognition of at least one of the protease peptides. All 35 peptides were recognized. The response was not associated with particular HLA-DR or -DQ alleles. Our results thus indicate that protease is a frequent target of CD4+ along with CD8+ proliferative T cell responses by the majority of HIV-1-infected patients under PI therapy. The frequent finding of matching CD4+ and CD8+ T cell responses to the same peptides may indicate that CD4+ T cells provide cognate T cell help for the maintenance of long-living protease-specific functional CD8+ T cells.