The surface-based approach for DNA computation is unreliable for SAT

Previous research presented DNA computing on surfaces, which applied to each clause three operations:"mark","destroy", and "unmark", and demonstrated how to solve a four-variable four-clause instance of the 3-SAT. It was claimed that only the strands satisfying the problem remained on the surface at the end of the computation and the surface-based approach was capable of scaling up to larger 3-SAT problems. Accordingly, the identities of the strands were only determined in the"readout" step for the correct solutions to the problem without checking if the strands really satisfied the problem. Thus, based on the claim above, the surface-based approach became a polynomial-time algorithm. In this paper, we show that for some instance of SAT, at the end of the computation all the remaining strands falsify the instance. However, by the previous claim all the strands falsifying the problems would be regarded as the correct solutions to the problems. Therefore, the DNA computing on surfaces is unreliable. For this reason, it is necessary to add a "verify" step after the "readout" step to check if the strands remaining on the surface at the end of the computation really satisfy the problem.     

Fitting protein chains to cubic lattice is NP-complete

It is known that folding a protein chain into a cubic lattice is an NP-complete problem. We consider a seemingly easier problem: given a three-dimensional (3D) fold of a protein chain (coordinates of its C(alpha) atoms), we want to find the closest lattice approximation of this fold. This problem has been studied under names such as "lattice approximation of a protein chain", "the protein chain fitting problem", and "building of protein lattice models". We show that this problem is NP-complete for the cubic lattice with side close to 3.8 A and coordinate root mean square deviation.     

An algorithm to enumerate sorting reversals for signed permutations.

The rearrangement distance between single-chromosome genomes can be estimated as the minimum number of inversions required to transform the gene ordering observed in one into that observed in the other. This measure, known as "inversion distance," can be computed as the reversal distance between signed permutations. During the past decade, much progress has been made both on the problem of computing reversal distance and on the related problem of finding a minimum-length sequence of reversals, which is known as "sorting by reversals." For most problem instances, however, many minimum-length sequences of reversals exist, and in the absence of auxiliary information, no one is of greater value than the others. The problem of finding all minimum-length sequences of reversals is thus a natural generalization of sorting by reversals, yet it has received little attention. This problem reduces easily to the problem of finding all "sorting reversals" of one permutation with respect to another - that is, all reversals rho such that, if rho is applied to one permutation, then the reversal distance of that permutation from the other is decreased. In this paper, an efficient algorithm is derived to solve the problem of finding all sorting reversals, and experimental results are presented indicating that, while the new algorithm does not represent a significant improvement in asymptotic terms (it takes O(n(3)) time, for permutations of size n; the problem can now be solved by brute force in Theta(n(3)) time), it performs dramatically better in practice than the best known alternative. An implementation of the algorithm is available at www.cse.ucsc.edu/~acs.     

USE OF PURCHASE PREFERENCE OPTIONS TO INCREASE "NO PREFERENCE" FREQUENCIES IN PLACEBO PREFERENCE TESTS

Besides responses to the different stimuli being tested in a paired preference test, responses to identical "placebo" stimuli can be used as a screening tool to identify biased consumers. Those consumers who give preference responses to identical stimuli can be assumed to be biased. Accordingly, only the data from unbiased consumers need to be considered for the different stimuli. The problem with this procedure is that the sample size is reduced. The goal of the present research was to see whether using options associated with purchase intent, elicited a greater number of "No Preference" responses to identical "placebo" stimuli. It was found that they did. The increase was large when the preference options implied exclusivity. In conditions where the preference strength options were not so strong, the frequency of "No Preference" responses dropped accordingly.

PRACTICAL APPLICATIONS

A problem with paired preference testing is the tendency of consumers to give false preferences, which produces the seriously misleading overestimation of the proportion of consumers who have preferences for one or other of the products being assessed. The "placebo" condition is an important control for alleviating this problem. The statistical analysis can be improved by finding a protocol that maximizes the proportion of "No Preference" responses in the placebo condition. The key finding here is that using purchase intent questions rather than preference questions may possibly provide a way of achieving this aim.     

A study of the application of Kohonen-type neural networks to the Travelling Salesman Problem

