Search

For every n ≥ 1 , generic models of ZFC will be presented for either of the following two sentences: 1. There exists a linear Σ n + 2 1 set not equal to the projection of any uniform planar Π n + 2 1 set. 2. There exists a linear Δ n + 2 1 set not equal to the projection of any uniform planar Π n + 1 1 set. Ensuing consistency and independence corollaries are discussed. [ABSTRACT FROM AUTHOR]

Simple Summary: The relationship between genomic characteristics and species traits is of paramount importance for biology. For genomic characteristics, we considered characteristics close to the rate of gene change in the process of evolution, including such extreme cases as pseudogenization and gene loss. This can be conceptualized as selection at the gene level. Amino acid substitutions in the positions that functionally determine protein domains were also considered. For species traits, we considered the maximal reported lifespan, the body weight of an adult animal, and the related longevity quotient. The first and second traits are also related, but only at the stochastic level; therefore, their behavior is a priori not similar. We proposed a novel technique that allows one to determine the relationship between any genomic characteristic and species traits. This technique is exemplified in the physiologically significant genes involved in regulating circadian rhythms, which change quite rapidly during evolution. Regardless of devising this technique, the study of the genes that are critical for circadian rhythms is of interest on its own. For instance, we thoroughly examined the paralogous genes Fbxl21 and Fbxl3, which are involved in the regulation of circadian rhythms. We found out that the above-mentioned characteristic of the Fbxl21 gene correlates with the maximal reported lifespan and body weight only in two superorders of placental mammals, Euarchontoglires (the clades Euarchonta, Lagomorpha, and Rodentia) and Afrotheria. On the contrary, such a correlation is not observed in other superorders, such as Laurasiatheria and Xenarthra. The presence or absence of the correlation is confirmed statistically with a very high accuracy. The rate of change in the Fbxl21 gene indicates, for example, the peculiarity of its evolution in apes. This article proposes a methodology for establishing a relationship between the change rate of a given gene (relative to a given taxon) together with the amino acid composition of the proteins encoded by this gene and the traits of the species containing this gene. The methodology is illustrated based on the mammalian genes responsible for regulating the circadian rhythms that underlie a number of human disorders, particularly those associated with aging. The methods used are statistical and bioinformatic ones. A systematic search for orthologues, pseudogenes, and gene losses was performed using our previously developed methods. It is demonstrated that the least conserved Fbxl21 gene in the Euarchontoglires superorder exhibits a statistically significant connection of genomic characteristics (the median of dN/dS for a gene relative to all the other orthologous genes of a taxon, as well as the preference or avoidance of certain amino acids in its protein) with species-specific lifespan and body weight. In contrast, no such connection is observed for Fbxl21 in the Laurasiatheria superorder. This study goes beyond the protein-coding genes, since the accumulation of amino acid substitutions in the course of evolution leads to pseudogenization and even gene loss, although the relationship between the genomic characteristics and the species traits is still preserved. The proposed methodology is illustrated using the examples of circadian rhythm genes and proteins in placental mammals, e.g., longevity is connected with the rate of Fbxl21 gene change, pseudogenization or gene loss, and specific amino acid substitutions (e.g., asparagine at the 19th position of the CRY-binding domain) in the protein encoded by this gene. [ABSTRACT FROM AUTHOR]

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called "structures", meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity. [ABSTRACT FROM AUTHOR]

It was established by Jensen in 1970 that there is a generic extension L [ a ] of the constructible universe L by a non-constructible real a ∉ L , minimal over L , such that a is Δ 3 1 in L [ a ] . Our first main theorem generalizes Jensen's result by constructing, for each n ≥ 2 , a generic extension L [ a ] by a non-constructible real a ∉ L , still minimal over L , such that a is Δ n + 1 1 in L [ a ] but all Σ n 1 reals are constructible in L [ a ] . Jensen's forcing construction has found a number of applications in modern set theory. A problem was recently discussed as to whether Jensen's construction can be reproduced entirely by means of second-order Peano arithmetic PA 2 , or, equivalently, ZFC − (minus the power set axiom). The obstacle is that the proof of the key CCC property (whether by Jensen's original argument or the later proof using the diamond technique) essentially involves countable elementary submodels of L ω 2 , which is way beyond ZFC − . We demonstrate how to circumvent this difficulty by means of killing only definable antichains in the course of a Jensen-like transfinite construction of the forcing notion, and then use this modification to define a model with a minimal Δ n + 1 1 real as required as a class-forcing extension of a model of ZFC − plus V = L . [ABSTRACT FROM AUTHOR]

The paper solves the problem of constructing an evolutionary tree and the evolution of structures along it. This problem has long been posed and extensively researched; it is formulated and discussed below. As a result, we construct an exact cubic-time algorithm which outputs a tree with the minimum cost of embedding into it and of embedding it into a given network (Theorem 1). We construct an algorithm that outputs a minimum embedding of a tree into a network, taking into account incomplete linear sorting; the algorithm depends linearly on the number of nodes in the network and is exact if the sorting cost is not less than the sum of the duplication cost and the loss cost (Theorem 3). We construct an exact approximately quadratic-time algorithm which, for arbitrary costs of SCJ operations, solves the problem of reconstruction of given structures on any two-star tree (Theorem 4). We construct an exact algorithm which reduced the problem of DCJ reconstruction of given structures on any star to a logarithmic-length sequence of SAT problems, each of them being of approximately quadratic size (Theorem 5). The theorems have rigorous and complete proofs of correctness and complexity of the algorithms, and are accompanied by numerical examples and numerous explanatory illustrations, including flowcharts. [ABSTRACT FROM AUTHOR]

