DNA barcodes are used as unique identifiers in high-throughput sequencing technologies with applications in areas such as single cell analysis, spatial transcriptomics and DNA data storage. Given a set of barcodes and a set of reads, each containing a barcode, the task of barcode calling is to assign each read to its respective barcode. This is challenging in applications involving large barcode sets and high rates of base insertion, deletion and substitution errors. Naive solutions require the calculation of pairwise distances between each barcode and read. As this is infeasible for modern applications with millions of barcodes and billions of reads, much work has been done during the previous years in accelerating this task. In 2026, Uphoff et al. introduced the barcode calling tool Quik based on k-mer filtering and pseudo-distances. They demonstrated that it is faster than state-of-the-art tools by several orders of magnitude. Here, we present Quik 2.0, which is faster than the original release by a factor of up to 56 and scales well to multiple GPUs. We discuss several algorithmic design choices that led to this speedup. In large-scale experiments with 10⁶ barcodes, we can now process approximately 300 million reads per hour on a GPU server equipped with four GPUs. In addition, we show that unfiltered barcode calling approaches can only slightly improve the accuracy at the cost of a vastly increased running time. Finally, we introduce more fine-grained assignment rejection criteria to achieve a better trade-off between precision and acceptance rate. To help users select suitable rejection parameters for real-world experiments, we propose an automatic calibration procedure that optimizes parameters for specific barcode and read sets.

Traffic assignment is a core component of many urban transport planning tools. It is used to determine how traffic is distributed over a transportation network. We study the task of computing traffic assignments for public transport: Given a public transit network, a timetable, vehicle capacities and a demand (i.e. a list of passengers, each with an associated origin, destination, and departure time), the goal is to predict the resulting passenger flow and the corresponding load of each vehicle. Microscopic stochastic simulation of individual passengers is a standard, but computationally expensive approach. Briem et al. (2017) have shown that a clever adaptation of the Connection Scan Algorithm (CSA) can lead to highly efficient traffic assignment algorithms, but ignores vehicle capacities, resulting in overcrowded vehicles. Taking their work as a starting point, we here propose a new and extended model that guarantees capacity-feasible assignments and incorporates dynamic network congestion effects such as crowded vehicles, denied boarding, and dwell time delays. Moreover, we also incorporate learning and adaptation of individual passengers based on their experience with the network. Applications include studying the evolution of perceived travel times as a result of adaptation, the impact of an increase in capacity, or network effects due to changes in the timetable such as the addition or the removal of a service or a whole line. The proposed framework has been experimentally evaluated with public transport networks of Göttingen and Stuttgart (Germany). The simulation proves to be highly efficient. On a standard PC the computation of a traffic assignment takes just a few seconds per simulation day.

The design and optimization of public transport systems is a highly complex and challenging process. Here, we focus on the trade-off between two criteria which shall make the transport system attractive for passengers: their travel time and the robustness of the system. The latter is time-consuming to evaluate. A passenger-based evaluation of robustness requires a performance simulation with respect to a large number of possible delay scenarios, making this step computationally very expensive. For optimizing the robustness, we hence apply a machine-learned oracle from previous work which approximates the robustness of a public transport system. We apply this oracle to bi-criteria optimization of integrated public transport planning (timetabling and vehicle scheduling) in two ways: First, we explore a local search based framework studying several variants of neighborhoods. Second, we evaluate a genetic algorithm. Computational experiments with artificial and close to real-word benchmark datasets yield promising results. In all cases, an existing pool of solutions (i.e., public transport plans) can be significantly improved by finding a number of new non-dominated solutions, providing better and different trade-offs between robustness and travel time.

