MOTIVATION: The generation of high-quality assemblies, even for large eukaryotic genomes, has become a routine task for many biologists thanks to recent advances in sequencing technologies. However, the annotation of these assemblies-a crucial step toward unlocking the biology of the organism of interest-has remained a complex challenge that often requires advanced bioinformatics expertise. RESULTS: Here, we present MOSGA (Modular Open-Source Genome Annotator), a genome annotation framework for eukaryotic genomes with a user-friendly web-interface that generates and integrates annotations from various tools. The aggregated results can be analyzed with a fully integrated genome browser and are provided in a format ready for submission to NCBI. MOSGA is built on a portable, customizable and easily extendible Snakemake backend, and thus, can be tailored to a wide range of users and projects. AVAILABILITY AND IMPLEMENTATION: We provide MOSGA as a web service at https://mosga.mathematik.uni-marburg.de and as a docker container at registry.gitlab.com/mosga/mosga: latest. Source code can be found at https://gitlab.com/mosga/mosga. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Upper and lower bounds for the number of geometric graphs of specific types on a given set of points in the plane have been intensively studied in recent years. For most classes of geometric graphs it is now known that point sets in convex position minimize their number. However, it is still unclear which point sets minimize the number of geometric triangulations; the so-called double circles are conjectured to be the minimizing sets. In this paper we prove that any set of n points in general position in the plane has at least Omega(2.631^n) geometric triangulations. Our result improves the previously best general lower bound of Omega(2.43^n) and also covers the previously best lower bound of Omega(2.63^n) for a fixed number of extreme points. We achieve our bound by showing and combining several new results, which are of independent interest: (1) Adding a point on the second convex layer of a given point set (of 7 or more points) at least doubles the number of triangulations. (2) Generalized configurations of points that minimize the number of triangulations have at most n/2 points on their convex hull. (3) We provide tight lower bounds for the number of triangulations of point sets with up to 15 points. These bounds further support the double circle conjecture.

Let P = B ∪ R be a set of 2n points in general position, where B is a set of n blue points and R a set of n red points. A BR-matching is a plane geometric perfect matching on P such that each edge has one red endpoint and one blue endpoint. Two BR-matchings are compatible if their union is also plane.

MOTIVATION: Today, the base code of DNA is mostly determined through sequencing by synthesis as provided by the Illumina sequencers. Although highly accurate, resulting reads are short, making their analyses challenging. Recently, a new technology, single molecule real-time (SMRT) sequencing, was developed that could address these challenges, as it generates reads of several thousand bases. But, their broad application has been hampered by a high error rate. Therefore, hybrid approaches that use high-quality short reads to correct erroneous SMRT long reads have been developed. Still, current implementations have great demands on hardware, work only in well-defined computing infrastructures and reject a substantial amount of reads. This limits their usability considerably, especially in the case of large sequencing projects. RESULTS: Here we present proovread, a hybrid correction pipeline for SMRT reads, which can be flexibly adapted on existing hardware and infrastructure from a laptop to a high-performance computing cluster. On genomic and transcriptomic test cases covering Escherichia coli, Arabidopsis thaliana and human, proovread achieved accuracies up to 99.9% and outperformed the existing hybrid correction programs. Furthermore, proovread-corrected sequences were longer and the throughput was higher. Thus, proovread combines the most accurate correction results with an excellent adaptability to the available hardware. It will therefore increase the applicability and value of SMRT sequencing. AVAILABILITY AND IMPLEMENTATION: proovread is available at the following URL: http://proovread.bioapps.biozentrum.uni-wuerzburg.de.

Given a set B of n black points in general position, we say that a set of white points W blocks B if in the Delaunay triangulation of B ∪ W there is no edge connecting two black points. We give the following bounds for the size of the smallest set W blocking B : (i) 3 n / 2 white points are always sufficient to block a set of n black points, (ii) if B is in convex position, 5 n / 4 white points are always sufficient to block it, and (iii) at least n − 1 white points are always necessary to block a set of n black points.

We have built an autonomous robot, out of standard components, and combined it with optimal game winning strategies. This results in an artificial companion which plays the board game Pylos in a fully interactive manner and up to the highest possible level.

We consider a variation of a problem stated by Erdős and Szekeres in 1935 about the existence of a number $f^{\mathrm{ES}}(k)$ such that any set S of at least $f^{\mathrm{ES}}(k)$ points in general position in the plane has a subset of k points that are the vertices of a convex k-gon. In our setting the points of S are colored, and we say that a (not necessarily convex) spanned polygon is monochromatic if all its vertices have the same color. Moreover, a polygon is called empty if it does not contain any points of S in its interior. We show that any sufficiently large bichromatic set of points in $\mathbb{R}^2$ in general position determines at least one empty, monochromatic quadrilateral (and thus linearly many).

We show how to divide the edge graph of a Voronoi diagram into a tree that corresponds to the medial axis of an (augmented) planar domain. Division into base cases is then possible, which, in the bottom-up phase, can be merged by trivial concatenation. The resulting construction algorithm--similar to Delaunay triangulation methods--is not bisector-based and merely computes dual links between the sites, its atomic steps being inclusion tests for sites in circles. This guarantees computational simplicity and numerical stability. Moreover, no part of the Voronoi diagram, once constructed, has to be discarded again. The algorithm works for polygonal and curved objects as sites and, in particular, for circular arcs which allows its extension to general free-form objects by Voronoi diagram preserving and data saving biarc approximations. The algorithm is randomized, with expected runtime O(n log n) under certain assumptions on the input data. Experiments substantiate an efficient behavior even when these assumptions are not met. Applications to offset computations and motion planning for general objects are described.

We introduce and discuss the concept of pre-triangulations, a relaxation of triangulations that goes beyond the well-established class of pseudo-triangulations.