On the complexity of the Whitehead minimization problem

The Whitehead minimization problem consists in finding a minimum size element in the automorphic orbit of a word, a cyclic word or a finitely generated subgroup in a finite rank free group. We give the first fully polynomial algorithm to solve this problem, that is, an algorithm that is polynomial both in the length of the input word and in the rank of the free group. Earlier algorithms had an exponential dependency in the rank of the free group. It follows that the primitivity problem – to decide whether a word is an element of some basis of the free group – and the free factor problem can also be solved in polynomial time.

6

The use of the Internet now has a specific purpose: to find information. Unfortunately, the amount of data available on the Internet is growing exponentially, creating what can be considered a nearly infinite and ever-evolving network with no discernable structure. This rapid growth has raised the question of how to find the most relevant information. Many different techniques have been introduced to address the information overload, including search engines, Semantic Web, and recommender systems, among others. Recommender systems are computer-based techniques that are used to reduce information overload and recommend products likely to interest a user when given some information about the user's profile. This technique is mainly used in e-Commerce to suggest items that fit a customer's purchasing tendencies. The use of recommender systems for e-Government is a research topic that is intended to improve the interaction among public administrations, citizens, and the private sector through reducing information overload on e-Government services. More specifically, e-Democracy aims to increase citizens' participation in democratic processes through the use of information and communication technologies. In this chapter, an architecture of a recommender system that uses fuzzy clustering methods for e-Elections is introduced. In addition, a comparison with the smartvote system, a Web-based Voting Assistance Application (VAA) used to aid voters in finding the party or candidate that is most in line with their preferences, is presented.

Structured RNAs in the ENCODE selected regions of the human genome.

Functional RNA structures play an important role both in the context of noncoding RNA transcripts as well as regulatory elements in mRNAs. Here we present a computational study to detect functional RNA structures within the ENCODE regions of the human genome. Since structural RNAs in general lack characteristic signals in primary sequence, comparative approaches evaluating evolutionary conservation of structures are most promising. We have used three recently introduced programs based on either phylogenetic-stochastic context-free grammar (EvoFold) or energy directed folding (RNAz and AlifoldZ), yielding several thousand candidate structures (corresponding to approximately 2.7% of the ENCODE regions). EvoFold has its highest sensitivity in highly conserved and relatively AU-rich regions, while RNAz favors slightly GC-rich regions, resulting in a relatively small overlap between methods. Comparison with the GENCODE annotation points to functional RNAs in all genomic contexts, with a slightly increased density in 3'-UTRs. While we estimate a significant false discovery rate of approximately 50%-70% many of the predictions can be further substantiated by additional criteria: 248 loci are predicted by both RNAz and EvoFold, and an additional 239 RNAz or EvoFold predictions are supported by the (more stringent) AlifoldZ algorithm. Five hundred seventy RNAz structure predictions fall into regions that show signs of selection pressure also on the sequence level (i.e., conserved elements). More than 700 predictions overlap with noncoding transcripts detected by oligonucleotide tiling arrays. One hundred seventy-five selected candidates were tested by RT-PCR in six tissues, and expression could be verified in 43 cases (24.6%).

Estudi GPGPU dedicat al processament de neuroimatges

La tecnologia GPGPU permet paral∙lelitzar càlculs executant operacions aritmètiques en els múltiples processadors de que disposen els xips gràfics. S'ha fet servir l'entorn de desenvolupament CUDA de la companyia NVIDIA, que actualment és la solució GPGPU més avançada del mercat. L'algorisme de neuroimatge implementat pertany a un estudi VBM desenvolupat amb l'eina SPM. Es tracta concretament del procés de segmentació d'imatges de ressonància magnètica cerebrals, en els diferents teixits dels quals es composa el cervell: matèria blanca, matèria grisa i líquid cefaloraquidi. S'han implementat models en els llenguatges Matlab, C i CUDA, i s'ha fet un estudi comparatiu per plataformes hardware diferents.

The analysis of approximate quickselect and related problems

Approximate Quickselect, a simple modification of the well known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Approximate Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm. The key element appearing in the analysis of Approximate Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us. In particular, we have been able to carry out a precise analysis of the expected number of moves of the ith element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results. Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.

Eye colour as a genetic marker for fertility and fecundity of Triatoma infestans (Klug, 1834) Hemiptera, Reduviidae, Triatominae

Eye colour of Triatoma infestans is controlled at a single autosomal locus, with black-eye as the dominant gene and red-eye as the recessive. Inheritance of these characters follows a classical Mendelian system, enabling eye colour to be used as a marker for studies of mating frequency. We found no significant differences in oviposition rates and egg hatching rates irrespective of parental phenotypes. Different mating schedules between red-eye and black-eye parents showed that eye colour did not affect mating competence. Females mated with a single male or with different males together or in succession produced similar numbers of fertile eggs, with the eye colour of the offspring reflecting exposure to the different males. We conclude that although a single mating can provide sufficient sperm for the whole reproductive life of the female, multiple matings can result in balanced assortative sperm usage from the spermatheca.

