Academic literature on the topic 'Local search taxonomy'

Metagenomic sequencing technologies are advancing rapidly and the size of output data from high-throughput genetic sequencing has increased substantially over the years. This brings us to a scenario where advanced computational optimizations are requested to perform a metagenomic analysis. In this paper, we describe a new parallel implementation of nucleotide BLAST (MPI-blastn) and a new tool for taxonomic attachment of Basic Local Alignment Search Tool (BLAST) results that supports the NCBI taxonomy (NCBI-TaxCollector). MPI-blastn obtained a high performance when compared to the mpiBLAST and ScalaBLAST. In our best case, MPI-blastn was able to run 408 times faster in 384 cores. Our evaluations demonstrated that NCBI-TaxCollector is able to perform taxonomic attachments 125 times faster and needs 120 times less RAM than the previous TaxCollector. Through our optimizations, a multiple sequence search that currently takes 37 hours can be performed in less than 6 min and a post processing with NCBI taxonomic data attachment, which takes 48 hours, now is able to run in 23 min.

Between 1998 and 2004, the planning community has seen vast progress in terms of the sizes of benchmark examples that domain-independent planners can tackle successfully. The key technique behind this progress is the use of heuristic functions based on relaxing the planning task at hand, where the relaxation is to assume that all delete lists are empty. The unprecedented success of such methods, in many commonly used benchmark examples, calls for an understanding of what classes of domains these methods are well suited for. In the investigation at hand, we derive a formal background to such an understanding. We perform a case study covering a range of 30 commonly used STRIPS and ADL benchmark domains, including all examples used in the first four international planning competitions. We *prove* connections between domain structure and local search topology -- heuristic cost surface properties -- under an idealized version of the heuristic functions used in modern planners. The idealized heuristic function is called h^+, and differs from the practically used functions in that it returns the length of an *optimal* relaxed plan, which is NP-hard to compute. We identify several key characteristics of the topology under h^+, concerning the existence/non-existence of unrecognized dead ends, as well as the existence/non-existence of constant upper bounds on the difficulty of escaping local minima and benches. These distinctions divide the (set of all) planning domains into a taxonomy of classes of varying h^+ topology. As it turns out, many of the 30 investigated domains lie in classes with a relatively easy topology. Most particularly, 12 of the domains lie in classes where FF's search algorithm, provided with h^+, is a polynomial solving mechanism. We also present results relating h^+ to its approximation as implemented in FF. The behavior regarding dead ends is provably the same. We summarize the results of an empirical investigation showing that, in many domains, the topological qualities of h^+ are largely inherited by the approximation. The overall investigation gives a rare example of a successful analysis of the connections between typical-case problem structure, and search performance. The theoretical investigation also gives hints on how the topological phenomena might be automatically recognizable by domain analysis techniques. We outline some preliminary steps we made into that direction.

Understanding the relationship between a search algorithm and the space of problems is a fundamental issue in the optimization field. In this paper, we lay the foundations to elaborate taxonomies of problems under estimation of distribution algorithms (EDAs). By using an infinite population model and assuming that the selection operator is based on the rank of the solutions, we group optimization problems according to the behavior of the EDA. Throughout the definition of an equivalence relation between functions it is possible to partition the space of problems in equivalence classes in which the algorithm has the same behavior. We show that only the probabilistic model is able to generate different partitions of the set of possible problems and hence, it predetermines the number of different behaviors that the algorithm can exhibit. As a natural consequence of our definitions, all the objective functions are in the same equivalence class when the algorithm does not impose restrictions to the probabilistic model. The taxonomy of problems, which is also valid for finite populations, is studied in depth for a simple EDA that considers independence among the variables of the problem. We provide the sufficient and necessary condition to decide the equivalence between functions and then we develop the operators to describe and count the members of a class. In addition, we show the intrinsic relation between univariate EDAs and the neighborhood system induced by the Hamming distance by proving that all the functions in the same class have the same number of local optima and that they are in the same ranking positions. Finally, we carry out numerical simulations in order to analyze the different behaviors that the algorithm can exhibit for the functions defined over the search space [Formula: see text].

