Search

Richomme, Saari and Zamboni (J. Lond. Math. Soc. 83: 79-95, 2011) proved that at every position of a Sturmian word starts an abelian power of exponent $k$ for every $k > 0$. We improve on this result by studying the maximum exponents of abelian powers and abelian repetitions (an abelian repetition is an analogue of a fractional power) in Sturmian words. We give a formula for computing the maximum exponent of an abelian power of abelian period $m$ starting at a given position in any Sturmian word of rotation angle $\alpha$. vAs an analogue of the critical exponent, we introduce the abelian critical exponent $A(s_\alpha)$ of a Sturmian word $s_\alpha$ of angle $\alpha$ as the quantity $A(s_\alpha) = limsup\ k_{m}/m=limsup\ k'_{m}/m$, where $k_{m}$ (resp. $k'_{m}$) denotes the maximum exponent of an abelian power (resp.~of an abelian repetition) of abelian period $m$ (the superior limits coincide for Sturmian words). We show that $A(s_\alpha)$ equals the Lagrange constant of the number $\alpha$. This yields a formula for computing $A(s_\alpha)$ in terms of the partial quotients of the continued fraction expansion of $\alpha$. Using this formula, we prove that $A(s_\alpha) \geq \sqrt{5}$ and that the equality holds for the Fibonacci word. We further prove that $A(s_\alpha)$ is finite if and only if $\alpha$ has bounded partial quotients, that is, if and only if $s_{\alpha}$ is $\beta$-power-free for some real number $\beta$. Concerning the infinite Fibonacci word, we prove that: i) The longest prefix that is an abelian repetition of period $F_j$, $j>1$, has length $F_j( F_{j+1}+F_{j-1} +1)-2$ if $j$ is even or $F_j( F_{j+1}+F_{j-1} )-2$ if $j$ is odd, where $F_{j}$ is the $j$th Fibonacci number; ii) The minimum abelian period of any factor is a Fibonacci number. Further, we derive a formula for the minimum abelian periods of the finite Fibonacci words, Comment: To appear in Theoretical Computer Science

In this paper we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple $O(\sigma~ n^2)$ time algorithm, where $n$ is the length of the strings and $\sigma$ is the alphabet size, and a sub-quadratic running time solution for the binary string case, both having linear space requirement. Furthermore, we present a modified algorithm applying some interesting tricks and experimentally show that the resulting algorithm runs faster., Comment: 13 pages, 4 figures

The genetic treatment of neurodegenerative diseases still remains a challenging task since many approaches fail to deliver the therapeutic material in relevant concentrations into the brain. As viral vectors comprise the risk of immune and inflammatory responses, human serum albumin (HSA) nanoparticles were found to represent a safer and more convenient alternative. Their ability to cross the blood-brain barrier (BBB) and deliver drugs into the brain in order to enhance gene-based therapy has been previously demonstrated. The present study deals with the development of pGL3-PEI-coated HSA nanoparticles and subsequent in vitro testing in cerebellar granular and HeLa cells. The luciferase control vector pGL3 was chosen as reporter plasmid encoding for the firefly luciferase protein, linear polyethylenimine (22 kDa) as endosomolytic agent for enhancing the cells’ transfection. Studies on particle characteristics, their cellular uptake into aforementioned cell lines and on subcellular localisation, and transfection efficiency in the cerebellar cells proved the feasibility of nanoparticle-based gene delivery.

Neuronal ceroid lipofuscinosis (NCL) is a group of neurodegenerative lysosomal storage disorders characterized by vision loss, mental and motor deficits, and spontaneous seizures. Neuropathological analyses of autopsy material from NCL patients and animal models revealed brain atrophy closely associated with glial activity. Earlier reports also noticed loss of retinal cells and reactive gliosis in some forms of NCL. To study this phenomenon in detail, we analyzed the ocular phenotype of CLN6(nclf) mice, an established mouse model for variant-late infantile NCL. Retinal morphometry, immunohistochemistry, optokinetic tracking, electroretinography, and mRNA expression were used to characterize retinal morphology and function as well as the responses of Muller cells and microglia. Our histological data showed a severe and progressive degeneration in the CLN6(nclf) retina co-inciding with reactive Muller glia. Furthermore, a prominent phenotypic transformation of ramified microglia to phagocytic, bloated, and mislocalized microglial cells was identified in CLN6(nclf) retinas. These events overlapped with a rapid loss of visual perception and retinal function. Based on the strong microglia reactivity we hypothesized that dietary supplementation with immuno-regulatory compounds, curcumin and docosahexaenoic acid (DHA), could ameliorate microgliosis and reduce retinal degeneration. Our analyses showed that treatment of three-week-old CLN6(nclf) mice with either 5% DHA or 0.6% curcumin for 30 weeks resulted in a reduced number of amoeboid reactive microglia and partially improved retinal function. DHA-treatment also improved the morphology of CLN6(nclf) retinas with a preserved thickness of the photoreceptor layer in most regions of the retina. Our results suggest that microglial reactivity closely accompanies disease progression in the CLN6(nclf) retina and both processes can be attenuated with dietary supplemented immuno-modulating compounds.

