Solving weighted CSPs with meta-constraints by reformulation into satisfiability modulo theories

We introduce WSimply, a new framework for modelling and solving Weighted Constraint Satisfaction Problems (WCSP) using Satisfiability Modulo Theories (SMT) technology. In contrast to other well-known approaches designed for extensional representation of goods or no-goods, and with few declarative facilities, our approach aims to follow an intensional and declarative syntax style. In addition, our language has built-in support for some meta-constraints, such as priority and homogeneity, which allows the user to easily specify rich requirements on the desired solutions, such as preferences and fairness. We propose two alternative strategies for solving these WCSP instances using SMT. The first is the reformulation into Weighted SMT (WSMT) and the application of satisfiability test based algorithms from recent contributions in the Weighted Maximum Satisfiability field. The second one is the reformulation into an operation research-like style which involves an optimisation variable or objective function and the application of optimisation SMT solvers. We present experimental results of two well-known problems: the Nurse Rostering Problem (NRP) and a variant of the Balanced Academic Curriculum Problem (BACP), and provide some insights into the impact of the addition of meta-constraints on the quality of the solutions and the solving time.     

An ant colony optimization algorithm for DNA sequencing by hybridization

The reconstruction of DNA sequences from DNA fragments is one of the most challenging problems in computational biology. In recent years the specific problem of DNA sequencing by hybridization has attracted quite a lot of interest in the optimization community. Several metaheuristics such as tabu search and evolutionary algorithms have been applied to this problem. However, the performance of existing metaheuristics is often inferior to the performance of recently proposed constructive heuristics. On the basis of these new heuristics we develop an ant colony optimization algorithm for DNA sequencing by hybridization. An important feature of this algorithm is the implementation in a so-called multi-level framework. The computational results show that our algorithm is currently a state-of-the-art method for the tackled problem.     

Real-time Light Animation

Light source animation is a particularly hard field of real‐time global illumination algorithms since moving light sources result in drastic illumination changes and make coherence techniques less effective. However, the animation of small (point‐like) light sources represents a special but practically very important case, for which the reuse of the results of other frames is possible. This paper presents a fast light source animation algorithm based on the virtual light sources illumination method. The speed up is close to the length of the animation, and is due to reusing paths in all frames and not only in the frame where they were obtained. The possible applications of this algorithm are the lighting design and systems to convey shape and features with relighting.     

STATISTICAL LINGUISTIC LAWS IN ECOLOGICAL MODELS

This paper gives the theoretical setup so that an ecological model, as a particular mathematical model, can be considered a text written in a formal language (mathematics), and therefore, statistical linguistic laws can be applied to obtain information parameters in different semantic levels of the same model. The statistical laws will be useful to: a) compare semantic levels, submodels, and different models mutually; b) prove that information temperature parameter is an indirect measure of meaning: the significance or semantic component of information, opposed to significant, or comprehension, on the part of the observer (modeller) of the model text. We will apply these ideas in two practical examples.     

Trading genes along the silk road: mtDNA sequences and the origin of central Asian populations

Central Asia is a vast region at the crossroads of different habitats, cultures, and trade routes. Little is known about the genetics and the history of the population of this region. We present the analysis of mtDNA control-region sequences in samples of the Kazakh, the Uighurs, the lowland Kirghiz, and the highland Kirghiz, which we have used to address both the population history of the region and the possible selective pressures that high altitude has on mtDNA genes. Central Asian mtDNA sequences present features intermediate between European and eastern Asian sequences, in several parameters-such as the frequencies of certain nucleotides, the levels of nucleotide diversity, mean pairwise differences, and genetic distances. Several hypotheses could explain the intermediate position of central Asia between Europe and eastern Asia, but the most plausible would involve extensive levels of admixture between Europeans and eastern Asians in central Asia, possibly enhanced during the Silk Road trade and clearly after the eastern and western Eurasian human groups had diverged. Lowland and highland Kirghiz mtDNA sequences are very similar, and the analysis of molecular variance has revealed that the fraction of mitochondrial genetic variance due to altitude is not significantly different from zero. Thus, it seems unlikely that altitude has exerted a major selective pressure on mitochondrial genes in central Asian populations.     

Improved mimicry of a foot-and-mouth disease virus antigenic site by a viral peptide displayed on beta-galactosidase surface