Abstract Background A long recognized problem is the inference of the supertree S that amalgamates a given set {Gj} of trees Gj, with leaves in each Gj being assigned homologous elements. We ground on an approach to find the tree S by minimizing the total cost of mappings αj of individual gene trees Gj into S. Traditionally, this cost is defined basically as a sum of duplications and gaps in each αj. The classical problem is to minimize the total cost, where S runs over the set of all trees that contain an exhaustive non-redundant set of species from all input Gj. Results We suggest a reformulation of the classical NP-hard problem of building a supertree in terms of the global minimization of the same cost functional but only over species trees S that consist of clades belonging to a fixed set P (e.g., an exhaustive set of clades in all Gj). We developed a deterministic solving algorithm with a low degree polynomial (typically cubic) time complexity with respect to the size of input data. We define an extensive set of elementary evolutionary events and suggest an original definition of mapping β of tree G into tree S. We introduce the cost functional c(G, S, f ) and define the mapping β as the global minimum of this functional with respect to the variable f, in which sense it is a generalization of classical mapping α. We suggest a reformulation of the classical NP-hard mapping (reconciliation) problem by introducing time slices into the species tree S and present a cubic time solving algorithm to compute the mapping β. We introduce two novel definitions of the evolutionary scenario based on mapping β or a random process of gene evolution along a species tree. Conclusions Developed algorithms are mathematically proved, which justifies the following statements. The supertree building algorithm finds exactly the global minimum of the total cost if only gene duplications and losses are allowed and the given sets of gene trees satisfies a certain condition. The mapping algorithm finds exactly the minimal mapping β, the minimal total cost and the evolutionary scenario as a minimum over all possible distributions of elementary evolutionary events along the edges of tree S. The algorithms and their effective software implementations provide useful tools in many biological studies. They facilitate processing of voluminous tree data in acceptable time still largely avoiding heuristics. Performance of the tools is tested with artificial and prokaryotic tree data. Reviewers This article was reviewed by Prof. Anthony Almudevar, Prof. Alexander Bolshoy (nominated by Prof. Peter Olofsson), and Prof. Marek Kimmel.

Abstract Background In previous work, we introduced a concept, a mathematical model and its computer realization that describe the interaction between bacterial and phage type RNA polymerases, protein factors, DNA and RNA secondary structures during transcription, including transcription initiation and termination. The model accurately reproduces changes of gene transcription level observed in polymerase sigma-subunit knockout and heat shock experiments in plant plastids. The corresponding computer program and a user guide are available at http://lab6.iitp.ru/en/rivals. Here we apply the model to the analysis of transcription and (partially) translation processes in the mitochondria of frog, rat and human. Notably, mitochondria possess only phage-type polymerases. We consider the entire mitochondrial genome so that our model allows RNA polymerases to complete more than one circle on the DNA strand. Results Our model of RNA polymerase interaction during transcription initiation and elongation accurately reproduces experimental data obtained for plastids. Moreover, it also reproduces evidence on bulk RNA concentrations and RNA half-lives in the mitochondria of frog, human with or without the MELAS mutation, and rat with normal (euthyroid) or hyposecretion of thyroid hormone (hypothyroid). The transcription characteristics predicted by the model include: (i) the fraction of polymerases terminating at a protein-dependent terminator in both directions (the terminator polarization), (ii) the binding intensities of the regulatory protein factor (mTERF) with the termination site and, (iii) the transcription initiation intensities (initiation frequencies) of all promoters in all five conditions (frog, healthy human, human with MELAS syndrome, healthy rat, and hypothyroid rat with aberrant mtDNA methylation). Using the model, absolute levels of all gene transcription can be inferred from an arbitrary array of the three transcription characteristics, whereas, for selected genes only relative RNA concentrations have been experimentally determined. Conversely, these characteristics and absolute transcription levels can be obtained using relative RNA concentrations and RNA half-lives known from various experimental studies. In this case, the “inverse problem” is solved with multi-objective optimization. Conclusions In this study, we demonstrate that our model accurately reproduces all relevant experimental data available for plant plastids, as well as the mitochondria of chordates. Using experimental data, the model is applied to estimate binding intensities of phage-type RNA polymerases to their promoters as well as predicting terminator characteristics, including polarization. In addition, one can predict characteristics of phage-type RNA polymerases and the transcription process that are difficult to measure directly, e.g., the association between the promoter’s nucleotide composition and the intensity of polymerase binding. To illustrate the application of our model in functional predictions, we propose a possible mechanism for MELAS syndrome development in human involving a decrease of Phe-tRNA, Val-tRNA and rRNA concentrations in the cell. In addition, we describe how changes in methylation patterns of the mTERF binding site and three promoters in hypothyroid rat correlate with changes in intensities of the mTERF binding and transcription initiations. Finally, we introduce an auxiliary model to describe the interaction between polysomal mRNA and ribonucleases.