162 research outputs found
String Problems in the Congested Clique Model
Get PDFIn this paper we present algorithms for several string problems in the Congested Clique model. In the Congested Clique model, n nodes (computers) are used to solve some problem. The input to the problem is distributed among the nodes, and the communication between the nodes is conducted in rounds. In each round, every node is allowed to send an O(log n)-bit message to every other node in the network.
We consider three fundamental string problems in the Congested Clique model. First, we present an O(1) rounds algorithm for string sorting that supports strings of arbitrary length. Second, we present an O(1) rounds combinatorial pattern matching algorithm. Finally, we present an O(log log n) rounds algorithm for the computation of the suffix array and the corresponding Longest Common Prefix array of a given string
Hairpin Completion Distance Lower Bound
Get PDFHairpin completion, derived from the hairpin formation observed in DNA biochemistry, is an operation applied to strings, particularly useful in DNA computing. Conceptually, a right hairpin completion operation transforms a string S into S⋅ S' where S' is the reverse complement of a prefix of S. Similarly, a left hairpin completion operation transforms a string S into S'⋅ S where S' is the reverse complement of a suffix of S. The hairpin completion distance from S to T is the minimum number of hairpin completion operations needed to transform S into T. Recently Boneh et al. [Itai Boneh et al., 2023] showed an O(n²) time algorithm for finding the hairpin completion distance between two strings of length at most n. In this paper we show that for any ε > 0 there is no O(n^{2-ε})-time algorithm for the hairpin completion distance problem unless the Strong Exponential Time Hypothesis (SETH) is false. Thus, under SETH, the time complexity of the hairpin completion distance problem is quadratic, up to sub-polynomial factors
Time-Space Tradeoffs for Finding a Long Common Substring
Get PDFWe consider the problem of finding, given two documents of total length n, a longest string occurring as a substring of both documents. This problem, known as the Longest Common Substring (LCS) problem, has a classic (n)-time solution dating back to the discovery of suffix trees (Weiner, 1973) and their efficient construction for integer alphabets (Farach-Colton, 1997). However, these solutions require Θ(n) space, which is prohibitive in many applications. To address this issue, Starikovskaya and Vildhøj (CPM 2013) showed that for n^{2/3} ≤ s ≤ n, the LCS problem can be solved in (s) space and ̃(n²/s) time. Kociumaka et al. (ESA 2014) generalized this tradeoff to 1 ≤ s ≤ n, thus providing a smooth time-space tradeoff from constant to linear space. In this paper, we obtain a significant speed-up for instances where the length L of the sought LCS is large. For 1 ≤ s ≤ n, we show that the LCS problem can be solved in (s) space and ̃(n²/(L⋅s) +n) time. The result is based on techniques originating from the LCS with Mismatches problem (Flouri et al., 2015; Charalampopoulos et al., CPM 2018), on space-efficient locally consistent parsing (Birenzwige et al., SODA 2020), and on the structure of maximal repetitions (runs) in the input documents
Searching 2D-Strings for Matching Frames
Get PDFWe study a natural type of repetitions in 2-dimensional strings. Such a repetition, called a matching frame, is a rectangular substring of size at least 2× 2 with equal marginal rows and equal marginal columns. Matching frames first appeared in literature in the context of Wang tiles.
We present two algorithms finding a matching frame with the maximum perimeter in a given n× m input string. The first algorithm solves the problem exactly in Õ(n^{2.5}) time (assuming n ≥ m). The second algorithm finds a (1-ε)-approximate solution in Õ((nm)/ε⁴) time, which is near linear in the size of the input for constant ε. In particular, by setting ε = O(1) the second algorithm decides the existence of a matching frame in a given string in Õ(nm) time. Some technical elements and structural properties used in these algorithms can be of independent interest
An Entropic Estimator for Linear Inverse Problems
No full textIn this paper we examine an Information-Theoretic method for solving noisy linear inverse estimation<em> </em>problems which encompasses under a single framework a whole class of estimation methods. Under this framework, the prior information about the unknown parameters (when such information exists), and constraints on the parameters can be incorporated in the statement of the problem. The method builds on the basics of the maximum entropy principle and consists of transforming the original problem into an estimation of a probability density on an appropriate space naturally associated with the statement of the problem. This estimation method is generic in the sense that it provides a framework for analyzing non-normal models, it is easy to implement and is suitable for all types of inverse problems such as small and or ill-conditioned, noisy data. First order approximation, large sample properties and convergence in distribution are developed as well. Analytical examples, statistics for model comparisons and evaluations, that are inherent to this method, are discussed and complemented with explicit examples
Toolbox: Creating a systematic database of secretory pathway proteins uncovers new cargo for COPI.
Get PDFA third of yeast genes encode for proteins that function in the endomembrane system. However, the precise localization for many of these proteins is still uncertain. Here, we visualized a collection of ~500 N-terminally, green fluorescent protein (GFP), tagged proteins of the yeast Saccharomyces cerevisiae. By co-localizing them with seven known markers of endomembrane compartments we determined the localization for over 200 of them. Using this approach, we create a systematic database of the various secretory compartments and identify several new residents. Focusing in, we now suggest that Lam5 resides in contact sites between the Endoplasmic Reticulum and the late Golgi. Additionally, analysis of interactions between the COPI coat and co-localizing proteins from our screen identifies a subset of proteins that are COPI-cargo. In summary, our approach defines the protein roster within each compartment enabling characterization of the physical and functional organization of the endomembrane system and its components
Golan Haji, L'autunno, qui, è magico e immenso (raccolta poetica siriana)
No full textItalian translation of a poetry collection by Kurdish-Syrian poet Golan Haji. The author composed these prose poems in different moments of his literary career: some before the peaceful uprising that started in Syria on March 15, 2011, and was soon defaced by a fierce civil war; and the other ones between 2012 and 2013. The Italian translation is side by side the original Arabic texts
Legal Aspects of International Security in the Near East with Focus on the Golan Heights
No full textTato práce se zabývá právními aspekty mezinárodní bezpečnosti na Blízkém východě a zaměřuje se na Golanské výšiny. Cílem práce je posouzení míry vlivu mezinárodních organizací na dosažení mezinárodní bezpečnosti na Blízkém východě. Autor vychází z analýzy dostupných textů v českém jazyce i z cizojazyčné literatury. Práce sestává ze čtyř kapitol, z nichž první se zabývá otázkou mezinárodní bezpečnosti na Blízkém východě. Druhá kapitola se soustřeďuje na problematiku spojenou s Golanskými výšinami v souvislosti s bezpečnostní situací zejména po roce 1967. Třetí kapitola pojednává o roli mezinárodních organizací při zajišťování míru a bezpečnosti na Blízkém východě. Poslední kapitola sleduje mírový proces na Blízkém východě a nastiňuje perspektivy řešení blízkovýchodního konfliktu.Katedra mezinárodního právaObhájenoThe thesis looks into the issue of legal aspects of international security in the Near East with focus on the Golan Heights. The aim of the thesis is to shed light on the success/ failure of international organizations in securing and maintaining peace and international security in the Near East.The author analyses both Czech and foreign texts dealing with the topic. The thesis consists of four chapters. The first chapter examines the issue of international security in the Near East. The second chapter focuses on the situation in the Golan Heights mainly after 1967. The third chapter looks at the role played by international organizations in maintaining peace and security in the Near East. The last chapter presents the main events of the peace process in the Near East and outlines the prospects of the resolution of the Near Eastern conflict
A novel model for development, organization and function of gonadotropes in fish pituitary
No full textThe gonadotropins follicle-stimulating hormone (FSH) and luteinizing hormone (LH) are key regulators of the reproductive axis in vertebrates. Despite the high popularity of zebrafish as a model organism for studying reproductive functions, to date no transgenic zebrafish with labeled gonadotropes have been introduced. Using gonadotropin regulatory elements from tilapia, we generated two transgenic zebrafish lines with labeled gonadotropes. The tilapia and zebrafish regulatory sequences were highly divergent but several conserved elements allowed the tilapia promoters to correctly drive the transgenes in zebrafish pituitaries. FSH cells reacted to stimulation with GnRH by proliferating and showing increased transgene fluorescence, whereas estrogen exposure caused a decrease in cell number and transgene fluorescence. Transgene fluorescence reflected the expression pattern of the endogenous fshb gene. Ontogenetic expression of the transgenes followed typical patterns, with FSH cells appearing early in development, and LH cells appearing later and increasing dramatically in number with the onset of puberty. Our transgenic lines provide a powerful tool for investigating the development, anatomy and function of the reproductive axis in lower vertebrates
Israeli Education Policies as a Tool for the Ethnic Manipulation of the Arab Druze: Israel and the Occupied Syrian Golan
No full textThis thesis investigates decisions and processes of ethnic manipulation within the educationsystem in Israel using archival documents, textbooks, and interviews to guide its arguments. The paper studies taught in Druze schools in Israel and the Occupied Syrian Golan OSG, documents interviews of Druze teachers and activists, and compares Israel's educational policies with international laws. Next, it examines the particular conditions of the Syrians in the Golan as an occupied people in the proximity of the Syrian civil war. The author argues that the state of Israel employs tactics of minoritization and ethnic manipulation against its Arab Druze communities in the OSG and Israel proper in order to maintain its ethnocratic regime. Institutionalized efforts of manipulation include the separation of Druze from the Arab school system, the construction of separate Druze holidays, and mandatory conscription to the Israeli army. Through these tactics, Israel has misappropriated Druze agency, undermined their identity, and manipulated their ethnic heritage. Within the education system, Israel's policies have created a Druze community that is uninformed about its history, disconnected from its culture, and confused about its identity. While Syrians in the Golan do not serve in the Israeli army, the effects of identity suppression have been magnified in the region due to the Syrian civil war and the consequent closure of their (limited) access to Syria. International law requires Israel, as a signatory to several covenants and partner in multiple treaties, to provide an education that preserves and promotes the culture and history of ethnic minorities—especially peoples in occupied territories. This includes an accurate representation of the borders of the State, inclusion of notable Arab Druze historical figures, and an education about their Arab culture and heritage. Finally, this thesis argues that while several international covenants and treaties are relevant to the acceptable cultural and historical representation for minorities and indigenous groups, the need to specify what that means remains. Adding General Comments and having the Special Rapporteur on Education visit Israel, combined with increased pressure from non-governmental organizations, would ultimately increase the state's accountability for and adherence to those conventions
- …
