Spatial interactions in simple and combined-feature visual search.

To isolate the mechanisms responsible for spatial interactions in visual search, we investigated the effects of inter-element distance and positional jittering in both simple (in/s) and combined-feature (inverted V in Vs) search tasks in which the observer had to find a target in a background of similar nontargets. Thresholds, defined as the stimulus duration for 75% correct, were measured for 'present' and 'absent' target conditions as a function of background numerosity (ranging from 4 to 64 background elements), independently for four inter-element distances and three positional jittering conditions. Results show: (1) both simple and combined-feature search involve a parallel, capacity limited process, (2) thresholds for parallel search of simple features are directly related to inter-element distance whereas this has little effect on thresholds in combined-feature search, and (3) positional jittering has a direct effect on thresholds in combined-feature search and an inverse effect in simple-feature search. These results indicate that two different mechanisms of spatial interactions are involved in parallel search. The activation of each of the two mechanisms depends on the stimulus used. In parallel search for simple and dissimilar features, the underlying mechanism is a short-range one, based on lateral inhibition, whereas the parallel search for combined and similar features is based on a nontarget grouping mechanism which relies on facilitatory interactions between regular elements.     

Search images not proven: A reappraisal of recent evidence

It is commonly agreed that predators hunting for cryptic prey have been demonstrated to adopt search images (involving perceptual specialization) for particular prey types. However, a simple alternative strategy, that of an appropriate reduction in search rate, may in many cases have the same effect as adopting a search image. The search image and search rate hypotheses are examined, and a series of critical predictions are proposed to distinguish them. Briefly, the search rate hypothesis predicts: (1) that adjusting search rate for one cryptic prey type will enhance the ability to detect other equally cryptic types (the search image hypothesis predicts that this will interfere with the ability to detect other equally cryptic types); (2) that adjusting search rate for cryptic prey will be achieved by learning to spend longer looking at each patch of the environment, and that the more cryptic the prey the longer will be the viewing time required to effect accurate detection (the search image hypothesis makes no such predictions). Four recent studies purporting to demonstrate search images are re-examined in the light of these predictions, and it is found that the published data fail to distinguish the two hypotheses. In addition, some evidence that is better explained by the search rate hypothesis is discussed. A brief examination of the ecological consequences of the search rate hypothesis shows that, unlike the search image hypothesis, it does not predict apostatic selection. It is therefore argued that the distinction between the two mechanisms explaining how predators ‘learn to see’ cryptic prey is important, but that the critical tests have not yet been made. The existence of search images remains not proven.     

Saltatory search: a theoretical analysis