Due to the significant growth in passenger numbers, higher vehicle load factors and crowding become more and more of an issue in public transport. For safety reasons and because of an unsatisfactory discomfort, standing of passengers is rather limited in high-speed long-distance trains. In case of delays and (partially) cancelled trains, many passengers have to be rerouted. State-of-the-art rerouting merely focuses on minimizing delay at the destination of affected passengers but neglects limited vehicle capacities and crowding. Not considering capacities allows using highly efficient shortest path algorithms like RAPTOR or the connection scan algorithm (CSA). In this paper, we study the more complicated scenario where passengers compete for scarce capacities. This can be modeled as a piece-wise linear, convex cost multi-source multi-commodity unsplittable flow problem where each passenger group which has to be rerouted corresponds to a commodity. We compare a path-based integer linear programming (ILP) model with a heuristic greedy approach. In experiments with instances from German long-distance train traffic, we quantify the importance of considering vehicle capacities in case of train cancellations. We observe a tradeoff: The ILP approach slightly outperforms the greedy approach and both are much better than capacity unaware rerouting in quality, while the greedy algorithm runs more than three times faster.

Providing attractive and efficient public transport services is of crucial importance due to higher demands for mobility and the need to reduce air pollution and to save energy. The classical planning process in public transport tries to achieve a reasonable compromise between service quality for passengers and operating costs. Service quality mostly considers quantities like average travel time and number of transfers. Since daily public transport inevitably suffers from delays caused by random disturbances and disruptions, robustness also plays a crucial role. While there are recent attempts to achieve delay-resistant timetables, comparably little work has been done to systematically assess and to compare the robustness of transport plans from a passenger point of view. We here provide a general and flexible framework for evaluating public transport plans (lines, timetables, and vehicle schedules) in various ways. It enables planners to explore several trade-offs between operating costs, service quality (average perceived travel time of passengers), and robustness against delays. For such an assessment we develop several passenger-oriented robustness tests which can be instantiated with parameterized delay scenarios. Important features of our framework include detailed passenger flow models, delay propagation schemes and disposition strategies, rerouting strategies as well as vehicle capacities. To demonstrate possible use cases, our framework has been applied to a variety of public transport plans which have been created for the same given demand for an artificial urban grid network and to instances for long-distance train networks. As one application we study the impact of different strategies to improve the robustness of timetables by insertion of supplement times. We also show that the framework can be used to optimize waiting strategies in delay management.

Read trimming is a fundamental first step of the analysis of next generation sequencing (NGS) data. Traditionally, it is performed heuristically, and algorithmic work in this area has been neglected. Here, we address this topic and formulate three optimization problems for block-based trimming (truncating the same low-quality positions at both ends for all reads and removing low-quality truncated reads). We find that all problems are NP-hard. Hence, we investigate the approximability of the problems. Two of them are NP-hard to approximate. However, the non-random distribution of quality scores in NGS data sets makes it tempting to speculate that quality constraints for read positions are typically satisfied by fulfilling quality constraints for reads. Thus, we propose three relaxed problems and develop efficient polynomial-time algorithms for them including heuristic speed-up techniques and parallelizations. We apply these optimized block trimming algorithms to 12 data sets from three species, four sequencers, and read lengths ranging from 36 to 101 bp and find that (i) the omitted constraints are indeed almost always satisfied, (ii) the optimized read trimming algorithms typically yield a higher number of untrimmed bases than traditional heuristics, and (iii) these results can be generalized to alternative objective functions beyond counting the number of untrimmed bases.

The classical planning process in public transport planning focuses on the two criteria operating costs and quality for passengers. Quality mostly considers quantities like average travel time and number of transfers. Since public transport often suffers from delays caused by random disturbances, we are interested in adding a third dimension: robustness. We propose passenger-oriented robustness indicators for public transport networks and timetables. These robustness indicators are evaluated for several public transport plans which have been created for an artificial urban network with the same demand. The study shows that these indicators are suitable to measure the robustness of a line plan and a timetable. We explore different trade-offs between operating costs, quality (average travel time of passengers), and robustness against delays. Our results show that the proposed robustness indicators give reasonable results.

