BACKGROUND: For single-cell or metagenomic sequencing projects, it is necessary to sequence with a very high mean coverage in order to make sure that all parts of the sample DNA get covered by the reads produced. This leads to huge datasets with lots of redundant data. A filtering of this data prior to assembly is advisable. Brown et al. (2012) presented the algorithm Diginorm for this purpose, which filters reads based on the abundance of their k-mers. METHODS: We present Bignorm, a faster and quality-conscious read filtering algorithm. An important new algorithmic feature is the use of phred quality scores together with a detailed analysis of the k-mer counts to decide which reads to keep. RESULTS: We qualify and recommend parameters for our new read filtering algorithm. Guided by these parameters, we remove in terms of median 97.15% of the reads while keeping the mean phred score of the filtered dataset high. Using the SDAdes assembler, we produce assemblies of high quality from these filtered datasets in a fraction of the time needed for an assembly from the datasets filtered with Diginorm. CONCLUSIONS: We conclude that read filtering is a practical and efficient method for reducing read data and for speeding up the assembly process. This applies not only for single cell assembly, as shown in this paper, but also to other projects with high mean coverage datasets like metagenomic sequencing projects. Our Bignorm algorithm allows assemblies of competitive quality in comparison to Diginorm, while being much faster. Bignorm is available for download at https://git.informatik.uni-kiel.de/axw/Bignorm .

Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given an instance (I,k) of some (parameterized) problem Π with a guarantee g(I), decide whether I admits a solution of size at least (at most) k+g(I). Here, g(I) is usually a lower bound (resp. upper bound) on the maximum (resp. minimum) size of a solution. Since its introduction in 1999 for Max SAT and Max Cut (with g(I) being half the number of clauses and half the number of edges, respectively, in the input), analysis of parameterization above a guarantee has become a very active and fruitful topic of research. We highlight a multiplicative form of parameterization above a guarantee: Given an instance (I,k) of some (parameterized) problem Π with a guarantee g(I), decide whether I admits a solution of size at least (resp. at most) k ⋅ g(I). In particular, we study the Long Cycle problem with a multiplicative parameterization above the girth g(I) of the input graph, and provide a parameterized algorithm for this problem. Apart from being of independent interest, this exemplifies how parameterization above a multiplicative guarantee can arise naturally. We also show that, for any fixed constant ε>0, multiplicative parameterization above g(I)^(1+ε) of Long Cycle yields para-NP-hardness, thus our parameterization is tight in this sense. We complement our main result with the design (or refutation of the existence) of algorithms for other problems parameterized multiplicatively above girth.

Abstract We present an extension to nonatomic congestion games (NCG). An NCG models a large number of players depending on a set of resources (e.g., network links) in certain combinations (e.g., paths or multicast trees) called strategies. The rate of consumption ZeS specifies how aggressively resource e is consumed when used via strategy S, but it also effects how strongly the resource's latency is experienced by the players. Our extension allows essentially unrelated factors CeS and ReS instead of ZeS. Factor CeS is the actual rate of consumption, whereas ReS expresses the amplification of the resource latency of e for players choosing strategy S, or, in other words, the relevance of resource e for strategy S. We call the extended model nonatomic consumption‐relevance congestion games (NCRCG). NCRCGs exhibit new phenomena, including multiple Nash equilibria of different social cost and—even from a worst‐case point of view—a dependence of the price of anarchy on structural parameters not limited to the class of resource latency functions used. We prove almost tight lower, upper, and bicriteria bounds for the price of anarchy for polynomial latency functions with nonnegative coefficients. We conjecture that the lower bound is the best possible. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013

We present a model for distributed network formation with cost expressing robustness in an adversary model. There are n players, each representing a vertex. Players may establish links to other players, building a link incurs a cost α. Individual cost comprises this building cost plus an indirect cost. After the network is built, an adversary deletes one link. The adversary is modeled by a random experiment, specified by a probability distribution on the links. Players know this distribution. Indirect cost for player v is the expected number of players to which v will become disconnected when the adversary strikes. We can prove an O(1) bound on the price of anarchy for two different adversaries under unilateral link formation. Under bilateral link formation, we can prove an O(1+√n/α) bound for one adversary, and for the other an asymptotically tight Ω(n) bound if α = Θ(1).