Many animal search in a saltatory fashion: they move forward,pause briefly, and move forward again. Although many optimal-foragingmodels have been developed, most do not address how an animalsearches for food. We view search strategies as "time-distance"functions to allow not only for the possibility of oscillationsin body speed, as implied by saltatory search, but other movementpatterns as well, including cruise search. The key feature ofour models is distinguishing between the body position and thescan position (where the forager is looking). We see the varyingmovement of saltatory search as a consequence of the curvaturein the functions that relate body speed to benefits (Jensen'sinequality)     

A rapid heuristic algorithm for finding minimum evolution trees

The minimum sum of branch lengths (S), or the minimum evolution (ME) principle, has been shown to be a good optimization criterion in phylogenetic inference. Unfortunately, the number of topologies to be analyzed is computationally prohibitive when a large number of taxa are involved. Therefore, simplified, heuristic methods, such as the neighbor-joining (NJ) method, are usually employed instead. The NJ method analyzes only a small number of trees (compared with the size of the entire search space); so, the tree obtained may not be the ME tree (for which the S value is minimum over the entire search space). Different compromises between very restrictive and exhaustive search spaces have been proposed recently. In particular, the "stepwise algorithm" (SA) utilizes what is known in computer science as the "beam search," whereas the NJ method employs a "greedy search." SA is virtually guaranteed to find the ME trees while being much faster than exhaustive search algorithms. In this study we propose an even faster method for finding the ME tree. The new algorithm adjusts its search exhaustiveness (from greedy to complete) according to the statistical reliability of the tree node being reconstructed. It is also virtually guaranteed to find the ME tree. The performances and computational efficiencies of ME, SA, NJ, and our new method were compared in extensive simulation studies. The new algorithm was found to perform practically as well as the SA (and, therefore, ME) methods and slightly better than the NJ method. For searching for the globally optimal ME tree, the new algorithm is significantly faster than existing ones, thus making it relatively practical for obtaining all trees with an S value equal to or smaller than that of the NJ tree, even when a large number of taxa is involved.     

Search filters for finding prognostic and diagnostic prediction studies in Medline to enhance systematic reviews

Background

The interest in prognostic reviews is increasing, but to properly review existing evidence an accurate search filer for finding prediction research is needed. The aim of this paper was to validate and update two previously introduced search filters for finding prediction research in Medline: the Ingui filter and the Haynes Broad filter.

Methodology/Principal Findings

Based on a hand search of 6 general journals in 2008 we constructed two sets of papers. Set 1 consisted of prediction research papers (n = 71), and set 2 consisted of the remaining papers (n = 1133). Both search filters were validated in two ways, using diagnostic accuracy measures as performance measures. First, we compared studies in set 1 (reference) with studies retrieved by the search strategies as applied in Medline. Second, we compared studies from 4 published systematic reviews (reference) with studies retrieved by the search filter as applied in Medline. Next – using word frequency methods – we constructed an additional search string for finding prediction research. Both search filters were good in identifying clinical prediction models: sensitivity ranged from 0.94 to 1.0 using our hand search as reference, and 0.78 to 0.89 using the systematic reviews as reference. This latter performance measure even increased to around 0.95 (range 0.90 to 0.97) when either search filter was combined with the additional string that we developed. Retrieval rate of explorative prediction research was poor, both using our hand search or our systematic review as reference, and even combined with our additional search string: sensitivity ranged from 0.44 to 0.85.

Conclusions/Significance

Explorative prediction research is difficult to find in Medline, using any of the currently available search filters. Yet, application of either the Ingui filter or the Haynes broad filter results in a very low number missed clinical prediction model studies.     

SeMoP: a new computational strategy for the unrestricted search for modified peptides using LC-MS/MS data

A novel computational approach, termed Search for Modified Peptides (SeMoP), for the unrestricted discovery and verification of peptide modifications in shotgun proteomic experiments using low resolution ion trap MS/MS spectra is presented. Various peptide modifications, including post-translational modifications, sequence polymorphisms, as well as sample handling-induced changes, can be identified using this approach. SeMoP utilizes a three-step strategy: (1) a standard database search to identify proteins in a sample; (2) an unrestricted search for modifications using a newly developed algorithm; and (3) a second standard database search targeted to specific modifications found using the unrestricted search. This targeted approach provides verification of discovered modifications and, due to increased sensitivity, a general increase in the number of peptides with the specific modification. The feasibility of the overall strategy has been first demonstrated in the analysis of 65 plasma proteins. Various sample handling induced modifications, such as beta-elimination of disulfide bridges and pyrocarbamidomethylation, as well as biologically induced modifications, such as phosphorylation and methylation, have been detected. A subsequent targeted Sequest search has been used to verify selected modifications, and a 4-fold increase in the number of modified peptides was obtained. In a second application, 1367 proteins of a cervical cancer cell line were processed, leading to detection of several novel amino acid substitutions. By conducting the search against a database of peptides derived from proteins with decoy sequences, a false discovery rate of less than 5% for the unrestricted search resulted. SeMoP is shown to be an effective and easily implemented approach for the discovery and verification of peptide modifications.     

Clustering of PubMed abstracts using nearer terms of the domain

Literature search is a process in which external developers provide alternative representations for efficient data mining of biomedical literature such as ranking search results, displaying summarized knowledge of semantics and clustering results into topics. In clustering search results, prominent vocabularies, such as GO (Gene Ontology), MeSH(Medical Subject Headings) and frequent terms extracted from retrieved PubMed abstracts have been used as topics for grouping. In this study, we have proposed FNeTD (Frequent Nearer Terms of the Domain) method for PubMed abstracts clustering. This is achieved through a two-step process viz; i) identifying frequent words or phrases in the abstracts through the frequent multi-word extraction algorithm and ii) identifying nearer terms of the domain from the extracted frequent phrases using the nearest neighbors search. The efficiency of the clustering of PubMed abstracts using nearer terms of the domain was measured using F-score. The present study suggests that nearer terms of the domain can be used for clustering the search results.     

Integration and Disruption Effects of Shape and Texture in Haptic Search