It is observed that animals often have to resolve difficult tasks of optimization and that this process can be studied by applying the formal framework of neural networks to a simple problem such as the Travelling Salesman Problem. Existing work is reviewed with particular emphasis on recent studies using self-organizing networks. An algorithm is described in which general principles developed by Kohonen are applied to the Travelling Salesman Problem. Simulation results are given for problem sets of up to 10,000 cities. The routes generated are reported as being slightly longer than those produced by simulating annealing; compute time is lower and scales less than quadratically with problem size. It is suggested that the ability to perform optimization is an emergent computational property not just of the Kohonen model but of any mechanism capable of producing topology-preserving mappings, including mechanisms within the brain.     

On Measures of Gametic Disequilibrium

Various measures have been proposed for characterizing the statistical association that arises between alleles at different loci. Hedrick has compared these measures with the standardized measure D' proposed by Lewontin on the grounds that this latter measure is independent of allele frequency. Although D' has the same range for all allelic frequencies, in fact, D' is not "independent" of allele frequency, and no measure with that general property is possible for the multilocus association problem. The insolubility of this problem arises from the ill-defined nature of general "association."     

Toward the Problem of Stages in the Mental Development of Children

The problem of stages' in the mental development of the child is the fundamental problem of child psychology. Elaboration of this problem has important theoretical significance since it is by determining the stages of mental development and by discovering the patterns of transition from one stage to the next that psychology will eventually solve the problem of the motive forces of mental development. We contend that every conception of the motive forces of mental development must first be tested on the "proving grounds" of the theory of developmental stages.     

An ILP solution for the gene duplication problem

Background

The gene duplication (GD) problem seeks a species tree that implies the fewest gene duplication events across a given collection of gene trees. Solving this problem makes it possible to use large gene families with complex histories of duplication and loss to infer phylogenetic trees. However, the GD problem is NP-hard, and therefore, most analyses use heuristics that lack any performance guarantee.

Results

We describe the first integer linear programming (ILP) formulation to solve instances of the gene duplication problem exactly. With simulations, we demonstrate that the ILP solution can solve problem instances with up to 14 taxa. Furthermore, we apply the new ILP solution to solve the gene duplication problem for the seed plant phylogeny using a 12-taxon, 6, 084-gene data set. The unique, optimal solution, which places Gnetales sister to the conifers, represents a new, large-scale genomic perspective on one of the most puzzling questions in plant systematics.

Conclusions

Although the GD problem is NP-hard, our novel ILP solution for it can solve instances with data sets consisting of as many as 14 taxa and 1, 000 genes in a few hours. These are the largest instances that have been solved to optimally to date. Thus, this work can provide large-scale genomic perspectives on phylogenetic questions that previously could only be addressed by heuristic estimates.

     

Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable

Reticulation processes in evolution mean that the ancestral history of certain groups of present-day species is non-tree-like. These processes include hybridization, lateral gene transfer, and recombination. Despite the existence of reticulation, such events are relatively rare and so a fundamental problem for biologists is the following: Given a collection of rooted binary phylogenetic trees on sets of species that correctly represent the tree-like evolution of different parts of their genomes, what is the smallest number of "reticulation" vertices in any network that explains the evolution of the species under consideration? It has been previously shown that this problem is NP-hard even when the collection consists of only two rooted binary phylogenetic trees. However, in this paper, we show that the problem is fixed-parameter tractable in the two-tree instance, when parameterized by this smallest number of reticulation vertices.     

Slow Response of Societies to New Problems: Causes and Costs

Human societies are confronted with a continuous stream of new problems. Many of these problems are caused by a limited sector of society but cause spillover costs to society as a whole. Here we show how a combination of mechanisms tends to delay effective regualtion of such situations. Obviously, problems may remain undetected for some time, especially if they are unlike those experienced in the past. However, it is at least as important to address the dynamics preceding the solution because societies that are systematically slow in suppressing problems in the early phases will pay a high overall cost. Here we show how a combination of mechanisms tends to delay effective regulation. Obviously, problems may remain undetected for some time, especially if it is unlike those experienced in the past. However, even if a problem is recognized by experts, the time lag before society in general recognizes that something should be done can be long because of the hysteresis in change of opinion. This causes abrupt but late shifts in opinion, much as described for Kuhns paradigm shifts. We use a mathematical model and review empirical evidence to show that this phenomenon will be particularly pronounced for complex problems and in societies that have strong social control, whereas key individuals such as charismatic leaders may catalyze earlier opinion shifts, reducing the time lag between problem and solution. An opinion shift may also be inhibited by downplay of a problem by a credible authority and by competition for attention by simultaneously occurring problems. Even if a problem is generally recognized, actual regulation may come late. We argue that this last phase of delay tends to be longer if a central decision-making authority is lacking and if disproportionately powerful stakeholders that benefit from the unregulated status quo are involved.     

