Rapid preconditioning of data for accelerating convex hull algorithms

Given a dataset of two-dimensional points in the plane with integer coordinates, the method proposed reduces a set of n points down to a set of s points s ≤ n, such that the convex hull on the set of s points is the same as the convex hull of the original set of n points. The method is O(n). It helps any convex hull algorithm run faster. The empirical analysis of a practical case shows a percentage reduction in points of over 98%, that is reflected as a faster computation with a speedup factor of at least 4.

Preconditioning 2D integer data for fast convex hull computations

In order to accelerate computing the convex hull on a set of n points, a heuristic procedure is often applied to reduce the number of points to a set of s points, s ≤ n, which also contains the same hull. We present an algorithm to precondition 2D data with integer coordinates bounded by a box of size p × q before building a 2D convex hull, with three distinct advantages. First, we prove that under the condition min(p, q) ≤ n the algorithm executes in time within O(n); second, no explicit sorting of data is required; and third, the reduced set of s points forms a simple polygonal chain and thus can be directly pipelined into an O(n) time convex hull algorithm. This paper empirically evaluates and quantifies the speed up gained by preconditioning a set of points by a method based on the proposed algorithm before using common convex hull algorithms to build the final hull. A speedup factor of at least four is consistently found from experiments on various datasets when the condition min(p, q) ≤ n holds; the smaller the ratio min(p, q)/n is in the dataset, the greater the speedup factor achieved.

Identification and validation of candidate genes associated with domesticated and improved traits in soybean

Soybean, an important source of vegetable oils and proteins for humans, has undergone significant phenotypic changes during domestication and improvement. However, there is limited knowledge about genes related to these domesticated and improved traits, such as flowering time, seed development, alkaline-salt tolerance, and seed oil content (SOC). In this study, more than 106,000 single nucleotide polymorphisms (SNPs) were identified by restriction site associated DNA sequencing of 14 wild, 153 landrace, and 119 bred soybean accessions, and 198 candidate domestication regions (CDRs) were identified via multiple genetic diversity analyses. Of the 1489 candidate domestication genes (CDGs) within these CDRs, a total of 330 CDGs were related to the above four traits in the domestication, gene ontology (GO) enrichment, gene expression, and pathway analyses. Eighteen, 60, 66, and 10 of the 330 CDGs were significantly associated with the above four traits, respectively. Of 134 traitassociated CDGs, 29 overlapped with previous CDGs, 11 were consistent with candidate genes in previous trait association studies, and 66 were covered by the domesticated and improved quantitative trait loci or their adjacent regions, having six common CDGs, such as one functionally characterized gene Glyma15 g17480 (GmZTL3). Of the 68 seed size (SS) and SOC CDGs, 37 were further confirmed by gene expression analysis. In addition, eight genes were found to be related to artificial selection during modern breeding. Therefore, this study provides an integrated method for efficiently identifying CDGs and valuable information for domestication and genetic research.