We introduce a new technique for proving bounds on the Kolmogorov complexity of geometric objects in Euclidean space, such as points and lines. We apply this technique to prove two theorems on algorithmic information theory, both of which have consequences for well-known problems in geometric measure theory. First, we show that for any point $x$ in the plane and any other point $y$ sufficiently independent of $x$, the distance between $x$ and $y$ retains at least half the complexity of the original point $x$. By the point-to-set principle of J. Lutz and N. Lutz, this yields an improved lower bound on the Hausdorff dimension of pinned distance sets, a topic closely related to Falconer's distance set conjecture. Second, we prove an analogous result for orthogonal projections: for any point $x$ in the plane and any line through the origin which is sufficiently independent of $x$, the projection of $x$ onto that line retains at least half the complexity of $x$. As a consequence, we obtain a generalization of a theorem of Bourgain on exceptional sets for orthogonal projections.

The point-to-set principle of J. Lutz and N. Lutz (2018) has recently enabled the theory of computing to be used to answer open questions about fractal geometry in Euclidean spaces Rn. These are classical questions, meaning that their statements do not involve computation or related aspects of logic. In this paper we extend the reach of the point-to-set principle from Euclidean spaces to arbitrary separable metric spaces X. We first extend two algorithmic dimensions—computability-theoretic versions of classical Hausdorff and packing dimensions that assign dimensions dim⁡(x) and Dim(x) to individual points x∈X—to arbitrary separable metric spaces and to arbitrary gauge families. Our first two main results then extend the point-to-set principle to arbitrary separable metric spaces and to a large class of gauge families. We demonstrate the power of our extended point-to-set principle by using it to prove new theorems about classical fractal dimensions in hyperspaces. (For a concrete computational example, the stages E0,E1,E2,… used to construct a self-similar fractal E in the plane are elements of the hyperspace of the plane, and they converge to E in the hyperspace.) Our third main result, proven via our extended point-to-set principle, states that, under a wide variety of gauge families, the classical packing dimension agrees with the classical upper Minkowski dimension on all hyperspaces of compact sets. We use this theorem to give, for all sets E that are analytic, i.e., Σ11, a tight bound on the packing dimension of the hyperspace of E in terms of the packing dimension of E itself.

The point-to-set principle of J. Lutz and N. Lutz (2018) has recently enabled the theory of computing to be used to answer open questions about fractal geometry in Euclidean spaces ℝⁿ. These are classical questions, meaning that their statements do not involve computation or related aspects of logic. In this paper we extend the reach of the point-to-set principle from Euclidean spaces to arbitrary separable metric spaces X. We first extend two fractal dimensions—computability-theoretic versions of classical Hausdorff and packing dimensions that assign dimensions dim(x) and Dim(x) to individual points x ∈ X—to arbitrary separable metric spaces and to arbitrary gauge families. Our first two main results then extend the point-to-set principle to arbitrary separable metric spaces and to a large class of gauge families. We demonstrate the power of our extended point-to-set principle by using it to prove new theorems about classical fractal dimensions in hyperspaces. (For a concrete computational example, the stages E₀, E₁, E₂, … used to construct a self-similar fractal E in the plane are elements of the hyperspace of the plane, and they converge to E in the hyperspace.) Our third main result, proven via our extended point-to-set principle, states that, under a wide variety of gauge families, the classical packing dimension agrees with the classical upper Minkowski dimension on all hyperspaces of compact sets. We use this theorem to give, for all sets E that are analytic, i.e., Σ¹₁, a tight bound on the packing dimension of the hyperspace of E in terms of the packing dimension of E itself.

A real number x is absolutely normal if, for every base b≥2, every two equally long strings of digits appear with equal asymptotic frequency in the base-b expansion of x. This paper presents an explicit algorithm that generates the binary expansion of an absolutely normal number x, with the nth bit of x appearing after npolylog(n) computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases.