Detecting the number of clusters of individuals using the software STRUCTURE: a simulation study.

The identification of genetically homogeneous groups of individuals is a long standing issue in population genetics. A recent Bayesian algorithm implemented in the software STRUCTURE allows the identification of such groups. However, the ability of this algorithm to detect the true number of clusters (K) in a sample of individuals when patterns of dispersal among populations are not homogeneous has not been tested. The goal of this study is to carry out such tests, using various dispersal scenarios from data generated with an individual-based model. We found that in most cases the estimated 'log probability of data' does not provide a correct estimation of the number of clusters, K. However, using an ad hoc statistic DeltaK based on the rate of change in the log probability of data between successive K values, we found that STRUCTURE accurately detects the uppermost hierarchical level of structure for the scenarios we tested. As might be expected, the results are sensitive to the type of genetic marker used (AFLP vs. microsatellite), the number of loci scored, the number of populations sampled, and the number of individuals typed in each sample.

Melanism, body condition and elevational distribution in the asp viper

Alternative morphotypes can confer important selective advantages in different habitats, whereas they can be penalized in other circumstances. In ectotherms, such as reptiles, the body colour can have direct effects on numerous aspects of their existence, such as thermoregulation or prey-predator interactions. Darker melanic individuals show lower skin reflectance and consequently heat up more rapidly and maintain optimal body temperatures more easily than lighter coloured individuals. As a consequence, melanistic individuals of diurnal species in cool areas may exhibit higher body condition, growth rate, survival and fecundity than lighter coloured individuals. Such advantages of dark coloration may be counterbalanced by a lower crypsis to predators and a decreased foraging efficiency. We investigated, in two montane populations of asp vipers Vipera aspis, the relationship between (1) colour polymorphism and body condition and length and (2) the coloration of individuals and their elevational distribution. We showed significant relationships between (1) the coloration, body condition and sex of individuals; (2) sexes and reproductive state and morph frequency; and (3) colour morphs that were distributed following an elevational gradient. Hence, colour polymorphism plays an important role in the ecology and evolution of the asp viper and is maintained through differential selective pressures.

Dietary lipids reduce the expression of carotenoid-based coloration in Lacerta vivipara

1. The importance of dietary lipids for carotenoid-based ornaments has rarely been investigated, although theory predicts that dietary lipids may control the development of these widespread animal signals. Dietary lipids have been suggested to enhance the expression of male carotenoid-based ornaments because they provide carotenoids with a hydrophobic domain that facilitates their absorption and transport. Dietary lipids may also enhance the uptake of tocopherols (vitamin E), which share common absorption and transport routes with carotenoids. Here, we test whether dietary lipids enhance carotenoid availability and male carotenoid-based colorations. We also explore the effects of dietary lipids on plasma tocopherol concentration, which allow disentangling between different pathways that may explain how dietary lipids affect ornamental expression. 2. Following a two-factorial design, we manipulated dietary access of naturally occurring fatty acids (oleic acid) and carotenoids (lutein and zeaxanthin) and measured its effects on the circulating concentrations of carotenoids (lutein and zeaxanthin) and vitamin E (α- and γ-(β-) tocopherols) and on the ventral, carotenoid-based coloration of male common lizards (Lacerta vivipara). 3. Lutein but not zeaxanthin plasma concentrations increased with carotenoid supplementation, which, however, did not affect coloration. Lipid intake negatively affected circulating concentrations of lutein and γ-(β-) tocopherol and led to significantly less orange colorations. The path analysis suggests that a relationship between the observed colour change and the change in plasma concentrations of γ-(β-) tocopherol may exist. 4. Our study shows for the first time that dietary lipids do not enhance but reduce the intensity of male carotenoid-based ornaments. Although dietary lipids affected plasma carotenoid concentration, its negative effect on coloration appeared to be linked to lower vitamin E plasma concentrations. These findings suggest that a conflict between dietary lipids and carotenoid and tocopherol uptake may arise if these nutrients are independently obtained from natural diets and that such conflict may reinforce signal honesty in carotenoid-based ornaments. They also suggest that, at least in the common lizard, sexual selection with respect to carotenoid-based coloration may select for males with low antioxidant capacity and thus for males of superior health.

Enhanced Model Selection for motion segmentation