In a search task, where one has to search for the presence of a target among distractors, the target is sometimes easily found, whereas in other searches it is much harder to find. The performance in a search task is influenced by the identity of the target, the identity of the distractors and the differences between the two. In this study, these factors were manipulated by varying the target and distractors in shape (cube or sphere) and roughness (rough or smooth) in a haptic search task. Participants had to grasp a bundle of items and determine as fast as possible whether a predefined target was present or not. It was found that roughness and edges were relatively salient features and the search for the presence of these features was faster than for their absence. If the task was easy, the addition of these features could also disrupt performance, even if they were irrelevant for the search task. Another important finding was that the search for a target that differed in two properties from the distractors was faster than a task with only a single property difference, although this was only found if the two target properties were non-salient. This means that shape and texture can be effectively integrated. Finally, it was found that edges are more beneficial to a search task than disrupting, whereas for roughness this was the other way round.     

Optimization of brownian search strategies

What are the simplest search strategies that lead an animal to a particular target, what are their limitations, and what changes can be made to develop more effective strategies? To answer these question a class of search strategies was examined that require an animal to have only a minimal capacity for spatial orientation; the effectiveness of such strategies in solving the following basic search problem was determined. The animal begins its search at a distance r _o (starting distance) from a spatially fixed target. It detects the target when it has approached it to within a certain distance a (the detection radius). The analysed class of search strategies has the following characteristics: C1. The animal uses the same search strategy in all regions it enters. Therefore it needs no information as to the actual location of the target. C2. Its search strategy is constant in time. The animal has only to detect whether it has reached the target or not. C3. Once the animal has chosen a direction, it continues in that direction for a certain distance. This is the only way in which the preceding parts of the search affect the animal's decision as to the direction in which it will search next. In the long term the animal's movement directions are independent, with no preference for any particular direction. Despite their extreme simplicity in application these “Brownian” search strategies are remarkably successful (Fig. 1). Indeed, if the search is continued long enough the target is certain to be found. The success of the search depends in part on the search duration (Fig. 2) or the search-path length S, the starting distance and the detection radius. On the other hand, an animal can have a decisive influence on its degree of success simply by adjusting the frequency with which it changes its walking direction to match its sensory abilities. That is, a not-too-short Brownian search (S?r _o) is most successful when the searching animal, between the points at which it changes direction, walks approximately straight for a distance equal to the detection radius (Figs. 3 and 4). A further increase in search effectiveness is possible only by turning to another class of search strategies. These, however, demand that the animal either have more information about the position of its target at the beginning of the search or be able to organize its search behavior even over fairly long periods of time.     

Influence of inter-item symmetry in visual search

Does visual search involve a serial inspection of individual items (Feature Integration Theory) or are items grouped and segregated prior to their consideration as a possible target (Attentional Engagement Theory)? For search items defined by motion and shape there is strong support for prior grouping (Kingstone and Bischof, 1999). The present study tested for grouping based on inter-item shape symmetry. Results showed that target-distractor symmetry strongly influenced search whereas distractor-distractor symmetry influenced search more weakly. This indicates that static shapes are evaluated for similarity to one another prior to their explicit identification as 'target' or 'distractor'. Possible reasons for the unequal contributions of target-distractor and distractor-distractor relations are discussed.     

Learning from Decoys to Improve the Sensitivity and Specificity of Proteomics Database Search Results

The statistical validation of database search results is a complex issue in bottom-up proteomics. The correct and incorrect peptide spectrum match (PSM) scores overlap significantly, making an accurate assessment of true peptide matches challenging. Since the complete separation between the true and false hits is practically never achieved, there is need for better methods and rescoring algorithms to improve upon the primary database search results. Here we describe the calibration and False Discovery Rate (FDR) estimation of database search scores through a dynamic FDR calculation method, FlexiFDR, which increases both the sensitivity and specificity of search results. Modelling a simple linear regression on the decoy hits for different charge states, the method maximized the number of true positives and reduced the number of false negatives in several standard datasets of varying complexity (18-mix, 49-mix, 200-mix) and few complex datasets (E. coli and Yeast) obtained from a wide variety of MS platforms. The net positive gain for correct spectral and peptide identifications was up to 14.81% and 6.2% respectively. The approach is applicable to different search methodologies- separate as well as concatenated database search, high mass accuracy, and semi-tryptic and modification searches. FlexiFDR was also applied to Mascot results and showed better performance than before. We have shown that appropriate threshold learnt from decoys, can be very effective in improving the database search results. FlexiFDR adapts itself to different instruments, data types and MS platforms. It learns from the decoy hits and sets a flexible threshold that automatically aligns itself to the underlying variables of data quality and size.     