Neuronal ceroid lipofuscinosis (NCL) is a group of neurodegenerative lysosomal storage disorders characterized by vision loss, mental and motor deficits, and spontaneous seizures. Neuropathological analyses of autopsy material from NCL patients and animal models revealed brain atrophy closely associated with glial activity. Earlier reports also noticed loss of retinal cells and reactive gliosis in some forms of NCL. To study this phenomenon in detail, we analyzed the ocular phenotype of CLN6(nclf) mice, an established mouse model for variant-late infantile NCL. Retinal morphometry, immunohistochemistry, optokinetic tracking, electroretinography, and mRNA expression were used to characterize retinal morphology and function as well as the responses of Muller cells and microglia. Our histological data showed a severe and progressive degeneration in the CLN6(nclf) retina co-inciding with reactive Muller glia. Furthermore, a prominent phenotypic transformation of ramified microglia to phagocytic, bloated, and mislocalized microglial cells was identified in CLN6(nclf) retinas. These events overlapped with a rapid loss of visual perception and retinal function. Based on the strong microglia reactivity we hypothesized that dietary supplementation with immuno-regulatory compounds, curcumin and docosahexaenoic acid (DHA), could ameliorate microgliosis and reduce retinal degeneration. Our analyses showed that treatment of three-week-old CLN6(nclf) mice with either 5% DHA or 0.6% curcumin for 30 weeks resulted in a reduced number of amoeboid reactive microglia and partially improved retinal function. DHA-treatment also improved the morphology of CLN6(nclf) retinas with a preserved thickness of the photoreceptor layer in most regions of the retina. Our results suggest that microglial reactivity closely accompanies disease progression in the CLN6(nclf) retina and both processes can be attenuated with dietary supplemented immuno-modulating compounds.

Neuronal ceroid lipofuscinosis (NCL) is a group of neurodegenerative lysosomal storage disorders characterized by vision loss, mental and motor deficits, and spontaneous seizures. Neuropathological analyses of autopsy material from NCL patients and animal models revealed brain atrophy closely associated with glial activity. Earlier reports also noticed loss of retinal cells and reactive gliosis in some forms of NCL. To study this phenomenon in detail, we analyzed the ocular phenotype of CLN6nclf mice, an established mouse model for variant-late infantile NCL. Retinal morphometry, immunohistochemistry, optokinetic tracking, electroretinography, and mRNA expression were used to characterize retinal morphology and function as well as the responses of Müller cells and microglia. Our histological data showed a severe and progressive degeneration in the CLN6nclf retina co-inciding with reactive Müller glia. Furthermore, a prominent phenotypic transformation of ramified microglia to phagocytic, bloated, and mislocalized microglial cells was identified in CLN6nclf retinas. These events overlapped with a rapid loss of visual perception and retinal function. Based on the strong microglia reactivity we hypothesized that dietary supplementation with immuno-regulatory compounds, curcumin and docosahexaenoic acid (DHA), could ameliorate microgliosis and reduce retinal degeneration. Our analyses showed that treatment of three-week-old CLN6nclf mice with either 5% DHA or 0.6% curcumin for 30 weeks resulted in a reduced number of amoeboid reactive microglia and partially improved retinal function. DHA-treatment also improved the morphology of CLN6nclf retinas with a preserved thickness of the photoreceptor layer in most regions of the retina. Our results suggest that microglial reactivity closely accompanies disease progression in the CLN6nclf retina and both processes can be attenuated with dietary supplemented immuno-modulating compounds.