A major antigenic site (site A) of foot-and-mouth disease virus includes multiple overlapping epitopes located within the flexible G-H loop of capsid protein VP1. We have studied the antigenicity of several recombinant E. coli beta-galactosidases displaying the site A from a serotype C virus in different surface regions of the bacterial enzyme. In each one of the explored insertion sites, the recombinant peptide shows different specificity with a set of anti-virus monoclonal antibodies directed to site A. In some of them, the inserted stretch mimics better than free or haemocyanin-coupled peptide the antigenicity of site A in the intact virus. In particular, an insertion within an exposed loop involved in the activating interface of beta-galactosidase (amino acids 272 to 287) led to a significant improvement of the overall reactivity. Since insertions at this site renders proteins enzymatically active, the activating interface could be an adequate place for the presentation of foreign antigens in correctly assembled beta-galactosidase tetramers. These results also suggest that anti-virus antibodies directed against the major antigenic site of FMDV recognize different conformations of the G-H loop, which are better reproduced in some of the recombinant proteins because of the dissimilar restrictions imposed by each particular insertion site.     

On the hardness of solving edge matching puzzles as SAT or CSP problems

Edge matching puzzles have been amongst us for a long time now and traditionally they have been considered, both, a children’s game and an interesting mathematical divertimento. Their main characteristics have already been studied, and their worst-case complexity has been properly classified as a NP-complete problem. It is in recent times, specially after being used as the problem behind a money-prized contest, with a prize of 2US$ million for the first solver, that edge matching puzzles have attracted mainstream attention from wider audiences, including, of course, computer science people working on solving hard problems. We consider these competitions as an interesting opportunity to showcase SAT/CSP solving techniques when confronted to a real world problem to a broad audience, a part of the intrinsic, i.e. monetary, interest of such a contest. This article studies the NP-complete problem known as edge matching puzzle using SAT and CSP approaches for solving it. We will focus on providing, first and foremost, a theoretical framework, including a generalized definition of the problem. We will design and show algorithms for easy and fast problem instances generation, generators with easily tunable hardness. Afterwards we will provide with SAT and CSP models for the problems and we will study problem complexity, both typical case and worst-case complexity. We will also provide some specially crafted heuristics that result in a boost in solving time and study which is the effect of such heuristics.     

Analysis and simulation of the effects of distributed nonlinearities in microwave superconducting devices

This paper presents a comprehensive study of microwave nonlinearities in superconductors, with an emphasis on intermodulation distortion and third-harmonic generation. It contains the analysis of various resonant and nonresonant test devices and its validation using numerical simulations based on harmonic balance (HB). The HB simulations made on test devices show that the closed-form equations for intermodulation and third-harmonic generation are only valid at low power levels. The paper also contains examples of application of HB to illustrate that this technique is useful to simulate superconductive devices other than simple test devices, and that the validity of the simulations is not restricted to low drive power levels. Most of the analyses and simulations of this paper are based on electrical parameters that describe the nonlinearities in the superconducting material. These parameters are compatible with many existing models of microwave nonlinearities in superconductors. We discuss the particulars on how to relate these electrical parameters with one of the existing models that postulates that the nonlinear effects are due to a dependence of the penetration depth on the current density in the superconductor.     

Informatics support to medical diagnosis. General information obtained from a first structured contact with the patient

BACKGROUND: The methods and characteristics of clinical data gathered at the initial steps of development of a computerized system to aid medical diagnosis are reported. The objectives of the study were as follows: to describe the overall method and to set a framework for developing an intellectual model of the medical diagnosis procedure. MATERIAL AND METHODS: A structured medical interview and physical examination using an informatic program on PC compatible portable computers were completed in a sample 1,238 patients attending the outpatient clinics of our institution. Data obtained were compared with information in the patient's medical record taking as reference pattern the record of physicians in charge of the patients. Diagnosis were codified according to WHO International Classification of Diseases (ICD-9-CM). RESULTS: The distribution of symptoms and signs corresponding to the different organs and systems was analyzed. Each subdivision afforded a range of 1.3 to 3.9 abnormal findings per patient. A total of 3,571 diagnoses were codified for the whole group 1,238 patients with a mean (standard deviation) of 3 (2) diagnoses per patient (range 0-12). The distribution of diagnostic groups varied depending on the consideration of the main diagnosis or the concomitant diagnoses that defined the patient's clinical context. The most frequent main diagnoses included tumors, cardiovascular diseases, gastrointestinal disorders, and genitourinary tract diseases. CONCLUSIONS: As shown by results obtained in a sample of 1,238 patients, there is a very complex situation in clinical practice due to the simultaneous occurrence of several clinical patterns. This finding should be taken into account when developing clinical decision making support systems. The use of a structured medical interview or a structured and standard medical visit may be an adequate tool to clarify this matter and to contribute to standardization of clinical concepts and situations.