Solution of the direct and inverse kinematic problems by a common algorithm based on the mean of multiple computations

For the control of the movement of a multijoint manipulator a mental model which represents the geometrical properties of the arm may prove helpful. Using this model the direct and the inverse kinematic problem could be solved. Here we propose such a model which is based on a recurrent network. It is realized for the example of a three-joint manipulator working in a two-dimensional plane, i.e., for a manipulator with one extra degree of freedom. The system computes the complete set of variables, in our example the three joint angles and the two work-space coordinates of the endpoint of the manipulator. The system finds a stable state and a geometrically correct solution even if only a part of these state variables is given. Thus, the direct and the inverse kinematic problem as well as any mixed problem, including the underconstrained case, can be solved by the network.     

Isometric gene tree reconciliation revisited

Background

Isometric gene tree reconciliation is a gene tree/species tree reconciliation problem where both the gene tree and the species tree include branch lengths, and these branch lengths must be respected by the reconciliation. The problem was introduced by Ma et al. in 2008 in the context of reconstructing evolutionary histories of genomes in the infinite sites model.

Results

In this paper, we show that the original algorithm by Ma et al. is incorrect, and we propose a modified algorithm that addresses the problems that we discovered. We have also improved the running time from \(O(N^2)\) to \(O(N\log N)\), where N is the total number of nodes in the two input trees. Finally, we examine two new variants of the problem: reconciliation of two unrooted trees and scaling of branch lengths of the gene tree during reconciliation of two rooted trees.

Conclusions

We provide several new algorithms for isometric reconciliation of trees. Some questions in this area remain open; most importantly extensions of the problem allowing for imprecise estimates of branch lengths.

     

