Automated sequence-specific protein NMR assignment using the memetic algorithm MATCH

MATCH (Memetic Algorithm and Combinatorial Optimization Heuristics) is a new memetic algorithm for automated sequence-specific polypeptide backbone NMR assignment of proteins. MATCH employs local optimization for tracing partial sequence-specific assignments within a global, population-based search environment, where the simultaneous application of local and global optimization heuristics guarantees high efficiency and robustness. MATCH thus makes combined use of the two predominant concepts in use for automated NMR assignment of proteins. Dynamic transition and inherent mutation are new techniques that enable automatic adaptation to variable quality of the experimental input data. The concept of dynamic transition is incorporated in all major building blocks of the algorithm, where it enables switching between local and global optimization heuristics at any time during the assignment process. Inherent mutation restricts the intrinsically required randomness of the evolutionary algorithm to those regions of the conformation space that are compatible with the experimental input data. Using intact and artificially deteriorated APSY-NMR input data of proteins, MATCH performed sequence-specific resonance assignment with high efficiency and robustness.     

启发式思考题对医学本科分子生物学实验教学的促进作用

目的:通过自行设计的启发式思考题,让问题式学习伴随医学生分子生物学实验教学全程,利用实验课的教学互动环节发挥学生学习的主观能动性。方法:借鉴启发式教学经验和问题式教学方法,在实验的平时考核中增加了启发式思考题,针对教学内容设置拓展性问题,以开卷回答的方式引导学生通过自学寻找操作实践及其理论基础中潜在的知识内涵和科学规律。结果:思考题的引入在强化学生自主学习,锻炼思考和解决问题能力的同时也显示出了良好的区分度。思考题成绩以及以此为基础的平时成绩与实验理论考核成绩之间显示出了显著的相关性。结论:贯穿于实验课教学活动中的启发式思考题在拓展思维、提升学生自主学习能力的同时促进了实验课的教学效果。     

Fast local search for unrooted Robinson-Foulds supertrees

A Robinson-Foulds (RF) supertree for a collection of input trees is a tree containing all the species in the input trees that is at minimum total RF distance to the input trees. Thus, an RF supertree is consistent with the maximum number of splits in the input trees. Constructing RF supertrees for rooted and unrooted data is NP-hard. Nevertheless, effective local search heuristics have been developed for the restricted case where the input trees and the supertree are rooted. We describe new heuristics, based on the Edge Contract and Refine (ECR) operation, that remove this restriction, thereby expanding the utility of RF supertrees. Our experimental results on simulated and empirical data sets show that our unrooted local search algorithms yield better supertrees than those obtained from MRP and rooted RF heuristics in terms of total RF distance to the input trees and, for simulated data, in terms of RF distance to the true tree.     

Stochastic Time Models of Syllable Structure

Drawing on phonology research within the generative linguistics tradition, stochastic methods, and notions from complex systems, we develop a modelling paradigm linking phonological structure, expressed in terms of syllables, to speech movement data acquired with 3D electromagnetic articulography and X-ray microbeam methods. The essential variable in the models is syllable structure. When mapped to discrete coordination topologies, syllabic organization imposes systematic patterns of variability on the temporal dynamics of speech articulation. We simulated these dynamics under different syllabic parses and evaluated simulations against experimental data from Arabic and English, two languages claimed to parse similar strings of segments into different syllabic structures. Model simulations replicated several key experimental results, including the fallibility of past phonetic heuristics for syllable structure, and exposed the range of conditions under which such heuristics remain valid. More importantly, the modelling approach consistently diagnosed syllable structure proving resilient to multiple sources of variability in experimental data including measurement variability, speaker variability, and contextual variability. Prospects for extensions of our modelling paradigm to acoustic data are also discussed.     

Deep learning for robust and flexible tracking in behavioral studies for C. elegans

Robust and accurate behavioral tracking is essential for ethological studies. Common methods for tracking and extracting behavior rely on user adjusted heuristics that can significantly vary across different individuals, environments, and experimental conditions. As a result, they are difficult to implement in large-scale behavioral studies with complex, heterogenous environmental conditions. Recently developed deep-learning methods for object recognition such as Faster R-CNN have advantages in their speed, accuracy, and robustness. Here, we show that Faster R-CNN can be employed for identification and detection of Caenorhabditis elegans in a variety of life stages in complex environments. We applied the algorithm to track animal speeds during development, fecundity rates and spatial distribution in reproductive adults, and behavioral decline in aging populations. By doing so, we demonstrate the flexibility, speed, and scalability of Faster R-CNN across a variety of experimental conditions, illustrating its generalized use for future large-scale behavioral studies.     

Uncertainty causes humans to use social heuristics and to cooperate more: An experiment among Belgian university students