The Schnorr-Stimm dichotomy theorem (Schnorr and Stimm, 1972) concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet Σ. The theorem asserts that, for any such sequence S, the following two things are true. (1) If S is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in S), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on S. (2) If S is normal, then any finite-state gambler loses money at an exponential rate betting on S. In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence div(S||α) of a probability measure α on Σ from a sequence S over Σ and the upper asymptotic divergence Div(S||α) of α from S in such a way that a sequence S is α-normal (meaning that every string w has asymptotic frequency α(w) in S) if and only if Div(S||α)=0. We also use the Kullback-Leibler divergence to quantify the total risk RiskG(w) that a finite-state gambler G takes when betting along a prefix w of S. Our main theorem is a strong dichotomy theorem that uses the above notions to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem (with the latter routinely extended from normality to α-normality). Modulo asymptotic caveats in the paper, our strong dichotomy theorem says that the following two things hold for prefixes w of S. ( $1~'$ ) The infinitely-often exponential rate of winning in 1 is 2Div(S||α)|w|. ( $2~'$ ) The exponential rate of loss in 2 is 2- RiskG(w). We also use (1 $'$ ) to show that 1- Div(S||α)/c, where c = log(1/ mina ∈ Σα(a)), is an upper bound on the finite-state α-dimension of S and prove the dual fact that 1- div(S||α)/c is an upper bound on the finite-state strong α-dimension of S.

The Schnorr-Stimm dichotomy theorem [Schnorr and Stimm, 1972] concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet Σ. The theorem asserts that, for any such sequence S, the following two things are true. (1) If S is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in S), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on S. (2) If S is normal, then any finite-state gambler betting on S loses money at an exponential rate betting on S. In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence div(S||α) of a probability measure α on Σ from a sequence S over Σ and the upper asymptotic divergence Div(S||α) of α from S in such a way that a sequence S is α-normal (meaning that every string w has asymptotic frequency α(w) in S) if and only if Div(S||α)=0. We also use the Kullback-Leibler divergence to quantify the total risk Risk_G(w) that a finite-state gambler G takes when betting along a prefix w of S. Our main theorem is a strong dichotomy theorem that uses the above notions to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem (with the latter routinely extended from normality to α-normality). Modulo asymptotic caveats in the paper, our strong dichotomy theorem says that the following two things hold for prefixes w of S. (1') The infinitely-often exponential rate of winning in 1 is 2^{Div(S||α)|w|}. (2') The exponential rate of loss in 2 is 2^{-Risk_G(w)}. We also use (1') to show that 1-Div(S||α)/c, where c= log(1/ min_{a∈Σ} α(a)), is an upper bound on the finite-state α-dimension of S and prove the dual fact that 1-div(S||α)/c is an upper bound on the finite-state strong α-dimension of S.

BACKGROUND: Several methods have been developed to predict the pathogenicity of missense mutations but none has been specifically designed for classification of variants in mtDNA-encoded polypeptides. Moreover, there is not available curated dataset of neutral and damaging mtDNA missense variants to test the accuracy of predictors. Because mtDNA sequencing of patients suffering mitochondrial diseases is revealing many missense mutations, it is needed to prioritize candidate substitutions for further confirmation. Predictors can be useful as screening tools but their performance must be improved. RESULTS: We have developed a SVM classifier (Mitoclass.1) specific for mtDNA missense variants. Training and validation of the model was executed with 2,835 mtDNA damaging and neutral amino acid substitutions, previously curated by a set of rigorous pathogenicity criteria with high specificity. Each instance is described by a set of three attributes based on evolutionary conservation in Eukaryota of wildtype and mutant amino acids as well as coevolution and a novel evolutionary analysis of specific substitutions belonging to the same domain of mitochondrial polypeptides. Our classifier has performed better than other web-available tested predictors. We checked performance of three broadly used predictors with the total mutations of our curated dataset. PolyPhen-2 showed the best results for a screening proposal with a good sensitivity. Nevertheless, the number of false positive predictions was too high. Our method has an improved sensitivity and better specificity in relation to PolyPhen-2. We also publish predictions for the complete set of 24,201 possible missense variants in the 13 human mtDNA-encoded polypeptides. CONCLUSIONS: Mitoclass.1 allows a better selection of candidate damaging missense variants from mtDNA. A careful search of discriminatory attributes and a training step based on a curated dataset of amino acid substitutions belonging exclusively to human mtDNA genes allows an improved performance. Mitoclass.1 accuracy could be improved in the future when more mtDNA missense substitutions will be available for updating the attributes and retraining the model.

The wide availability of sequenced biological data has challenged the conventional methods and tools used in molecular biology to compute the conservation index. As the size of input datasets increases, the time-cost of current conservation methods is becoming unaffordable. We propose a new software tool that combines several estimation methods applied to the conservation computation process with parallelization and divide-and-conquer techniques substantially improving its performance without affecting its accuracy. We have also made an in-depth analysis of the impact of different methods and parameter selection on the alignment process applied to input datasets prior to their conservation analysis. We have used sets of mitochondrial DNA sequences with different levels of heterogeneity and length, to provide a full case study. Both the software tool and the input datasets used in this research are freely available at http://www.zaramit.orglconservation_index.

Alessandra Carbone, Fernando Ferreira, Benedikt Löwe, Elvira Mayordomo; Computability in Europe 2010, Journal of Logic and Computation, Volume 25, Issue 4,

Most phylogeny estimation systems such as SATe2or DACTAL use fixed configurations and tools that make them suitable only for solving specific problems. Out of that scope, a hand-made combination of individual tools and methods has to be composed in order to get the desired phylogeny estimation. PhyloFlow is a new framework based on a workflow extendable to a wide range of tasks in phylogenetic analysis. This system is specially intended to build large phylogenies, where most of the methods do not provide a solution at all or the computing time required is not affordable. The workflow can scale to different phylogenetic estimation problems, the methods and stages already included can be fully customizable and once the user has set up the system, it will run automatically until the phylogenetic tree is completely estimated. With the current version we have recreated two different phy-logenetic systems: DACTAL and a study case for the human mitochondrial DNA. The first one displays the capabilities of our framework to reproduce the existing systems, in addition with the properties that a parallel system can provide. The second one shows the possibilities of building a real case workflow to estimate a phylogenetic tree for more than 23000 sequences of human mitochondrial DNA (16569 bp on average) applying biological knowledge to the process. Both workflows have been run sequentially and in parallel in a HTC cluster (HTCCondor and DAGMan). PhyloFlow source code, the datasets and the workflow configurations are available by request to the first author.

F. FerreiraDepartamento de Matematica, Faculdade de Ciencias, Universidade de Lisboa, Campo Grande,1749-016 Lisboa, Portugale-mail: [email protected]. Lowe ( )Institute for Logic, Language and Computation, Universiteit van Amsterdam, Postbus 94242,1090 GE Amsterdam, The Netherlandse-mail: [email protected]. LoweDepartment Mathematik, Universitat Hamburg, Bundesstrasse 55, 20146 Hamburg, GermanyE. MayordomoDepartamento de Informatica e Ingenieria de Sistemas, Instituto de Investigacion en Ingenieria deAragon (I3A), Universidad de Zaragoza, 50015 Zaragoza, Spaine-mail: [email protected]

BACKGROUND: Mitochondrial DNA is an ideal source of information to conduct evolutionary and phylogenetic studies due to its extraordinary properties and abundance. Many insights can be gained from these, including but not limited to screening genetic variation to identify potentially deleterious mutations. However, such advances require efficient solutions to very difficult computational problems, a need that is hampered by the very plenty of data that confers strength to the analysis. RESULTS: We develop a systematic, automated methodology to overcome these difficulties, building from readily available, public sequence databases to high-quality alignments and phylogenetic trees. Within each stage in an autonomous workflow, outputs are carefully evaluated and outlier detection rules defined to integrate expert knowledge and automated curation, hence avoiding the manual bottleneck found in past approaches to the problem. Using these techniques, we have performed exhaustive updates to the human mitochondrial phylogeny, illustrating the power and computational scalability of our approach, and we have conducted some initial analyses on the resulting phylogenies. CONCLUSIONS: The problem at hand demands careful definition of inputs and adequate algorithmic treatment for its solutions to be realistic and useful. It is possible to define formal rules to address the former requirement by refining inputs directly and through their combination as outputs, and the latter are also of help to ascertain the performance of chosen algorithms. Rules can exploit known or inferred properties of datasets to simplify inputs through partitioning, therefore cutting computational costs and affording work on rapidly growing, otherwise intractable datasets. Although expert guidance may be necessary to assist the learning process, low-risk results can be fully automated and have proved themselves convenient and valuable.

This paper investigates the existence of inseparable disjoint pairs of NP languages and related strong hypotheses in computational complexity. Our main theorem says that, if NP does not have measure 0 in EXP, then there exist disjoint pairs of NP languages that are P-inseparable, in fact TIME(2(n k))-inseparable. We also relate these conditions to strong hypotheses concerning randomness and genericity of disjoint pairs.

The pressing need for eficient compression schemes for XML documents has recently been focused on stack computation [6, 9], and in particular calls for a formulation of information-lossless stack or pushdown compressors that allows a formal analysis of their performance and a more ambitious use of the stack in XML compression, where so far it is mainly connected to parsing mechanisms. In this paper we introduce the model of pushdown compressor, based on pushdown transducers that compute a single injective function while keeping the widest generality regarding stack computation. The celebrated Lempel-Ziv algorithm LZ78 [10] was introduced as a general purpose compression algorithm that outperforms finite-state compressors on all sequences. We compare the performance of the Lempel-Ziv algorithm with that of the pushdown compressors, or compression algorithms that can be implemented with a pushdown transducer. This comparison is made without any a priori assumption on the data's source and considering the asymptotic compression ratio for infinite sequences. We prove that Lempel-Ziv is incomparable with pushdown compressors.

Self-similar fractals arise as the unique attractors of iterated function systems (IFSs) consisting of finitely many contracting similarities satisfying an open set condition. Each point x in such a fractal F arising from an IFS S is naturally regarded as the “outcome” of an infinite coding sequence T (which need not be unique) over the alphabet $\Sigma_k = \{0, \ldots, k-1\}$, where k is the number of contracting similarities in S. A classical theorem of Moran (1946) and Falconer (1989) states that the Hausdorff and packing dimensions of a self-similar fractal coincide with its similarity dimension, which depends only on the contraction ratios of the similarities. The theory of computing has recently been used to provide a meaningful notion of the dimensions of individual points in Euclidean space. In this paper, we use (and extend) this theory to analyze the dimensions of individual points in fractals that are computably self-similar, meaning that they are unique attractors of IFSs that are computable and satisfy the open set condition. Our main theorem states that, if $F \subseteq \mathbb{R}^n$ is any computably self-similar fractal and S is any IFS testifying to this fact, then the dimension identities $\operatorname{dim}(x) = \operatorname{sdim}(F) \operatorname{dim}^{\pi_S}(T)$ and $\operatorname{Dim}(x) = \operatorname{sdim}(F) \operatorname{Dim}^{\pi_S}(T)$ hold for all $x \in F$ and all coding sequences T for x. In these equations, $\operatorname{sdim}(F)$ denotes the similarity dimension of the fractal F; $\operatorname{dim}(x)$ and $\operatorname{Dim}(x)$ denote the dimension and strong dimension, respectively, of the point x in Euclidean space; and $\operatorname{dim}^{\pi_S}(T)$ and $\operatorname{Dim}^{\pi_S}(T)$ denote the dimension and strong dimension, respectively, of the coding sequence T relative to a probability measure $\pi_S$ that the IFS S induces on the alphabet $\Sigma_k$. The above-mentioned theorem of Moran and Falconer follows easily from our main theorem by relativization. Along the way to our main theorem, we develop the elements of the theory of constructive dimensions relative to general probability measures. The proof of our main theorem uses Kolmogorov complexity characterizations of these dimensions.

The two most important notions of fractal dimension are Hausdorff dimension, developed by Hausdorff [Math. Ann., 79 (1919), pp. 157–179], and packing dimension, developed independently by Tricot [Math. Proc. Cambridge Philos. Soc., 91 (1982), pp. 57–74] and Sullivan [Acta Math., 153 (1984), pp. 259–277]. Both dimensions have the mathematical advantage of being defined from measures, and both have yielded extensive applications in fractal geometry and dynamical systems. Lutz [Proceedings of the 15th IEEE Conference on Computational Complexity, Florence, Italy, 2000, IEEE Computer Society Press, Piscataway, NJ, 2000, pp. 158–169] has recently proven a simple characterization of Hausdorff dimension in terms of gales, which are betting strategies that generalize martingales. Imposing various computability and complexity constraints on these gales produces a spectrum of effective versions of Hausdorff dimension, including constructive, computable, polynomial-space, polynomial-time, and finite-state dimensions. Work by several investigators has already used these effective dimensions to shed significant new light on a variety of topics in theoretical computer science. In this paper we show that packing dimension can also be characterized in terms of gales. Moreover, even though the usual definition of packing dimension is considerably more complex than that of Hausdorff dimension, our gale characterization of packing dimension is an exact dual of—and every bit as simple as—the gale characterization of Hausdorff dimension. Effectivizing our gale characterization of packing dimension produces a variety of effective strong dimensions, which are exact duals of the effective dimensions mentioned above. In general (and in analogy with the classical fractal dimensions), the effective strong dimension of a set or sequence is at least as great as its effective dimension, with equality for sets or sequences that are sufficiently regular. We develop the basic properties of effective strong dimensions and prove a number of results relating them to fundamental aspects of randomness, Kolmogorov complexity, prediction, Boolean circuit-size complexity, polynomial-time degrees, and data compression. Aside from the above characterization of packing dimension, our two main theorems are the following. 1. If $\vec{\beta} = (\beta_0,\beta_1,\ldots)$ is a computable sequence of biases that are bounded away from 0 and R is random with respect to $\vec{\beta}$, then the dimension and strong dimension of R are the lower and upper average entropies, respectively, of $\vec{\beta}$. 2. For each pair of $\Delta^0_2$-computable real numbers $0 < \alpha \le \beta \le 1$, there exists $A \in {\rm E}$ such that the polynomial-time many-one degree of A has dimension $\alpha$ in E and strong dimension $\beta$ in E. Our proofs of these theorems use a new large deviation theorem for self-information with respect to a bias sequence $\vec{\beta}$ that need not be convergent.

The "analyst's traveling salesman theorem" of geometric measure theory characterizes those subsets of Euclidean space that are contained in curves of finite length. This result, proven for the plane by Jones (1990) and extended to higher-dimensional Euclidean spaces by Okikiolu (1992), says that a bounded set K is contained in some curve of finite length if and only if a certain "square beta sum", involving the "width of K" in each element of an infinite system of overlapping "tiles" of descending size, is finite. In this paper we characterize those points of Euclidean space that lie on computable curves of finite length. We do this by formulating and proving a computable extension of the analyst's traveling salesman theorem. Our extension, the computable analyst's traveling salesman theorem, says that a point in Euclidean space lies on some computable curve of finite length if and only if it is "permitted" by some computable "Jones constriction". A Jones constriction here is an explicit assignment of a rational cylinder to each of the above-mentioned tiles in such a way that, when the radius of the cylinder corresponding to a tile is used in place of the "width of K" in each tile, the square beta sum is finite. A point is permitted by a Jones constriction if it is contained in the cylinder assigned to each tile containing the point. The main part of our proof is the construction of a computable curve of finite length traversing all the points permitted by a given Jones constriction. Our construction uses the main ideas of Jones's "farthest insertion" construction, but takes a very different form, because, having no direct access to the points permitted by the Jones constriction, our algorithm must work exclusively with the constriction itself

We compare the weak completeness notions for E in the sense of Lutz's resource-bounded measure theory (1992) with respect to the standard polynomial time reducibilities. Our results parallel results for classical completeness by Watanabe (1987) and others. We show that the weak completeness notions for 1-query reductions coincide: A set is weakly complete for E under 1-truth-table reducibility iff it is weakly complete for length-increasing one-one reducibility. For most of the other polynomial reducibilities, however, we obtain separations of the weak completeness notions where these reducibilities differ on E (Ladner et al. (1975)). In fact our separations simultaneously hold for the corresponding weak completeness notions for E and E/sub 2/, for the classical completeness notions, and for the weak completeness notions in the sense of the resource-bounded Baire category concepts of Ambos-Spies et al. (1988) and Ambos-Spies (1995).

The main theorem of this paper is that, for every real number $\alpha < 1$ (e.g., $\alpha = 0.99$), only a measure 0 subset of the languages decidable in exponential time are $ \leqslant _{n^\alpha - tt}^{\text{p}} $-reducible to languages that are not exponentially dense. Thus every$ \leqslant _{n^\alpha - tt}^{\text{p}} $hard language for E is exponentially dense. This strengthens Watanabe’s 1987 result, that every $ \leqslant _{(\log n) - tt}^{\text{p}} $-hard language for E is exponentially dense. The combinatorial technique used here, the sequentially most frequent query selection, also gives a new, simpler proof of Watanabe’s result. The main theorem also has implications for the structure of NP under strong hypotheses. Ogiwara and Watanabe (1991) have shown that the hypothesis ${\text{P}} \ne {\text{NP}}$ implies that every $ \leqslant _{btt}^{\text{p}} $ -hard language for NP is nonsparse (i.e., not polynomially sparse). Their technique does not appear to allow significant relaxation of either the query bound or the sparseness criterion. It is shown here that a stronger hypothesis—namely, that NP does not have measure 0 in exponential time—implies the stronger conclusion that, for every real $\alpha < 1$, every $ \leqslant _{n^\alpha - tt}^{\text{p}} $-hard language for NP is exponentially dense. Evidence is presented that this stronger hypothesis is reasonable. The proof of the main theorem uses a new, very general weak stochasticity theorem, ensuring that almost every language in E is statistically unpredictable by feasible deterministic algorithms, even with linear nonuniform advice.