A computational model of visual marking using an inter-connected network of spiking neurons: the spiking search over time & space model (sSoTS).

In the real world, visual information is selected over time as well as space, when we prioritise new stimuli for attention. Watson and Humphreys [Watson, D., Humphreys, G.W., 1997. Visual marking: prioritizing selection for new objects by top-down attentional inhibition of old objects. Psychological Review 104, 90-122] presented evidence that new information in search tasks is prioritised by (amongst other processes) active ignoring of old items - a process they termed visual marking. In this paper we present, for the first time, an explicit computational model of visual marking using biologically plausible activation functions. The "spiking search over time and space" model (sSoTS) incorporates different synaptic components (NMDA, AMPA, GABA) and a frequency adaptation mechanism based on [Ca(2+)] sensitive K(+) current. This frequency adaptation current can act as a mechanism that suppresses the previously attended items. We show that, when coupled with a process of active inhibition applied to old items, frequency adaptation leads to old items being de-prioritised (and new items prioritised) across time in search. Furthermore, the time course of these processes mimics the time course of the preview effect in human search. The results indicate that the sSoTS model can provide a biologically plausible account of human search over time as well as space.     

How to reliably estimate the tortuosity of an animal's path: straightness, sinuosity, or fractal dimension?

The tortuosity of an animal's path is a key parameter in orientation and searching behaviours. The tortuosity of an oriented path is inversely related to the efficiency of the orientation mechanism involved, the best mechanism being assumed to allow the animal to reach its goal along a straight line movement. The tortuosity of a random search path controls the local searching intensity, allowing the animal to adjust its search effort to the local profitability of the environment. This paper shows that (1) the efficiency of an oriented path can be reliably estimated by a straightness index computed as the ratio between the distance from the starting point to the goal and the path length travelled to reach the goal, but such a simple index, ranging between 0 and 1, cannot be applied to random search paths; (2) the tortuosity of a random search path, ranging between straight line movement and Brownian motion, can be reliably estimated by a sinuosity index which combines the mean cosine of changes of direction with the mean step length; and (3) in the current state of the art, the fractal analysis of animals' paths, which may appear as an alternative and promising way to measure the tortuosity of a random search path as a fractal dimension ranging between 1 (straight line movement) and 2 (Brownian motion), is only liable to generate artifactual results. This paper also provides some help for distinguishing between oriented and random search paths, and depicts a general, comprehensive framework for analysing individual animals' paths in a two-dimensional space.     

An evaluation, comparison, and accurate benchmarking of several publicly available MS/MS search algorithms: sensitivity and specificity analysis

MS/MS and associated database search algorithms are essential proteomic tools for identifying peptides. Due to their widespread use, it is now time to perform a systematic analysis of the various algorithms currently in use. Using blood specimens used in the HUPO Plasma Proteome Project, we have evaluated five search algorithms with respect to their sensitivity and specificity, and have also accurately benchmarked them based on specified false-positive (FP) rates. Spectrum Mill and SEQUEST performed well in terms of sensitivity, but were inferior to MASCOT, X!Tandem, and Sonar in terms of specificity. Overall, MASCOT, a probabilistic search algorithm, correctly identified most peptides based on a specified FP rate. The rescoring algorithm, PeptideProphet, enhanced the overall performance of the SEQUEST algorithm, as well as provided predictable FP error rates. Ideally, score thresholds should be calculated for each peptide spectrum or minimally, derived from a reversed-sequence search as demonstrated in this study based on a validated data set. The availability of open-source search algorithms, such as X!Tandem, makes it feasible to further improve the validation process (manual or automatic) on the basis of "consensus scoring", i.e., the use of multiple (at least two) search algorithms to reduce the number of FPs. complement.     

The Gene-Duplication Problem: Near-Linear Time Algorithms for NNI-Based Local Searches

