Search

There are several problems in the theory of online computation where tight lower bounds on the competitive ratio are unknown and expected to be difficult to describe in a short form. A good example is the Online Bin Stretching problem, in which the task is to pack the incoming items online into bins while minimizing the load of the largest bin. Additionally, the optimal load of the entire instance is known in advance. The contribution of this paper is twofold. We use the Coq proof assistant to formalize the Online Bin Stretching problem and provide a program certifying lower bounds of this problem. Because of the size of the certificates, previously claimed lower bounds were never formally proven. To the best of our knowledge, this is the first use of a formal verification toolkit to certify a lower bound for an online problem. We also provide the first non-trivial lower bounds for Online Bin Stretching with 6, 7 and 8 bins, and increase the best known lower bound for 3 bins. We describe in detail the algorithmic improvements which were necessary for the discovery of the new lower bounds, which are several orders of magnitude more complex. [ABSTRACT FROM AUTHOR]

Nuclear accumulation of the small phosphoprotein integrin cytoplasmic domain-associated protein-1 (ICAP1) results in recruitment of its binding partner, Krev/Rap1 interaction trapped-1 (KRIT1), to the nucleus. KRIT1 loss is the most common cause of cerebral cavernous malformation, a neurovascular dysplasia resulting in dilated, thin-walled vessels that tend to rupture, increasing the risk for hemorrhagic stroke. KRIT1's nuclear roles are unknown, but it is known to function as a scaffolding or adaptor protein at cell-cell junctions and in the cytosol, supporting normal blood vessel integrity and development. As ICAP1 controls KRIT1 subcellular localization, presumably influencing KRIT1 function, in this work, we investigated the signals that regulate ICAP1 and, hence, KRIT1 nuclear localization. ICAP1 contains a nuclear localization signal within an unstructured, N-terminal region that is rich in serine and threonine residues, several of which are reportedly phosphorylated. Using quantitative microscopy, we revealed that phosphorylation-mimicking substitutions at Ser-10, or to a lesser extent at Ser-25, within this N-terminal region inhibit ICAP1 nuclear accumulation. Conversely, phosphorylation-blocking substitutions at these sites enhanced ICAP1 nuclear accumulation. We further demonstrate that p21-activated kinase 4 (PAK4) can phosphorylate ICAP1 at Ser-10 both in vitro and in cultured cells and that active PAK4 inhibits ICAP1 nuclear accumulation in a Ser-10-dependent manner. Finally, we show that ICAP1 phosphorylation controls nuclear localization of the ICAP1-KRIT1 complex. We conclude that serine phosphorylation within the ICAP1 N-terminal region can prevent nuclear ICAP1 accumulation, providing a mechanism that regulates KRIT1 localization and signaling, potentially influencing vascular development. [ABSTRACT FROM AUTHOR]

Abstract Scientific workflows are frequently modeled as Directed Acyclic Graphs (DAGs) of tasks, which represent computational modules and their dependences in the form of data produced by a task and used by another one. This formulation allows the use of runtime systems which dynamically allocate tasks onto the resources of increasingly complex computing platforms. However, for some workflows, such a dynamic schedule may run out of memory by processing too many tasks simultaneously. This paper focuses on the problem of transforming such a DAG to prevent memory shortage, and concentrates on shared memory platforms. We first propose a simple model of DAGs which is expressive enough to emulate complex memory behaviors. We then exhibit a polynomial-time algorithm that computes the maximum peak memory of a DAG, that is, the maximum memory needed by any parallel schedule. We consider the problem of reducing this maximum peak memory to make it smaller than a given bound. Our solution consists in adding new fictitious edges, while trying to minimize the critical path of the graph. After proving that this problem is NP-complete, we provide an ILP solution as well as several heuristic strategies that are thoroughly compared by simulation on synthetic DAGs modeling actual computational workflows. We show that on most instances we are able to decrease the maximum peak memory at the cost of a small increase in the critical path, thus with little impact on the quality of the final parallel schedule. Highlights • Minimization of the memory footprint of task graphs representing computational workflows. • Adding fictitious edges that represent "memory dependences" prevents the scheduler from running out of memory. • Algorithm to compute the maximal peak memory of any graph. • The best heuristics either never fail or are able to limit the memory footprint with limited impact on the parallel makespan. [ABSTRACT FROM AUTHOR]

