Search

A new perspective is introduced regarding the analysis of Multiple Sequence Alignments (MSA), representing aligned data defined over a finite alphabet of symbols. The framework is designed to produce a block decomposition of an MSA, where each block is comprised of sequences exhibiting a certain site-coherence. The key component of this framework is an information theoretical potential defined on pairs of sites (links) within the MSA. This potential quantifies the expected drop in variation of information between the two constituent sites, where the expectation is taken with respect to all possible sub-alignments, obtained by removing a finite, fixed collection of rows. It is proved that the potential is zero for linked sites representing columns, whose symbols are in bijective correspondence and it is strictly positive, otherwise. It is furthermore shown that the potential assumes its unique minimum for links at which each symbol pair appears with the same multiplicity. Finally, an application is presented regarding anomaly detection in an MSA, composed of inverse fold solutions of a fixed tRNA secondary structure, where the anomalies are represented by inverse fold solutions of a different RNA structure., Comment: 15 pages, 2 figures

We propose a novel mathematical paradigm for the study of genetic variation in sequence alignments. This framework originates from extending the notion of pairwise relations, upon which current analysis is based on, to k-ary dissimilarity. This dissimilarity naturally leads to a generalization of simplicial complexes by endowing simplices with weights, compatible with the boundary operator. We introduce the notion of k-stances and dissimilarity complex, the former encapsulating arithmetic as well as topological structure expressing these k-ary relations. We study basic mathematical properties of dissimilarity complexes and show how this approach captures an entirely new layer of biologically relevant viral dynamics in the context of SARS-CoV-2 and H1N1 flu genomic data.

We provide a bottom up construction of torsion generators for weighted homology of a weighted complex over a discrete valuation ring $R=\mathbb{F}[[\pi]]$. This is achieved by starting from a basis for classical homology of the $n$-th skeleton for the underlying complex with coefficients in the residue field $\mathbb{F}$ and then lifting it to a basis for the weighted homology with coefficients in the ring $R$. Using the latter, a bijection is established between $n+1$ and $n$ dimensional simplices whose weight ratios provide the exponents of the $\pi$-monomials that generate each torsion summand in the structure theorem of the weighted homology modules over $R$. We present algorithms that subsume the torsion computation by reducing it to normalization over the residue field of $R$, and describe a Python package we implemented that takes advantage of this reduction and performs the computation efficiently., Comment: 16 pages, 2 figures

In this paper we further describe the features of the topological space $K(R)$ obtained from the loop nerve of $R$, for $R=(S,T)$ a bi-secondary structure. We will first identify certain distinct combinatorial structures in the arc diagram of $R$ which we will call crossing components. The main theorem of this paper shows that the total number of these crossing components equals the rank of $H_2(R)$, the second homology group of the loop nerve.

In this paper we compute the loop homology of bi-secondary structures. Bi-secondary structures were introduced by Haslinger and Stadler and are pairs of RNA secondary structures, i.e. diagrams having non-crossing arcs in the upper half-plane. A bi-secondary structure is represented by drawing its respective secondary structures in the upper and lower half-plane. An RNA secondary structure has a loop decomposition, where a loop corresponds to a boundary component, regarding the secondary structure as an orientable fatgraph. The loop-decomposition of secondary structures facilitates the computation of its free energy and any two loops intersect either trivially or in exactly two vertices. In bi-secondary structures the intersection of loops is more complex and is of importance in current algorithmic work in bio-informatics and evolutionary optimization. We shall construct a simplicial complex capturing the intersections of loops and compute its homology. We prove that only the zeroth and second homology groups are nontrivial and furthermore show that the second homology group is free. Finally, we provide evidence that the generators of the second homology group have a bio-physical interpretation: they correspond to pairs of mutually exclusive substructures.

The analysis of the dynamics on complex networks is closely connected to structural features of the networks. Features like, for instance, graph-cores and node degrees have been studied ubiquitously. Here we introduce the D-spectrum of a network, a novel new framework that is based on a collection of nested chains of subgraphs within the network. Graph-cores and node degrees are merely from two particular such chains of the D-spectrum. Each chain gives rise to a ranking of nodes and, for a fixed node, the collection of these ranks provides us with the D-spectrum of the node. Besides a node deletion algorithm, we discover a connection between the D-spectrum of a network and some fixed points of certain graph dynamical systems (MC systems) on the network. Using the D-spectrum we identify nodes of similar spreading power in the susceptible-infectious-recovered (SIR) model on a collection of real world networks as a quick application. We then discuss our results and conclude that D-spectra represent a meaningful augmentation of graph-cores and node degrees., Comment: SOME UPDATE WITH A NEW TITLE. SI HAS NOT BEEN UPLOADED AS IT CONTAINS TOO MANY FIGURES WHICH ARE ESSENTIALLY THE SAME AS THE ONES IN v1 EXCEPT FOR SOME MINOR ADJUSTMENTS, AND IT IS SLOW TO UPLOAD HERE

Computing the reversal distances of signed permutations is an important topic in Bioinformatics. Recently, a new lower bound for the reversal distance was obtained via the plane permutation framework. This lower bound appears different from the existing lower bound obtained by Bafna and Pevzner through breakpoint graphs. In this paper, we prove that the two lower bounds are equal. Moreover, we confirm a related conjecture on skew-symmetric plane permutations, which can be restated as follows: let $p=(0,-1,-2,\ldots -n,n,n-1,\ldots 1)$ and let $$ \tilde{s}=(0,a_1,a_2,\ldots a_n,-a_n,-a_{n-1},\ldots -a_1) $$ be any long cycle on the set $\{-n,-n+1,\ldots 0,1,\ldots n\}$. Then, $n$ and $a_n$ are always in the same cycle of the product $p\tilde{s}$. Furthermore, we show the new lower bound via plane permutations can be interpreted as the topological genera of orientable surfaces associated to signed permutations., Comment: slightly updated