Detecting the communicative intent behind user queries is critically required by search engines to understand a user’s search goal and retrieve the desired results. Due to increased web searching in local languages, there is an emerging need to support the language understanding for languages other than English. This article presents a distinctive, capsule neural network architecture for intent detection from search queries in Urdu, a widely spoken South Asian language. The proposed two-tiered capsule network utilizes LSTM cells and an iterative routing mechanism between the capsules to effectively discriminate diversely expressed search intents. Since no Urdu queries dataset is available, a benchmark intent-annotated dataset of 11,751 queries was developed, incorporating 11 query domains and annotated with Broder’s intent taxonomy (i.e., navigational, transactional and informational intents). Through rigorous experimentation, the proposed model attained the state of the art accuracy of 91.12%, significantly improving upon several alternate classification techniques and strong baselines. An error analysis revealed systematic error patterns owing to a class imbalance and large lexical variability in Urdu web queries.

Straipsnis skiriamas euristinių optimizavimo algoritmų, kurie jau kelis dešimtmečius traukia kompiuterių mokslo specialistų dėmesį, klasifikavimo klausimų aptarčiai. Jame apibrėžiami euristinių algoritmų tikslai, paskirtis, jų principiniai skiriamieji faktoriai, savybės. Apžvelgiamos svarbesnių euristinių optimizavimo algoritmų (tokių kaip atkaitinimo modeliavimas, tabu paieška, genetiniai algoritmai ir pan.) klasifikavimo schemos (metodikos). Nagrinėjamas universalios algoritmų sudedamųjų komponentų matricos – substancinių konceptų sistemos – naudojimas klasifikuojant euristinius algoritmus. Pabaigoje pateikiamos apibendrinamosios išvados.Reikšminiai žodžiai: algoritmai, algoritmų klasės, euristiniai ir metaeuristiniai algoritmai, algoritmų klasifikavimas.On the classification of heuristic algorithmsAlfonsas Misevičius, Vytautas Bukšnaitis, Jonas Blonskis SummaryIn this paper, the issues related to the classification (taxonomy) of heuristic optimization algorithms are discussed. Firstly, the main goals and features of heuristic techniques are introduced. Further, we outline some important classification schemes (templates) for the classical and modern heuristic algorithms such as (descent) local search, simulated annealing, tabu search, genetic (evolutionary) algorithms, ant colony optimization, etc. We also analyze the basic aspects of a universal classification template based on a set of so-called substantial concepts, i.e. the fundamental structural components of the algorithms. The paper is completed with concluding remarks. Key words: algorithms, heuristic and metaheuristic algorithms, classification of algorithms.

This article presents a novel algorithm based on the cluster first-route second method, which executes a solution through K-means and Optics clustering techniques and Nearest Neighbor and Local Search 2-opt heuristics, for the solution of a vehicle routing problem with time windows (VRPTW). The objective of the problem focuses on reducing distances, supported by the variables of demand, delivery points, capacities, time windows and type of fleet in synergy with the model's taxonomy, based on data referring to deliveries made by a logistics operator in Colombia. As a result, good solutions are generated in minimum time periods after fulfilling the agreed constraints, providing high performance in route generation and solutions for large customer instances. Similarly, the algorithm demonstrates efficiency and competitiveness compared to other methods detailed in the literature, after being benchmarked with the Solomon instance data set, exporting even better results.

Abstract The distribution of the highly diversified and species-rich snake genus Atractus was assessed in search for endemism areas. The dataset of 6000 museum specimens was used to run an Endemicity Analyses in order to identify areas of biogeographic relevance for the genus Atractus. By using distinct methodological approaches and modifying the size and shape of grid cells we obtained a better adjustment to each species range, taking into account species distributed along the Andean and Atlantic Forest mountain ranges or certain vegetation constraints. Three scales of endemism were observed: micro endemic areas, represented by three different regions; intermediate sized endemic areas, represented by nine different regions; and macro-endemic areas, represented by four different provinces. Although most assessed regions corroborate well-defined biogeographic units according to the scientific literature, some, mainly located in the Colombian Andes, are not regularly considered in biogeographic syntheses carried out for vertebrates. Methodological approaches, along with a well curated database and taxonomic accuracy, may significantly influence the recovery of endemism areas, mainly considering mountain topography and local niche structure. The results present herein highlight the relevance of three Colombian Cordilleras, in order to completely understand Neotropical biota patterns of distribution. It is important to note that a well-resolved taxonomy represents both the framework and the first step toward a comprehensive biographical synthesis reducing Wallacean shortfalls in biodiversity.