Tomographic diffractive microscopy allows for imaging unlabeled specimens, with a better resolution than conventional microscopes, giving access to the index of refraction distribution within the specimen, and possibly at high speed. Principles of image formation and reconstruction are presented, and progresses towards real-time, three-dimensional acquisition, image reconstruction and final display, are discussed. [ABSTRACT FROM AUTHOR]

Scientific workloads are often described by Directed Acyclic task Graphs. Indeed, DAGs represent both a theoretical model and the structure employed by dynamic runtime schedulers to handle HPC applications. A natural problem is then to compute a makespan-minimizing schedule of a given graph. In this paper, we are motivated by task graphs arising from multifrontal factorizations of sparse matrices and therefore work under the following practical model. Tasks are malleable (i.e., a single task can be allotted a time-varying number of processors) and their speedup behaves perfectly up to a first threshold, then speedup increases linearly, but not perfectly, up to a second threshold where the speedup levels off and remains constant. After proving the NP-hardness of minimizing the makespan of DAGs under this model, we study several heuristics. We propose model-optimized variants for PropScheduling, widely used in linear algebra application scheduling, and FlowFlex. GreedyFilling is proposed, a novel heuristic designed for our speedup model, and we demonstrate that PropScheduling and GreedyFilling are 2-approximation algorithms. In the evaluation, employing synthetic data sets and task graphs arising from multifrontal factorization, the proposed optimized variants and GreedyFilling significantly outperform the traditional algorithms, whereby GreedyFilling demonstrates a particular strength for balanced graphs. [ABSTRACT FROM AUTHOR]

Summary The regulation of many protein kinases by binding to calcium/calmodulin connects two principal mechanisms in signaling processes: protein phosphorylation and responses to dose- and time-dependent calcium signals. We used the calcium/calmodulin-dependent members of the death-associated protein kinase (DAPK) family to investigate the role of a basic DAPK signature loop near the kinase active site. In DAPK2, this loop comprises a novel dimerization-regulated calcium/calmodulin-binding site, in addition to a well-established calcium/calmodulin site in the C-terminal autoregulatory domain. Unexpectedly, impairment of the basic loop interaction site completely abolishes calcium/calmodulin binding and DAPK2 activity is reduced to a residual level, indicative of coupled binding to the two sites. This contrasts with the generally accepted view that kinase calcium/calmodulin interactions are autonomous of the kinase catalytic domain. Our data establish an intricate model of multi-step kinase activation and expand our understanding of how calcium binding connects with other mechanisms involved in kinase activity regulation. [ABSTRACT FROM AUTHOR]

Many human protein kinases are regulated by the calcium-sensor protein calmodulin, which binds to a short flexible segment C-terminal to the enzyme’s catalytic kinase domain. Our understanding of the molecular mechanism of kinase activity regulation by calcium/calmodulin has been advanced by the structures of two protein kinases—calmodulin kinase II and death-associated protein kinase 1—bound to calcium/calmodulin. Comparison of these two structures reveals a surprising level of diversity in the overall kinase—calcium/calmodulin arrangement and functional readout of activity, as well as complementary mechanisms of kinase regulation such as phosphorylation. [ABSTRACT FROM AUTHOR]

Within the large group of calcium/calmodulin-dependent protein kinases ( CAMKs) of the human kinome, there is a distinct branch of highly related kinases that includes three families: death-associated protein-related kinases, myosin light-chain-related kinases and triple functional domain protein-related kinases. In this review, we refer to these collectively as DMT kinases. There are several functional features that span the three families, such as a broad involvement in apoptotic processes, cytoskeletal association and cellular plasticity. Other CAMKs contain a highly conserved HRD motif, which is a prerequisite for kinase regulation through activation-loop phosphorylation, but in all 16 members of the DMT branch, this is replaced by an HF/ LD motif. This DMT kinase signature motif substitutes phosphorylation-dependent active-site interactions with a local hydrophobic core that maintains an active kinase conformation. Only about half of the DMT kinases have an additional autoregulatory domain, C-terminal to the kinase domain that binds calcium/calmodulin in order to regulate kinase activity. Protein substrates have been identified for some of the DMT kinases, but little is known about the mechanism of recognition. Substrate conformation could be an equally important parameter in substrate recognition as specific preferences in sequence position. Taking the data together, this kinase branch encapsulates a treasure trove of features that renders it distinct from many other protein kinases and calls for future research activities in this field. [ABSTRACT FROM AUTHOR]

