An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

TESTING STATISTICAL HYPOTHESIS ON RANDOM TREES AND APPLICATIONS TO THE PROTEIN CLASSIFICATION PROBLEM

Efficient automatic protein classification is of central importance in genomic annotation. As an independent way to check the reliability of the classification, we propose a statistical approach to test if two sets of protein domain sequences coming from two families of the Pfam database are significantly different. We model protein sequences as realizations of Variable Length Markov Chains (VLMC) and we use the context trees as a signature of each protein family. Our approach is based on a Kolmogorov-Smirnov-type goodness-of-fit test proposed by Balding et at. [Limit theorems for sequences of random trees (2008), DOI: 10.1007/s11749-008-0092-z]. The test statistic is a supremum over the space of trees of a function of the two samples; its computation grows, in principle, exponentially fast with the maximal number of nodes of the potential trees. We show how to transform this problem into a max-flow over a related graph which can be solved using a Ford-Fulkerson algorithm in polynomial time on that number. We apply the test to 10 randomly chosen protein domain families from the seed of Pfam-A database (high quality, manually curated families). The test shows that the distributions of context trees coming from different families are significantly different. We emphasize that this is a novel mathematical approach to validate the automatic clustering of sequences in any context. We also study the performance of the test via simulations on Galton-Watson related processes.

On S-asymptotically omega-periodic functions on Banach spaces and applications

This paper is devoted to the study of the class of continuous and bounded functions f : [0, infinity] -> X for which exists omega > 0 such that lim(t ->infinity) (f (t + omega) - f (t)) = 0 (in the sequel called S-asymptotically omega-periodic functions). We discuss qualitative properties and establish some relationships between this type of functions and the class of asymptotically omega-periodic functions. We also study the existence of S-asymptotically omega-periodic mild solutions of the first-order abstract Cauchy problem in Banach spaces. (C) 2008 Elsevier Inc. All rights reserved.

Almost automorphic mild solutions to some partial neutral functional-differential equations and applications

The paper considers the existence and uniqueness of almost automorphic mild solutions to some classes of first-order partial neutral functional-differential equations. Sufficient conditions for the existence and uniqueness of almost automorphic mild solutions to the above-mentioned equations are obtained. As an application, a first-order boundary value problem arising in control systems is considered. (C) 2007 Elsevier Ltd. All fights reserved.

Knowledge, attitudes and motivations among blood donors in Sao Paulo, Brazil

Recruiting safe, volunteer blood donors requires understanding motivations for donating and knowledge and attitudes about HIV. We surveyed 1,600 persons presenting for blood donation at a large blood bank in Sao Paulo, Brazil using a self-administered, structured questionnaire, and classified motivations into three domains as well as categorizing persons by HIV test-seeking behavior. Motivations, in descending order, and their significant associations were: ""altruism``: female gender, volunteer donor and repeat donor status; ""direct appeal``: female gender, repeat donor status and age 21-50 years; ""selfinterest``: male gender, age under 20 years, first-time donor status and lower education. HIV test-seekers were more likely to give incorrect answers regarding HIV risk behavior and blood donation and the ability of antibody testing to detect recent HIV infections. Altruism is the main motivator for blood donation in Brazil; other motivators were associated with specific demographic subgroups. HIV test-seeking might be reduced by educational interventions.

Articular Cartilage in the Knee: Current MR Imaging Techniques and Applications in Clinical Practice and Research

Magnetic resonance (MR) imaging is the most important imaging modality for the evaluation of traumatic or degenerative cartilaginous lesions in the knee. It is a powerful noninvasive tool for detecting such lesions and monitoring the effects of pharmacologic and surgical therapy. The specific MR imaging techniques used for these purposes can be divided into two broad categories according to their usefulness for morphologic or compositional evaluation. To assess the structure of knee cartilage, standard spin-echo (SE) and gradient-recalled echo (GRE) sequences, fast SE sequences, and three-dimensional SE and GRE sequences are available. These techniques allow the detection of morphologic defects in the articular cartilage of the knee and are commonly used in research for semiquantitative and quantitative assessments of cartilage. To evaluate the collagen network and proteoglycan content in the knee cartilage matrix, compositional assessment techniques such as T2 mapping, delayed gadolinium-enhanced MR imaging of cartilage (or dGEMRIC), T1 rho imaging, sodium imaging, and diffusion-weighted imaging are available. These techniques may be used in various combinations and at various magnetic field strengths in clinical and research settings to improve the characterization of changes in cartilage. (C)RSNA, 2011 , radiographics.rsna.org

Structure and Applications of a Rhamnolipid Surfactant Produced in Soybean Oil Waste

Soybean oil soapstock was utilized as an alternative carbon source for the production of rhamnolipids by Pseudomonas aeruginosa LBI strain. The chemical composition and properties of the rhamnolipid mixture obtained were determined to define its potential applications. The chemical characterization of the rhamnolipid has revealed the presence of ten different homologues. The monorhamnolipid RhaC(10)C(10) and the dirhamnolipid Rha(2)C(10)C(10) were the main components of the mixture that showed predominance of 44% and 29%, respectively, after 144-h of cultivation. The biosurfactant was able to form stable emulsions with several hydrocarbons and showed excellent emulsification for soybean oil and chicken fat (100%). The rhamnolipid removed 67% of crude oil present in sand samples and presented antimicrobial activity against Bacillus cereus and Mucor miehei at 64 mu g/mL and inhibition of Neurospora crassa, Staphylococcus aureus, and Micrococcus luteus at 256 mu g/mL. The results demonstrated that the rhamnolipid produced in soybean oil soapstock can be useful in environmental and food industry applications.

Distance Education in Another Register: Uses and Appropriation of Technologies in Teacher Education

The article explores the relationships between distance education, information and communication technologies and teacher education. Its focus is on the interactive media and its uses in an in-service teacher education program, in Brazil, and on the ways the teachers used the technologies doing their own appropriateness. It departs from the presuppositions of the society of knowledge, that is, the close relationships between new technologies, continuing professional development and social inclusion, arguing that this paradigm is an ideological discourse. The article shows how the teachers have used the technologies in creative ways, calling the attention to the importance of this teachers` abilities as a basic skill to facing the challenges of the society of knowledge itself.