Nocardiosis is a neglected tropical disease. It has varied geographical presence and a spectrum of clinical presentations. This review aims to focus on the epidemiology of nocardial infections with a systematic approach to their diagnosis and treatment. <i>Nocardia</i>causes chronic infections and ailments, and may remain cryptic but progressive in its course. Unless suspected, diagnosis can be easily missed resulting in increased morbidity and mortality. Thorough knowledge of local epidemiology, demography, clinical course and presentation, diagnostic modalities, and antibiotic susceptibility patterns of the prevalent <i>Nocardia</i> species is essential to curb spread of this infection. This is a systematic review in which internet search has been done for citation indices (Embase, PubMed, Ovid, and other individual journals) till March 2020 utilizing the following key words “Nocardia,” “taxonomy,” “prevalence,” “clinical features,” “diagnosis,” “treatment,” and “susceptibility.” We selected a total of 87 review articles, case series, and case reports all in English language.

Zamiaceae, a family of the ancient order Cycadales, is distributed throughout the tropical and subtropical regions of both the Old and New Worlds. Here, we present a systematic review of Zamiaceae with emphasis on Zamia species from South America. We aim to (a) establish the current knowledge, (b) identify research gaps, and (c) indicate directions for future studies, discussing ecology and conservation of South America species. The search recovered 508 papers, further classified into 11 research topics: taxonomy and systematics, morphology, biochemistry, genetics, phylogeography, population ecology, reproductive biology, ecological interactions, plant propagation, conservation, and reviews. The number of publications doubled in the 21st century, mostly focusing on genetics ( n = 60), taxonomy and systematics ( n = 52), morphology ( n = 36), ecological interactions ( n = 30), and an increasing interest in population ecology ( n = 29) and conservation ( n = 32). Studies are concentrated in North and Central America (54% of all studies) with just 6% (29) addressing South America species of Zamia. Overall, studies point out the key role of pollinators in promoting gene flow through pollen dispersal among populations of Zamiaceae. Therefore, investigate natural history, ecology, reproductive biology, genetic, and phylogeography, especially for South America species, are needed. Moreover, the implementation of in situ and ex situ collections and germplasm banks linked to botanical gardens are essential for the conservation and reestablishment of local populations of critically endangered Zamia species in South America. Concomitantly, we suggest studies modeling the distribution of Zamia species in future climate change scenarios.

Purpose: to determine the dependence of the development of local relapse depending on the chosen tactics of surgical treatment with different biological subtypes of breast cancer. Materials and methods: molecular taxonomy of breast cancer may improve the prognosis of regional regional recurrence (MPR) and has a great potential for improving decisionmaking regarding local treatment for breast cancer. The review of the world literature, reflecting prospective and retrospective studies on the biological characteristics of breast cancer, is reviewed. The studies reflect such parameters as the degree of malignancy, the age of the patients, the biological subtype of the tumor, and the treatment performed. The development of local and regional regional relapse was assessed depending on the choice of surgical treatment tactics: radical mastectomy and organ-preserving treatment + radiotherapy. The search was limited to 2001, when biological subtypes of breast cancer were identified. Prospective and retrospective studies were evaluated in patients with early operable breast cancer. Conclusions: young age, tumor malignancy, tumor node size, presence of lymphovascular invasion or lymph node involvement and unfavorable tumor subtypes such as Her2 /neu and triple-negative tumors can be considered as the main predictors of relapse in breast cancer. Tumors having a triple-negative nature have the most aggressive course, this concerns both local, regional relapse, and distant metastasis. Advances in modern neoadjuvant therapy have reduced the overall number of local relapses for all subgroups. Radiation therapy also helps to reduce the risk of local and regional recurrence. At present, there is no single-valued data on the choice of surgical treatment tactics for various biological subtypes, however effective systemic therapy as well as radiotherapy reduces the frequency of local recurrences after performing organ-preserving surgeries in unfavorable tumor subtypes and according to the results of studies, the total and disease-free survival is comparable, as and during mastectomy.