Abstract: The resolution of fluorescence microscopes is limited by diffraction, which determines the extension of their point spread functions. We propose and study numerically a simple method, based on a combination of subtraction microscopy with regular and annular excitation beams, which permits to double the resolution compared to wide field microscopy. When combined with the fluorescence saturation phenomenon, this approach would be able to deliver a resolution of a few tens of nanometers. [Copyright &y& Elsevier]

Abstract: The confocal fluorescence microscope is the instrument of choice for biologists. However, compared to other instruments, its resolution is still limited. We propose a simple technique, based on laterally interfering beams, to improve the resolution. One technique consists in using a halve phase plate to modify the illumination, combined with a laterally offset detection. A 90nm lateral resolution is obtained for properly prepared specimens using readily available dyes. Another approach is to use several excitation beams, slightly shifted and properly dephased, to decrease the lateral extension of the PSF. With this approach, a lateral resolution of 75nm is predicted with the advantage of a regular confocal detection. Finally, we show how using these techniques in combination with a two-color two-photon excitation could permit to further improve the resolution to 60nm. [Copyright &y& Elsevier]

Scientific applications are usually described using directed acyclic graphs, where nodes represent tasks and edges represent dependencies between tasks. For some applications, this graph is a tree: each task produces a single result used solely by its parent. The temporary results of each task have to be stored between their production and their use. We focus on the case when the data manipulated are very large. Then, during an execution, all data may not fit together in memory. In such a case, some data have to be temporarily written to disk and evicted from memory. These data are later read from disk when they are needed for computation. These Input/Output operations are very expensive; hence, our goal is to minimize their total volume. The order in which the tasks are processed considerably influences the amount of such Input/Output operations. Finding the schedule which minimizes this amount is an open problem that we revisit in this paper. We first formalize and generalize known results, and prove that existing solutions can be arbitrarily worse than the optimal. We then present an Integer Linear Program to solve it optimally. Finally, we propose a novel heuristic algorithm. We demonstrate its good performance through simulations on both synthetic and realistic trees built from actual scientific applications. [ABSTRACT FROM AUTHOR]

Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}$ 4 m / k -competitive online algorithm by Amaris et al. , where $m$ m is the number of CPUs and $k$ k the number of GPUs ($m\geq k$ m ≥ k ). We prove that no online algorithm can have a competitive ratio smaller than $\sqrt{m/k}$ m / k . We also study how adding flexibility on task processing, such as task migration or spoliation, or increasing the knowledge of the scheduler by providing it with information on the task graph, influences the lower bound. We provide a $(2\sqrt{m/k}+1)$ (2 m / k + 1) -competitive algorithm as well as a tunable combination of a system-oriented heuristic and a competitive algorithm; this combination performs well in practice and has a competitive ratio in $\Theta (\sqrt{m/k})$ Θ (m / k) . We also adapt all our results to the case of multiple types of processors. Finally, simulations on different sets of task graphs illustrate how the instance properties impact the performance of the studied algorithms and show that our proposed tunable algorithm performs the best among the online algorithms in almost all cases and has even performance close to an offline algorithm. [ABSTRACT FROM AUTHOR]

Binding of ICAP1 (integrin cytoplasmic domain-associated protein-1) to the cytoplasmic tails ofβ1 integrins inhibits integrin activation. ICAP1 also binds to KRIT1 (Krev interaction trapped-1), a protein whose loss of function leads to cerebral cavernous malformation, a cerebrovascular dysplasia occurring in up to 0.5% of the population. We previously showed that KRIT1 functions as a switch forβ1 integrin activation by antagonizing ICAP1-mediated inhibition of integrin activation. Here we use overexpression studies, mutagenesis, and flow cytometry to show that ICAP1 contains a functional nuclear localization signal and that nuclear localization impairs the ability of ICAP1 to suppress integrin activation. Moreover, we find that ICAP1 drives the nuclear localization of KRIT1 in a manner dependent upon a direct ICAP1/KRIT1 interaction. Thus, nuclear-cytoplasmic shuttling of ICAP1 influences both integrin activation and KRIT1 localization, presumably impacting nuclear functions of KRIT1. [ABSTRACT FROM AUTHOR]