For a partial word $w$ the longest common compatible prefix of two positions $i,j$, denoted $lccp(i,j)$, is the largest $k$ such that $w[i,i+k-1]\uparrow w[j,j+k-1]$, where $\uparrow$ is the compatibility relation of partial words (it is not an equivalence relation). The LCCP problem is to preprocess a partial word in such a way that any query $lccp(i,j)$ about this word can be answered in $O(1)$ time. It is a natural generalization of the longest common prefix (LCP) problem for regular words, for which an $O(n)$ preprocessing time and $O(1)$ query time solution exists. Recently an efficient algorithm for this problem has been given by F. Blanchet-Sadri and J. Lazarow (LATA 2013). The preprocessing time was $O(nh+n)$, where $h$ is the number of "holes" in $w$. The algorithm was designed for partial words over a constant alphabet and was quite involved. We present a simple solution to this problem with slightly better runtime that works for any linearly-sortable alphabet. Our preprocessing is in time $O(n\mu+n)$, where $\mu$ is the number of blocks of holes in $w$. Our algorithm uses ideas from alignment algorithms and dynamic programming.

Recently Kubica et al. (Inf. Process. Let., 2013) and Kim et al. (submitted to Theor. Comp. Sci.) introduced order-preserving pattern matching. In this problem we are looking for consecutive substrings of the text that have the same "shape" as a given pattern. These results include a linear-time order-preserving pattern matching algorithm for polynomially-bounded alphabet and an extension of this result to pattern matching with multiple patterns. We make one step forward in the analysis and give an $O(\frac{n\log{n}}{\log\log{n}})$ time randomized algorithm constructing suffix trees in the order-preserving setting. We show a number of applications of order-preserving suffix trees to identify patterns and repetitions in time series.

LZ77-based compression schemes compress the input text by replacing factors in the text with an encoded reference to a previous occurrence formed by the couple (length, offset). For a given factor, the smallest is the offset, the smallest is the resulting compression ratio. This is optimally achieved by using the rightmost occurrence of a factor in the previous text. Given a cost function, for instance the minimum number of bits used to represent an integer, we define the Rightmost Equal-Cost Position (REP) problem as the problem of finding one of the occurrences of a factor which cost is equal to the cost of the rightmost one. We present the Multi-Layer Suffix Tree data structure that, for a text of length n, at any time i, it provides REP(LPF) in constant time, where LPF is the longest previous factor, i.e. the greedy phrase, a reference to the list of REP({set of prefixes of LPF}) in constant time and REP(p) in time O(|p| log log n) for any given pattern p.

Dynamic dictionary-based compression schemes are the most daily used data compression schemes since they appeared in the foundational papers of Ziv and Lempel in 1977, commonly referred to as LZ77. Their work is the base of Deflate, gZip, WinZip, 7Zip and many others compression software. All of those compression schemes use variants of the greedy approach to parse the text into dictionary phrases. Greedy parsing optimality was proved by Cohn et al. (1996) for fixed length code and unbounded dictionaries. The optimality of the greedy parsing was never proved for bounded size dictionary which actually all of those schemes require. We define the suffix-closed property for dynamic dictionaries and we show that any LZ77-based dictionary, including the bounded variants, satisfy this property. Under this condition we prove the optimality of the greedy parsing as a variant of the proof by Cohn et al.

We investigate abelian repetitions in Sturmian words. We exploit a bijection between factors of Sturmian words and subintervals of the unitary segment that allows us to study the periods of abelian repetitions by using classical results of elementary Number Theory. We prove that in any Sturmian word the superior limit of the ratio between the maximal exponent of an abelian repetition of period $m$ and $m$ is a number $\geq\sqrt{5}$, and the equality holds for the Fibonacci infinite word. We further prove that the longest prefix of the Fibonacci infinite word that is an abelian repetition of period $F_j$, $j>1$, has length $F_j(F_{j+1}+F_{j-1} +1)-2$ if $j$ is even or $F_j(F_{j+1}+F_{j-1})-2$ if $j$ is odd. This allows us to give an exact formula for the smallest abelian periods of the Fibonacci finite words. More precisely, we prove that for $j\geq 3$, the Fibonacci word $f_j$ has abelian period equal to $F_n$, where $n = \lfloor{j/2}\rfloor$ if $j = 0, 1, 2\mod{4}$, or $n = 1 + \lfloor{j/2}\rfloor$ if $ j = 3\mod{4}$., Comment: Accepted to DLT 2013