One of the challenges for the constraint satisfaction community has been to develop an automated approach to solving Constraint Satisfaction Problems (CSPs) rather than creating specific algorithms for specific problems. Much of this work has concentrated on the development and improvement of general purpose backtracking techniques. However, the success of relatively simple local search techniques on larger satisfiability problems [Selman et a!. 1992] and CSPs such as the n-queens [Minton et al. 1992] has caused interest in applying local search to constraint satisfaction. In this thesis we look at the usefulness of constraint weighting as a local search technique for constraint satisfaction. The work is based on the clause weighting ideas of Selman and Kautz [1993] and Moths [1993] and applies, evaluates and extends these ideas from the satisfiability domain to the more general domain of CSPs. Specifically, the contributions of the thesis are: 1. The introduction of a local search taxonomy. We examine the various better known local search techniques and recognise four basic strategies: restart, randomness, memory and weighting. 2. The extension of the CSP modelling framework. In order to represent and efficiently solve more realistic problems we extend the C SP modelling framework to include array-based domains and array-based domain use constraints. 3. The empirical evaluation of constraint weighting. We compare the performance of three constraint weighting strategies on a range of CSP and satisflability problems and with several other local search techniques. We find that no one technique dominates in all problem domains. 4. The characterisation of constraint weighting performance. Based on our empirical study we identiIS' the weighting behaviours and problem features that favour constrtt weighting. We conclude weighting does better on structured problems where the algorithm can recognise a harder sub-group of constraints. 5. The extension of constraint weighting. We introduce an efficient arc weighting algorithm that additionally weights connections between constraints that are simultaneously violated at a local minimum. This algorithm is empirically shown to outperform standard constraint weighting on a range of CSPs and within a general constraint solving system. Also we look at combining constraint weighting with other local search heuristics and find that these hybrid techniques can do well on problems where the parent algorithms are evenly matched. 6. The application of constraint weighting to over constrained domains. Our empirical work suggests constraint weighting does well for problems with distinctions between constraint groups. This led us to investigate solving real-world over constrained problems with hard and soft constraint groups and to introduce two dynamic constraint weighting heuristics that maintain a distinction between hard and soft constraint groups while still adding weights to violated constraints in a local minimum. In an empirical study, the dynamic schemes are shown to outperform other fixed weighting and non-weighting systems on a range of real world problems. In addition, the performance of weighting is shown to degrade less severely when soft constraints are added to the system, suggesting constraint weighting is especially applicable to realistic, hard and soft constraint problems
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Computing and Information Technology
Science, Environment, Engineering and Technology
Full Text

One of the challenges for the constraint satisfaction community has been to develop an automated approach to solving Constraint Satisfaction Problems (CSPs) rather than creating specific algorithms for specific problems. Much of this work has concentrated on the development and improvement of general purpose backtracking techniques. However, the success of relatively simple local search techniques on larger satisfiability problems [Selman et a!. 1992] and CSPs such as the n-queens [Minton et al. 1992] has caused interest in applying local search to constraint satisfaction. In this thesis we look at the usefulness of constraint weighting as a local search technique for constraint satisfaction. The work is based on the clause weighting ideas of Selman and Kautz [1993] and Moths [1993] and applies, evaluates and extends these ideas from the satisfiability domain to the more general domain of CSPs. Specifically, the contributions of the thesis are: 1. The introduction of a local search taxonomy. We examine the various better known local search techniques and recognise four basic strategies: restart, randomness, memory and weighting. 2. The extension of the CSP modelling framework. In order to represent and efficiently solve more realistic problems we extend the C SP modelling framework to include array-based domains and array-based domain use constraints. 3. The empirical evaluation of constraint weighting. We compare the performance of three constraint weighting strategies on a range of CSP and satisflability problems and with several other local search techniques. We find that no one technique dominates in all problem domains. 4. The characterisation of constraint weighting performance. Based on our empirical study we identiIS' the weighting behaviours and problem features that favour constrtt weighting. We conclude weighting does better on structured problems where the algorithm can recognise a harder sub-group of constraints. 5. The extension of constraint weighting. We introduce an efficient arc weighting algorithm that additionally weights connections between constraints that are simultaneously violated at a local minimum. This algorithm is empirically shown to outperform standard constraint weighting on a range of CSPs and within a general constraint solving system. Also we look at combining constraint weighting with other local search heuristics and find that these hybrid techniques can do well on problems where the parent algorithms are evenly matched. 6. The application of constraint weighting to over constrained domains. Our empirical work suggests constraint weighting does well for problems with distinctions between constraint groups. This led us to investigate solving real-world over constrained problems with hard and soft constraint groups and to introduce two dynamic constraint weighting heuristics that maintain a distinction between hard and soft constraint groups while still adding weights to violated constraints in a local minimum. In an empirical study, the dynamic schemes are shown to outperform other fixed weighting and non-weighting systems on a range of real world problems. In addition, the performance of weighting is shown to degrade less severely when soft constraints are added to the system, suggesting constraint weighting is especially applicable to realistic, hard and soft constraint problems

This chapter aims to collect, analyze, and compare quality data regarding the current status and prospective evolution of search engine platforms offered by leading platform companies. The authors describe the search MSPs competition across different markets in a general way and compare several emerging markets where Google MSP is not a leader. The methodology and organization of search platform ontology/taxonomy and search platform business models are discussed. Then detailed comparative analysis of search MSP innovation services and strategies is developed for Google SMSP and Yandex SMSP. Finally, the possible ways of further evolution of local SMSP and services are discussed.