The speed-robust scheduling problem is a two-stage problem where, given m machines, jobs must be grouped into at most m bags while the processing speeds of the machines are unknown. After the speeds are revealed, the grouped jobs must be assigned to the machines without being separated. To evaluate the performance of algorithms, we determine upper bounds on the worst-case ratio of the algorithm's makespan and the optimal makespan given full information. We refer to this ratio as the robustness factor. We give an algorithm with a robustness factor 2 - 1 m for the most general setting and improve this to 1.8 for equal-size jobs. For the special case of infinitesimal jobs, we give an algorithm with an optimal robustness factor equal to e e - 1 ≈ 1.58 . The particular machine environment in which all machines have either speed 0 or 1 was studied before by Stein and Zhong (ACM Trans Algorithms 16(1):1-20, 2020. https://doi.org/10.1145/3340320). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of 1 + 2 2 ≈ 1.207 . It lays the foundation for an algorithm matching the lower bound of 4 3 for equal-size jobs. [ABSTRACT FROM AUTHOR]

The evolution in the design of modern parallel platforms leads to revisit the scheduling jobs on distributed heterogeneous resources. The goal of this survey is to present the main existing algorithms, to classify them based on their underlying principles, and to propose unified implementations to enable their fair comparison, in terms of running time and quality of schedules, on a large set of common benchmarks that we made available for the community. Beyond this comparison, our goal is also to understand the main difficulties that heterogeneity conveys and the shared principles that guide the design of efficient algorithms. [ABSTRACT FROM AUTHOR]

• Curved microdisplays improve visual systems for image quality and luminous flux. • Best curvature shape is spherical for on axis systems; biconic for off axis ones. • Mechanical simulations are validated and a better insight in given on the chip failure. • The curving yield depends on the aggressiveness of the shape. • No significant impact of the process used for chip preparation on the curving yield. Freeform optical designs deal with off-axis field curvature, which can be corrected by using curved microdisplays, with a biconic shape. In this work, we first show using simulations how curved microdisplays permit increasing image quality, but may also improve the distortion, the system's cumbersomeness and luminous flux in visual systems. Focusing on developing functional curved microdisplays, we therefore first designed a simulation process and then an experimental set-up to explore the mechanical limitations of silicon-based curved chips. The experimental results are compared to the simulation, allowing for more insight into realistic shapes for curved silicon dies. Tests were run for three different chip preparation processes, to evaluate their influence. [ABSTRACT FROM AUTHOR]

Summary: Knowledge about protein kinase substrate preferences is biased toward residues immediately adjacent to the site of phosphorylation. By a combined structural, biochemical, and cellular approach, we have discovered an unexpected substrate recognition element with the consensus sequence PEF/Y in the tumor suppressor death-associated protein kinase 1. This motif can be effectively blocked by a specific pseudosubstrate-type interaction with an autoregulatory domain of this kinase. In this arrangement, the central PEF/Y glutamate interacts with a conserved arginine distant to the phosphorylation site in sequence and structure. We also demonstrate that the element is crucial for kinase activity regulation and substrate recognition. The PEF/Y motif distinguishes close death-associated protein kinase relatives from canonical calcium/calmodulin-dependent protein kinases. Insight into this signature and mode of action offers new opportunities to identify specific small molecule inhibitors in PEF/Y-containing protein kinases. [Copyright &y& Elsevier]

A new procedure is described for the determination of Hg2+ ions in water samples. A Rhodamine based fluorescent sensor was synthesized and the experimental conditions were specifically optimized for application to environmental samples, which requires low detection limits and high selectivity in competitive experiments with realistic concentrations of other metal ions. Incorporation of a Rhodamine-6G fluorophore to a previously described sensor and optimization of the buffer system (detection with acetic acid at pH 5.25) enabled significant enhancement of the sensitivity (detection limit = 0.27 μg L−1) and selectivity. The optimized procedure using high-throughput microplates has been applied to tap and river waters with good results. Image 1 • Optimized rhodamine sensor and experimental conditions for Hg2+ detection. • Acetic acid buffer enables detection limit at nM level. • Selectivity over other metal ions has been proven with environmental concentrations. • Procedure applied and validated on real water samples (tap water and river samples). [ABSTRACT FROM AUTHOR]