New Data on the Problem of Social Perception (A Person's Perception and Conception of Another Person)

Throughout the world at the present time more and more scientists are working on the problem of social perception. Though they are interested in different aspects of this problem, all are helping to elucidate the more or less complex features that characterize the process of how a human being forms images of other people and how he develops conceptions of their personalities. It was no slip of the pen when we included as a part of "social perception" the evolution of one's conception of another human being as a personality, for today the term "social perception" has been extended by most psychologists working on this problem to include the whole range of phenomena involved in one person's knowledge of another on the level of feeling as well as on the rational plane.     

A resolution of the ascertainment sampling problem I. Theory

We consider the "ascertainment problem" arising when families are sampled by a nonrandom sampling process and, for the purpose of estimating genetic parameters, some assumption must be made about the process by which families enter the sample. A resolution of this problem, involving conditioning the likelihood of the sample on that part of the data relevant to ascertainment, is put forward. Numerical examples illustrating the properties of the procedure are provided.     

Models and algorithms for genome rearrangement with positional constraints

Background

Traditionally, the merit of a rearrangement scenario between two gene orders has been measured based on a parsimony criteria alone; two scenarios with the same number of rearrangements are considered equally good. In this paper, we acknowledge that each rearrangement has a certain likelihood of occurring based on biological constraints, e.g. physical proximity of the DNA segments implicated or repetitive sequences.

Results

We propose optimization problems with the objective of maximizing overall likelihood, by weighting the rearrangements. We study a binary weight function suitable to the representation of sets of genome positions that are most likely to have swapped adjacencies. We give a polynomial-time algorithm for the problem of finding a minimum weight double cut and join scenario among all minimum length scenarios. In the process we solve an optimization problem on colored noncrossing partitions, which is a generalization of the Maximum Independent Set problem on circle graphs.

Conclusions

We introduce a model for weighting genome rearrangements and show that under simple yet reasonable conditions, a fundamental distance can be computed in polynomial time. This is achieved by solving a generalization of the Maximum Independent Set problem on circle graphs. Several variants of the problem are also mentioned.

     

Protein side-chain packing problem: a maximum edge-weight clique algorithmic approach

"Protein Side-chain Packing" has an ever-increasing application in the field of bio-informatics, dating from the early methods of homology modeling to protein design and to the protein docking. However, this problem is computationally known to be NP-hard. In this regard, we have developed a novel approach to solve this problem using the notion of a maximum edge-weight clique. Our approach is based on efficient reduction of protein side-chain packing problem to a graph and then solving the reduced graph to find the maximum clique by applying an efficient clique finding algorithm developed by our co-authors. Since our approach is based on deterministic algorithms in contrast to the various existing algorithms based on heuristic approaches, our algorithm guarantees of finding an optimal solution. We have tested this approach to predict the side-chain conformations of a set of proteins and have compared the results with other existing methods. We have found that our results are favorably comparable or better than the results produced by the existing methods. As our test set contains a protein of 494 residues, we have obtained considerable improvement in terms of size of the proteins and in terms of the efficiency and the accuracy of prediction.     

The neural correlates of problem states: testing FMRI predictions of a computational model of multitasking

Background

It has been shown that people can only maintain one problem state, or intermediate mental representation, at a time. When more than one problem state is required, for example in multitasking, performance decreases considerably. This effect has been explained in terms of a problem state bottleneck.

Methodology

In the current study we use the complimentary methodologies of computational cognitive modeling and neuroimaging to investigate the neural correlates of this problem state bottleneck. In particular, an existing computational cognitive model was used to generate a priori fMRI predictions for a multitasking experiment in which the problem state bottleneck plays a major role. Hemodynamic responses were predicted for five brain regions, corresponding to five cognitive resources in the model. Most importantly, we predicted the intraparietal sulcus to show a strong effect of the problem state manipulations.

Conclusions

Some of the predictions were confirmed by a subsequent fMRI experiment, while others were not matched by the data. The experiment supported the hypothesis that the problem state bottleneck is a plausible cause of the interference in the experiment and that it could be located in the intraparietal sulcus.     

Uncertainty, ecology, sustainability and policy

Using an Australian focus to explore theoretical and policy issues of wider concern, this article examines linkages between public policy and the science of ecology. This is done within the broader framework of sustainability, emphasizing the problem of decision making in the face of uncertainty. Insights from the ecological, risk, sustainability and policy literatures are used. The sustainability-uncertainty problem is characterized, and the adequacy of existing policy support techniques and approaches noted, particularly the precautionary principle. The problem is further defined using the notion of ignorance. The treatment of ignorance and uncertainty in ecology is discussed. We suggest that the science of ecology has had a limited influence on policy formulation and discuss the basis of this using biodiversity conservation and ecosystem management as examples. We conclude by considering challenges for handling risk, uncertainty and ignorance in ecological science for policy formulation. We emphasize the need for improved communication between the science and policy communities, greater recognition of the limits of quantitative techniques in addressing uncertainty, and contingency planning.     

A posteriori time-varying filtering of averaged evoked potentials

The problem of estimating an unknown transient signal, given an ensemble of waveforms, in which this signal appears as a nonrandom component in the presence of additive noise is considered. This problem is solved by generalizing the method of a posteriori Wiener filtering. In the new method, the ensemble average is filtered by a time-varying system which is based on estimated time-varying power spectra of signal and noise. The nature of this system, and the computational procedures involved, are discussed in detail. A software package for time-varying filtering is briefly described. Application of the method is illustrated by a simulation example, which also provides a comparison to time-invariant a posteriori Wiener filtering.     

Towards sub-quadratic time and space complexity solutions for the dated tree reconciliation problem

Background

Recent coevolutionary analysis has considered tree topology as a means to reduce the asymptotic complexity associated with inferring the complex coevolutionary interrelationships that arise between phylogenetic trees. Targeted algorithmic design for specific tree topologies has to date been highly successful, with one recent formulation providing a logarithmic space complexity reduction for the dated tree reconciliation problem.

Methods

In this work we build on this prior analysis providing a further asymptotic space reduction, by providing a new formulation for the dynamic programming table used by a number of popular coevolutionary analysis techniques. This model gives rise to a sub quadratic running time solution for the dated tree reconciliation problem for selected tree topologies, and is shown to be, in practice, the fastest method for solving the dated tree reconciliation problem for expected evolutionary trees. This result is achieved through the analysis of not only the topology of the trees considered for coevolutionary analysis, but also the underlying structure of the dynamic programming algorithms that are traditionally applied to such analysis.

Conclusion

The newly inferred theoretical complexity bounds introduced herein are then validated using a combination of synthetic and biological data sets, where the proposed model is shown to provide an \(O(\sqrt{n})\) space saving, while it is observed to run in half the time compared to the fastest known algorithm for solving the dated tree reconciliation problem. What is even more significant is that the algorithm derived herein is able to guarantee the optimality of its inferred solution, something that algorithms of comparable speed have to date been unable to achieve.