Frequent train delays make passenger-oriented train dispatching a task of high practical relevance. In case of delays, dispatchers have to decide whether trains should wait for one or several delayed feeder trains or should depart on time. To support dispatchers, we have recently introduced the train dispatching framework PANDA (CASPT 2015). In this paper, we present and evaluate two enhancements which are also of general interest. First, we study the sensitivity of waiting decisions with respect to the accuracy of passenger flow data. More specifically, we develop an integer linear programming formulation for the following optimization problem: Given a critical transfer, what is the minimum number of passengers we have to add or to subtract from the given passenger flow such that the decision would change from waiting to non-waiting or vice versa? Based on experiments with realistic passenger flows and delay data from 2015 in Germany, an important empirical finding is that a significant fraction of all decisions is highly sensitive to small changes in passenger flow composition. Hence, very accurate passenger flows are needed in these cases. Second, we investigate the practical value of more sophisticated simulations. A simple strategy evaluates the effect of a waiting decision of some critical transfer on passenger delay subject to the assumption that all subsequent decisions are taken according to standard waiting time rules, as usually employed by railway companies like Deutsche Bahn. Here we analyze the impact of a higher level of simulation where waiting decisions for a critical transfer are considered jointly with one or more other decisions for subsequent transfers. We learn that such "coupled decisions" lead to improved solution in about 6.3% of all considered cases.

Passenger-friendly train disposition is a challenging, highly complex online optimization problem with uncertain and incomplete information about future delays. In this paper we focus on the timing within the disposition process. We introduce three different classification schemes to predict as early as possible the status of a transfer: whether it will almost surely break, is so critically delayed that it requires manual disposition, or can be regarded as only slightly uncertain or as being safe. The three approaches use lower bounds on travel times, historical distributions of delay data, and fuzzy logic, respectively. In experiments with real delay data we achieve an excellent classification rate. Furthermore, using realistic passenger flows we observe that there is a significant potential to reduce the passenger delay if an early rerouting strategy is applied.

We outline a blueprint for the development of new computer science approaches for the management and analysis of big data problems for biodiversity science. Such problems are characterized by a combination of different data sources each of which owns at least one of the typical characteristics of big data (volume, variety, velocity, or veracity). For these problems, we envision a solution that covers different aspects of integrating data sources and algorithms for their analysis on one of the following three layers: At the data layer, there are various data archives of heterogeneous, unstructured, and uncertain data. At the functional layer, the data are analyzed for each archive individually. At the meta-layer, multiple functional archives are combined for complex analysis.

Timetable information is the process of determining a suitable travel route for a passenger. Due to delays in the original timetable, in practice it often happens that the travel route cannot be used as originally planned. For a passenger being already en route, it would hence be useful to know about alternatives that ensure that his/her destination can be reached. In this work we propose a recoverable robust approach to timetable information; i.e., we aim at finding travel routes that can easily be updated when delays occur during the journey. We present polynomial-time algorithms for this problem and evaluate the performance of the routes obtained this way on schedule data of the German train network of 2013 and simulated delay scenarios.

In daily operation, railway traffic always deviates from the planned schedule to a certain extent. Primary initial delays of trains may cause a whole cascade of secondary delays of other trains over the entire network. In this paper, we propose a stochastic model for delay propagation and forecasts of arrival and departure events which is applicable to all kind of public transport (not only to railway traffic). Our model is fairly realistic, it includes general waiting policies (how long do trains wait for delayed feeder trains), it uses driving time profiles (discrete distributions) on travel arcs which depend on the departure time, and it incorporates the catch-up potential of buffer times on driving sections and train stops. The model is suited for an online scenario where a massive stream of update messages on the current status of trains arrives which has to be propagated through the whole network. Efficient stochastic propagation of delays has important applications in online timetable information, in delay management and train disposition, and in stability analysis of timetables. The proposed approach has been implemented and evaluated on the German timetable of 2011 with waiting policies of Deutsche Bahn AG. A complete stochastic delay propagation for the whole German train network and a whole day can be performed in less than 14 seconds on a PC. We tested our propagation algorithm with artificial discrete travel time distributions which can be parametrized by the size of their fluctuations. Our forecasts are compared with real data. It turns out that stochastic propagation of delays is efficient enough to be applicable in practice, but the forecast quality requires further adjustments of our artificial travel time distributions to estimates from real data.