When humans engage in social interactions, they are often uncertain about what the possible outcomes are. Because of this, highly sophisticated cooperation strategies may not be very effective. Indeed, some models instead predict the emergence of ‘social heuristics’: simple cooperation strategies that perform well across a range of different situations. Here, we put these predictions to the test in a large-scale interactive decision making experiment. We confronted participants (mostly Belgian university students) with a broad range of cooperative interactions, systematically varying the uncertainty participants had about the consequences of cooperating. As expected, we find that uncertainty about the payoff consequences of cooperation causes individuals to use social heuristics. Additionally, these heuristics directly cause a marked increase in cooperation compared to the treatment without uncertainty, even in situations where cooperation can never be beneficial. These findings provide a new explanation for why human social behavior often violates the standard predictions of economic and evolutionary theory.     

Simple heuristics and rules of thumb: where psychologists and behavioural biologists might meet

The Centre for Adaptive Behaviour and Cognition (ABC) has hypothesised that much human decision-making can be described by simple algorithmic process models (heuristics). This paper explains this approach and relates it to research in biology on rules of thumb, which we also review. As an example of a simple heuristic, consider the lexicographic strategy of Take The Best for choosing between two alternatives: cues are searched in turn until one discriminates, then search stops and all other cues are ignored. Heuristics consist of building blocks, and building blocks exploit evolved or learned abilities such as recognition memory; it is the complexity of these abilities that allows the heuristics to be simple. Simple heuristics have an advantage in making decisions fast and with little information, and in avoiding overfitting. Furthermore, humans are observed to use simple heuristics. Simulations show that the statistical structures of different environments affect which heuristics perform better, a relationship referred to as ecological rationality. We contrast ecological rationality with the stronger claim of adaptation. Rules of thumb from biology provide clearer examples of adaptation because animals can be studied in the environments in which they evolved. The range of examples is also much more diverse. To investigate them, biologists have sometimes used similar simulation techniques to ABC, but many examples depend on empirically driven approaches. ABC's theoretical framework can be useful in connecting some of these examples, particularly the scattered literature on how information from different cues is integrated. Optimality modelling is usually used to explain less detailed aspects of behaviour but might more often be redirected to investigate rules of thumb.     

Ten Heuristics for Interdisciplinary Modeling Projects

Complex environmental and ecological problems require collaborative, interdisciplinary efforts. A common approach to integrating disciplinary perspectives on these problems is to develop simulation models in which the linkages between system components are explicitly represented. There is, however, little guidance in the literature on how such models should be developed through collaborative teamwork. In this paper, we offer a set of heuristics (rules of thumb) that address a range of challenges associated with this enterprise, including the selection of team members, negotiating a consensus view of the research problem, prototyping and refining models, the role of sensitivity analysis, and the importance of team communication. These heuristics arose from a comparison of our experiences with several interdisciplinary modeling projects. We use one such experience—a project in which natural scientists, social scientists, and local residents came together to investigate the sustainability of small indigenous communities in the Arctic—to illustrate the heuristics. Received 27 April 2001; accepted 12 November 2001.     

A computational approach to animal breeding

We propose a computational model of mating strategies for controlled animal breeding programs. A mating strategy in a controlled breeding program is a heuristic with some optimization criteria as a goal. Thus, it is appropriate to use the computational tools available for analysis of optimization heuristics. In this paper, we propose the first discrete model of the controlled animal breeding problem and analyse heuristics for two possible objectives: (1) breeding for maximum diversity and (2) breeding a target individual. These two goals are representative of conservation biology and agricultural livestock management, respectively. We evaluate several mating strategies and provide upper and lower bounds for the expected number of matings. While the population parameters may vary and can change the actual number of matings for a particular strategy, the order of magnitude of the number of expected matings and the relative competitiveness of the mating heuristics remains the same. Thus, our simple discrete model of the animal breeding problem provides a novel viable and robust approach to designing and comparing breeding strategies in captive populations.     

A comparison of four pair-wise sequence alignment methods

Protein sequence alignment has become an essential task in modern molecular biology research. A number of alignment techniques have been documented in literature and their corresponding tools are made available as freeware and commercial software. The choice and use of these tools for sequence alignment through the complete interpretation of alignment results is often considered non-trivial by end-users with limited skill in Bioinformatics algorithm development. Here, we discuss the comparison of sequence alignment techniques based on dynamic programming (N-W, S-W) and heuristics (LFASTA, BL2SEQ) for four sets of sequence data towards an educational purpose. The analysis suggests that heuristics based methods are faster than dynamic programming methods in alignment speed.     

Heuristics and Biases in Evolutionary Biology

Approaching science by considering the epistemological virtues which scientists see as constitutive of good science, and the way these virtues trade-off against one another, makes it possible to capture action that may be lost by approaches which focus on either the theoretical or institutional level. Following Wimsatt (1984) I use the notion of heuristics and biases to help explore a case study from the history of biology. Early in the 20th century, mutation theorists and natural historians fought over the role that isolation plays in evolution. This debate was principally about whether replication was the central scientific virtue (and hence the ultimate goal of science to replace non-experimental evidence with experimental evidence) or whether consilience of inductions was the central virtue (and hence, as many kinds of evidence as possible should be pursued).     