The gene-duplication problem is to infer a species supertree from a collection of gene trees that are confounded by complex histories of gene-duplication events. This problem is NP-complete and thus requires efficient and effective heuristics. Existing heuristics perform a stepwise search of the tree space, where each step is guided by an exact solution to an instance of a local search problem. A classical local search problem is the {tt NNI} search problem, which is based on the nearest neighbor interchange operation. In this work, we 1) provide a novel near-linear time algorithm for the {tt NNI} search problem, 2) introduce extensions that significantly enlarge the search space of the {tt NNI} search problem, and 3) present algorithms for these extended versions that are asymptotically just as efficient as our algorithm for the {tt NNI} search problem. The exceptional speedup achieved in the extended {tt NNI} search problems makes the gene-duplication problem more tractable for large-scale phylogenetic analyses. We verify the performance of our algorithms in a comparison study using sets of large randomly generated gene trees.     

Attentional Requirements on Feature Search Are Modulated by Stimulus Properties

We report a series of dual-task experiments, in which a rapid serial visual presentation (RSVP) task was combined with a visual search task. Orientation, motion, and color were used as the defining target features in the search task. Lag between target onsets was manipulated and interference between the two tasks was quantified by measuring detection scores for the search task as a function of lag. While simultaneous performance of an orientation detection task with an RSVP letter identification task resulted in a performance decrease for lags up to 320 ms, no such decrease was detected for highly salient motion- and color-defined targets. Subsequently, detectability of the motion and color feature was matched to that of the orientation-feature resulting in the reintroduction of a (smaller) performance decrease, but only during simultaneous performance (lag 0 ms). The results suggest that there are two causes for the impaired search performance occurring when a feature search task is combined with an RSVP task. The first is short-lasting interference probably due to attentional competition; the second, which plays a role only when targets for both tasks share features, is interference that may be attributed to a central processing bottleneck.     

MSblender: A probabilistic approach for integrating peptide identifications from multiple database search engines

Shotgun proteomics using mass spectrometry is a powerful method for protein identification but suffers limited sensitivity in complex samples. Integrating peptide identifications from multiple database search engines is a promising strategy to increase the number of peptide identifications and reduce the volume of unassigned tandem mass spectra. Existing methods pool statistical significance scores such as p-values or posterior probabilities of peptide-spectrum matches (PSMs) from multiple search engines after high scoring peptides have been assigned to spectra, but these methods lack reliable control of identification error rates as data are integrated from different search engines. We developed a statistically coherent method for integrative analysis, termed MSblender. MSblender converts raw search scores from search engines into a probability score for every possible PSM and properly accounts for the correlation between search scores. The method reliably estimates false discovery rates and identifies more PSMs than any single search engine at the same false discovery rate. Increased identifications increment spectral counts for most proteins and allow quantification of proteins that would not have been quantified by individual search engines. We also demonstrate that enhanced quantification contributes to improve sensitivity in differential expression analyses.     

Efficiencies of fast algorithms of phylogenetic inference under the criteria of maximum parsimony, minimum evolution, and maximum likelihood when a large number of sequences are used

In phylogenetic inference by maximum-parsimony (MP), minimum-evolution (ME), and maximum-likelihood (ML) methods, it is customary to conduct extensive heuristic searches of MP, ME, and ML trees, examining a large number of different topologies. However, these extensive searches tend to give incorrect tree topologies. Here we show by extensive computer simulation that when the number of nucleotide sequences (m) is large and the number of nucleotides used (n) is relatively small, the simple MP or ML tree search algorithms such as the stepwise addition (SA) plus nearest neighbor interchange (NNI) search and the SA plus subtree pruning regrafting (SPR) search are as efficient as the extensive search algorithms such as the SA plus tree bisection-reconnection (TBR) search in inferring the true tree. In the case of ME methods, the simple neighbor-joining (NJ) algorithm is as efficient as or more efficient than the extensive NJ+TBR search. We show that when ME methods are used, the simple p distance generally gives better results in phylogenetic inference than more complicated distance measures such as the Hasegawa-Kishino-Yano (HKY) distance, even when nucleotide substitution follows the HKY model. When ML methods are used, the simple Jukes-Cantor (JC) model of phylogenetic inference generally shows a better performance than the HKY model even if the likelihood value for the HKY model is much higher than that for the JC model. This indicates that at least in the present case, selecting of a substitution model by using the likelihood ratio test or the AIC index is not appropriate. When n is small relative to m and the extent of sequence divergence is high, the NJ method with p distance often shows a better performance than ML methods with the JC model. However, when the level of sequence divergence is low, this is not the case.