In timetable information in public transport the goal is to search for a good passenger's path between an origin and a destination. Usually, the travel time and the number of transfers shall be minimized. In this paper, we consider robust timetable information, i.e. we want to identify a path which will bring the passenger to the planned destination even in the case of delays. The classic notion of strict robustness leads to the problem of identifying those changing activities which will never break in any of the expected delay scenarios. We show that this is in general a strongly NP-hard problem. Therefore, we propose a conservative heuristic which identifies a large subset of these robust changing activities in polynomial time by dynamic programming and so allows us to find strictly robust paths efficiently. We also transfer the notion of light robustness, originally introduced for timetabling, to timetable information. In computational experiments we then study the price of strict and light robustness: How much longer is the travel time of a robust path than of a shortest one according to the published schedule? Based on the schedule of high-speed trains within Germany of 2011, we quantitatively explore the trade-off between the level of guaranteed robustness and the increase in travel time. Strict robustness turns out to be too conservative, while light robustness is promising: a modest level of guarantees is achievable at a reasonable price for the majority of passengers.

Abstract The search for attractive night train connections is fundamentally different from ordinary search: the primary objective of a customer of a night train is to have a reasonably long sleeping period without interruptions due to train changes. For most passengers it is also undesirable to reach the final destination too early in the morning. These objectives are in sharp contrast to standard information systems which focus on minimizing the total travel time. In this article, we present and compare two new approaches to support queries for night train connections. These approaches have been integrated into the Multi‐Objective Traffic Information System (MOTIS), which is currently being developed by our group. Its purpose is to find all train connections which are attractive from a customer point of view. Using a computational study, we demonstrate that our specialized algorithms for night train connections are able to satisfy customer queries much better than standard methods. This can be achieved with reasonable computational costs: a specialized night train search requires only a few seconds of CPU time. © 2010 Wiley Periodicals, Inc. NETWORKS, 2011

BACKGROUND: Mass spectrometry has become the analytical method of choice in metabolomics research. The identification of unknown compounds is the main bottleneck. In addition to the precursor mass, tandem MS spectra carry informative fragment peaks, but the coverage of spectral libraries of measured reference compounds are far from covering the complete chemical space. Compound libraries such as PubChem or KEGG describe a larger number of compounds, which can be used to compare their in silico fragmentation with spectra of unknown metabolites. RESULTS: We created the MetFrag suite to obtain a candidate list from compound libraries based on the precursor mass, subsequently ranked by the agreement between measured and in silico fragments. In the evaluation MetFrag was able to rank most of the correct compounds within the top 3 candidates returned by an exact mass query in KEGG. Compared to a previously published study, MetFrag obtained better results than the commercial MassFrontier software. Especially for large compound libraries, the candidates with a good score show a high structural similarity or just different stereochemistry, a subsequent clustering based on chemical distances reduces this redundancy. The in silico fragmentation requires less than a second to process a molecule, and MetFrag performs a search in KEGG or PubChem on average within 30 to 300 seconds, respectively, on an average desktop PC. CONCLUSIONS: We presented a method that is able to identify small molecules from tandem MS measurements, even without spectral reference data or a large set of fragmentation rules. With today's massive general purpose compound libraries we obtain dozens of very similar candidates, which still allows a confident estimate of the correct compound class. Our tool MetFrag improves the identification of unknown substances from tandem MS spectra and delivers better results than comparable commercial software. MetFrag is available through a web application, web services and as java library. The web frontend allows the end-user to analyse single spectra and browse the results, whereas the web service and console application are aimed to perform batch searches and evaluation.