In this paper a novel rank estimation technique for trajectories motion segmentation within the Local Subspace Affinity (LSA) framework is presented. This technique, called Enhanced Model Selection (EMS), is based on the relationship between the estimated rank of the trajectory matrix and the affinity matrix built by LSA. The results on synthetic and real data show that without any a priori knowledge, EMS automatically provides an accurate and robust rank estimation, improving the accuracy of the final motion segmentation

A multidimensional segmentation evaluation for medical image data.

Evaluation of segmentation methods is a crucial aspect in image processing, especially in the medical imaging field, where small differences between segmented regions in the anatomy can be of paramount importance. Usually, segmentation evaluation is based on a measure that depends on the number of segmented voxels inside and outside of some reference regions that are called gold standards. Although some other measures have been also used, in this work we propose a set of new similarity measures, based on different features, such as the location and intensity values of the misclassified voxels, and the connectivity and the boundaries of the segmented data. Using the multidimensional information provided by these measures, we propose a new evaluation method whose results are visualized applying a Principal Component Analysis of the data, obtaining a simplified graphical method to compare different segmentation results. We have carried out an intensive study using several classic segmentation methods applied to a set of MRI simulated data of the brain with several noise and RF inhomogeneity levels, and also to real data, showing that the new measures proposed here and the results that we have obtained from the multidimensional evaluation, improve the robustness of the evaluation and provides better understanding about the difference between segmentation methods.

Weighted Shape-based Averaging with Neighborhood Prior Model for Multiple Atlas Fusion-based Medical Image Segmentation

In medical imaging, merging automated segmentations obtained from multiple atlases has become a standard practice for improving the accuracy. In this letter, we propose two new fusion methods: "Global Weighted Shape-Based Averaging" (GWSBA) and "Local Weighted Shape-Based Averaging" (LWSBA). These methods extend the well known Shape-Based Averaging (SBA) by additionally incorporating the similarity information between the reference (i.e., atlas) images and the target image to be segmented. We also propose a new spatially-varying similarity-weighted neighborhood prior model, and an edge-preserving smoothness term that can be used with many of the existing fusion methods. We first present our new Markov Random Field (MRF) based fusion framework that models the above mentioned information. The proposed methods are evaluated in the context of segmentation of lymph nodes in the head and neck 3D CT images, and they resulted in more accurate segmentations compared to the existing SBA.

Effective atomic orbitals for fuzzy atoms

The method of extracting effective atomic orbitals and effective minimal basis sets from molecular wave function characterizing the state of an atom in a molecule is developed in the framework of the "fuzzy" atoms. In all cases studied, there were as many effective orbitals that have considerable occupation numbers as orbitals in the classical minimal basis. That is considered to be of high conceptual importance

One- and two-center physical space partitioning of the energy in the density functional theory

A conceptually new approach is introduced for the decomposition of the molecular energy calculated at the density functional theory level of theory into sum of one- and two-atomic energy components, and is realized in the "fuzzy atoms" framework. (Fuzzy atoms mean that the three-dimensional physical space is divided into atomic regions having no sharp boundaries but exhibiting a continuous transition from one to another.) The new scheme uses the new concept of "bond order density" to calculate the diatomic exchange energy components and gives them unexpectedly close to the values calculated by the exact (Hartree-Fock) exchange for the same Kohn-Sham orbitals

Medical futility at the end of life: the perspectives of intensive care and palliative care clinicians.

Objectives Medical futility at the end of life is a growing challenge to medicine. The goals of the authors were to elucidate how clinicians define futility, when they perceive life-sustaining treatment (LST) to be futile, how they communicate this situation and why LST is sometimes continued despite being recognised as futile. Methods The authors reviewed ethics case consultation protocols and conducted semi-structured interviews with 18 physicians and 11 nurses from adult intensive and palliative care units at a tertiary hospital in Germany. The transcripts were subjected to qualitative content analysis. Results Futility was identified in the majority of case consultations. Interviewees associated futility with the failure to achieve goals of care that offer a benefit to the patient's quality of life and are proportionate to the risks, harms and costs. Prototypic examples mentioned are situations of irreversible dependence on LST, advanced metastatic malignancies and extensive brain injury. Participants agreed that futility should be assessed by physicians after consultation with the care team. Intensivists favoured an indirect and stepwise disclosure of the prognosis. Palliative care clinicians focused on a candid and empathetic information strategy. The reasons for continuing futile LST are primarily emotional, such as guilt, grief, fear of legal consequences and concerns about the family's reaction. Other obstacles are organisational routines, insufficient legal and palliative knowledge and treatment requests by patients or families. Conclusion Managing futility could be improved by communication training, knowledge transfer, organisational improvements and emotional and ethical support systems. The authors propose an algorithm for end-of-life decision making focusing on goals of treatment.