An analysis of the meaning of the concepts of "commitment" and "determination" in the study of patterns of development

The use of the term "commitment" by different authors was compared and the term itself was compared with the term "determination". Different authors understand the term "commitment" in different ways. It is proposed to preserve the terms "competence", "determination" (labile and stable) and "differentiation" in studies of normal development at stages preceding the appearance of organ rudiments in order to facilitate the use of the knowledge acquired by experimental embryology and to decipher these concepts at the molecular level. The meaning of the term "commitment" should be made more precise when describing the experimental results and also when assessing the results obtained by various authors and published in numerous papers and reviews.     

Identifying protein complexes directly from high-throughput TAP data with Markov random fields

Background  

Predicting protein complexes from experimental data remains a challenge due to limited resolution and stochastic errors of high-throughput methods. Current algorithms to reconstruct the complexes typically rely on a two-step process. First, they construct an interaction graph from the data, predominantly using heuristics, and subsequently cluster its vertices to identify protein complexes.     

Sequence-based heuristics for faster annotation of non-coding RNA families

MOTIVATION: Non-coding RNAs (ncRNAs) are functional RNA molecules that do not code for proteins. Covariance Models (CMs) are a useful statistical tool to find new members of an ncRNA gene family in a large genome database, using both sequence and, importantly, RNA secondary structure information. Unfortunately, CM searches are extremely slow. Previously, we created rigorous filters, which provably sacrifice none of a CM's accuracy, while making searches significantly faster for virtually all ncRNA families. However, these rigorous filters make searches slower than heuristics could be. RESULTS: In this paper we introduce profile HMM-based heuristic filters. We show that their accuracy is usually superior to heuristics based on BLAST. Moreover, we compared our heuristics with those used in tRNAscan-SE, whose heuristics incorporate a significant amount of work specific to tRNAs, where our heuristics are generic to any ncRNA. Performance was roughly comparable, so we expect that our heuristics provide a high-quality solution that--unlike family-specific solutions--can scale to hundreds of ncRNA families. AVAILABILITY: The source code is available under GNU Public License at the supplementary web site.     

Use of the positive difference transform for RBC elimination in bone marrow smear images

The use of an algorithm with a broad range of utility in digital image processing (the positive difference transform) is illustrated. Its effectiveness as a procedure for selective elimination of hemoglobin-containing images is demonstrated. A set of heuristics, employing information concerning nuclear hemoglobin content, is shown to discriminate nucleated erythrocytic cells from those of the leukocyte series.     

Automatically Generated Algorithms for the Vertex Coloring Problem

The vertex coloring problem is a classical problem in combinatorial optimization that consists of assigning a color to each vertex of a graph such that no adjacent vertices share the same color, minimizing the number of colors used. Despite the various practical applications that exist for this problem, its NP-hardness still represents a computational challenge. Some of the best computational results obtained for this problem are consequences of hybridizing the various known heuristics. Automatically revising the space constituted by combining these techniques to find the most adequate combination has received less attention. In this paper, we propose exploring the heuristics space for the vertex coloring problem using evolutionary algorithms. We automatically generate three new algorithms by combining elementary heuristics. To evaluate the new algorithms, a computational experiment was performed that allowed comparing them numerically with existing heuristics. The obtained algorithms present an average 29.97% relative error, while four other heuristics selected from the literature present a 59.73% error, considering 29 of the more difficult instances in the DIMACS benchmark.     

The effect of the "patency test" on arterial endothelial surface

The effect of the "milking patency test" on the arterial endothelium of the experimental rat is investigated. Each of 18 rats served as its own control. Bilateral femoral artery anastomoses were performed in identical fashion. The milking patency test was performed on one side (experimental) but not on the other (control). After removal of the approximator clamps, rats were perfusion-fixed in situ. Harvested experimental vessels stained with silver showed a twofold increase in endothelial cell loss compared to controls. Visual evidence of extensive endothelial loss was seen on silver-stained segments in the tested area. This was corroborated by scanning electron microscopy. The degree of damage seen in this study suggests that the milking patency test is too traumatic for use in clinical microsurgery.     

Heuristics and general principles of learning

This research on decision-making heuristics is similar to research on animal learning in at least two ways. First, optimality modeling has not proven to be very useful for either research area. Second, both of these research areas seek to find general principles (or heuristics) that are applicable to different species in different settings. However, the basic principles of classical and operant conditioning seem to be more uniform across species and situations, whereas decision-making heuristics can vary for different species and different situations, even for tasks with very similar characteristics.     

Energy aware DAG scheduling on heterogeneous systems

We address the problem of scheduling directed a-cyclic task graph (DAG) on a heterogeneous distributed processor system with the twin objectives of minimizing finish time and energy consumption. Previous scheduling heuristics have assigned DAGs to processors to minimize overall run-time of the application. But applications on embedded systems, such as high performance DSP in image processing, multimedia, and wireless security, need schedules which use low energy too.