We present the first attempt on implementing a highly theoretical polynomial-time approximation scheme (PTAS) with huge hidden constants, namely, the PTAS for Steiner tree in planar graphs by Borradaile, Klein, and Mathieu (SODA 2007, WADS 2007). Whereas this result, and several other PTAS results of the recent years, are of high theoretical importance, no practical applications or even implementation attempts have been known to date, due to the extremely large constants that are involved in them. We describe techniques on how to circumvent the challenges in implementing such a scheme. Our main contribution is the engineering of several details of the original algorithm to make it work in practice. With today's limitations on processing power and space, we still have to sacrifice approximation guarantees for improved running times by choosing some parameters empirically. But our experiments show that with our choice of parameters, we do get the desired approximation ratios, suggesting that a much tighter analysis might be possible. Hence, we show that it is possible to actually implement and run this algorithm, even on large instances, already today - but under some compromises. Further improvements, both in theory and practice, might make these great theoretical works finally bear practical fruits in the future. First computational experiments with benchmark instances from SteinLib and large artificial instances well exceeded our own expectations. We demonstrate that we are able to handle instances with up to a million nodes and several hundreds of terminals in 1.5 hours on a standard PC. On the rectilinear preprocessed instances from SteinLib, we observe a monotonous improvement for smaller values of ∊, with an average gap below 1% for ∊ = 0.1. We compare our implementation against the well-known batched 1-Steiner heuristic and observe that on very large instances, we are able to produce comparable solutions much faster.

Article Improving the surface cycle structure for hexahedral mesh generation Share on Author: Matthias Müller-Hannemann Technische Universität Berlin, Department of Mathematics, MA 6-1, Straβe des 17. Juni 136, 10623 Berlin, Germany Technische Universität Berlin, Department of Mathematics, MA 6-1, Straβe des 17. Juni 136, 10623 Berlin, GermanyView Profile Authors Info & Claims SCG '00: Proceedings of the sixteenth annual symposium on Computational geometryMay 2000 Pages 19–28https://doi.org/10.1145/336154.336167Online:01 May 2000Publication History 3citation373DownloadsMetricsTotal Citations3Total Downloads373Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The computer--aided solution to algorithmic problems is becoming more and more important in various application domains.This is in particular true for computational geometry.For example, geometric problems naturally arise in image processing, computer graphics, and all kinds of computer-aided design, just to mention a few.Even more, the general tendency towards the application of visual aids in virtually all fields of science, technology, and business raises many new, unexpected geometric challenges.A sound mathematical treatment of these problems and a systematic computational study on the resulting algorithms are desirable.However, in practice, there are often obstacles to such an attempt.In this paper, we will systematically discuss our experiences with a few obstacles that occurred in four of our projects and significantly influenced our reasoning on algorithms in each of them.

We presenta linear-time afgorithmthatdecomposesa convex polygon conformablyinto a minimum numberof strictly convex quadrilaterals.Morezwer, wecharacterize thepolygons that cm be decomposed without additional vertices inside the polygon, and we presentalinear-time algorithtnforsuch decompositions, too.As an application, we consider theproblem of constructinga minimum conformal refinement of a mesh in the three-dimensional space, which approximates the surface of a workpiece.It turns out that this problem is AfP-hard, and we presenta linear-timealgorithm with a constantapproximationratio of 4. Conformal decompositionsof polygons. Conformalquadrangu-Iationsof polygons is a fundamentalproblem and has applications in finiteelement methods, watchguardproblems, and scattereddata interpolation.See [Tou95] for a survey of this topic and its applications.

We investigate a problem arising in the computer-aided design of cars, planes, ships, trains, and other motor vehicles and machines: refine a mesh of curved polygons, which approximates the surface of a workpiece, into quadrilaterals so that the resulting mesh is suitable for a numerical analysis. This mesh refinement problem turns out to be strongly NP -hard In commercial CAD systems, this problem is usually solved using a gree dy approach. However, these algorithms leave the user a lot of patchwork to do afterwards. We introduce a new global approach, which is based on network flow techniques. Abstracting from all geometric and numerical aspects, we obtain an undirected graph with upper and lower capacities on the edges and some additional node constraints. We reduce this problem to a sequence of bidirected flwo problems (or, equivalently, to b -matching problems). For the first time, network flow techniques are applied to a mesh refinement problem. This approach avoids the local traps of greedy approaches and yields solutions that require significantly less additional patchwork.