A topological algorithm for identification of structural domains of proteins

Background: Identification of the structural domains of proteins is important for our understanding of the organizational principles and mechanisms of protein folding, and for insights into protein function and evolution. Algorithmic methods of dissecting protein of known structure into domains developed so far are based on an examination of multiple geometrical, physical and topological features. Successful as many of these approaches are, they employ a lot of heuristics, and it is not clear whether they illuminate any deep underlying principles of protein domain organization. Other well-performing domain dissection methods rely on comparative sequence analysis. These methods are applicable to sequences with known and unknown structure alike, and their success highlights a fundamental principle of protein modularity, but this does not directly improve our understanding of protein spatial structure.

A similarity measure for graphs with low computational complexity

We present and analyze an algorithm to measure the structural similarity of generalized trees, a new graph class which includes rooted trees. For this, we represent structural properties of graphs as strings and define the similarity of two Graphs as optimal alignments of the corresponding property stings. We prove that the obtained graph similarity measures are so called Backward similarity measures. From this we find that the time complexity of our algorithm is polynomial and, hence, significantly better than the time complexity of classical graph similarity methods based on isomorphic relations. (c) 2006 Elsevier Inc. All rights reserved.

Information theoretic measures of UHG graphs with low computational complexity

We introduce a novel graph class we call universal hierarchical graphs (UHG) whose topology can be found numerously in problems representing, e.g., temporal, spacial or general process structures of systems. For this graph class we show, that we can naturally assign two probability distributions, for nodes and for edges, which lead us directly to the definition of the entropy and joint entropy and, hence, mutual information establishing an information theory for this graph class. Furthermore, we provide some results under which conditions these constraint probability distributions maximize the corresponding entropy. Also, we demonstrate that these entropic measures can be computed efficiently which is a prerequisite for every large scale practical application and show some numerical examples. (c) 2007 Elsevier Inc. All rights reserved.

On the spectrum of frequently hypercyclic operators

A bounded linear operator $T$ on a Banach space $X$ is called frequently hypercyclic if there exists $x\in X$ such that the lower density of the set $\{n\in\N:T^nx\in U\}$ is positive for any non-empty open subset $U$ of $X$. Bayart and Grivaux have raised a question whether there is a frequently hypercyclic operator on any separable infinite dimensional Banach space. We prove that the spectrum of a frequently hypercyclic operator has no isolated points. It follows that there are no frequently hypercyclic operators on all complex and on some real hereditarily indecomposable Banach spaces, which provides a negative answer to the above question.

Pointwise universal trigonometric series

A series $S_a=\sum\limits_{n=-\infty}^\infty a_nz^n$ is called a {\it pointwise universal trigonometric series} if for any $f\in C(\T)$, there exists a strictly increasing sequence $\{n_k\}_{k\in\N}$ of positive integers such that $\sum\limits_{j=-n_k}^{n_k} a_jz^j$ converges to $f(z)$ pointwise on $\T$. We find growth conditions on coefficients allowing and forbidding the existence of a pointwise universal trigonometric series. For instance, if $|a_n|=O(\e^{\,|n|\ln^{-1-\epsilon}\!|n|})$ as $|n|\to\infty$ for some $\epsilon>0$, then the series $S_a$ can not be pointwise universal. On the other hand, there exists a pointwise universal trigonometric series $S_a$ with $|a_n|=O(\e^{\,|n|\ln^{-1}\!|n|})$ as $|n|\to\infty$.

A short proof of existence of disjoint hypercyclic operators

We give a short proof of existence of disjoint hypercyclic tuples of operators of any given length on any separable infinite dimensional Fr\'echet space. Similar argument provides disjoint dual hypercyclic tuples of operators of any length on any infinite dimensional Banach space with separable dual.

Dynamic Linear Precoding for the Exploitation of Known Interference in MIMO Broadcast Systems

This paper introduces a novel channel inversion (CI) precoding scheme for the downlink of phase shift keying (PSK)-based multiple input multiple output (MIMO) systems. In contrast to common practice where knowledge of the interference is used to eliminate it, the main idea proposed here is to use this knowledge to glean benefit from the interference. It will be shown that the system performance can be enhanced by exploiting some of the existent inter-channel interference (ICI). This is achieved by applying partial channel inversion such that the constructive part of ICI is preserved and exploited while the destructive part is eliminated by means of CI precoding. By doing so, the effective signal to interference-plus-noise ratio (SINR) delivered to the mobile unit (MU) receivers is enhanced without the need to invest additional transmitted signal power at the MIMO base station (BS). It is shown that the trade-off to this benefit is a minor increase in the complexity of the BS processing. The presented theoretical analysis and simulations demonstrate that due to the SINR enhancement, significant performance and throughput gains are offered by the proposed MIMO precoding technique compared to its conventional counterparts.

A Syntax-based approach to measuring the degree of inconsistency for belief bases

Measuring the degree of inconsistency of a belief base is an important issue in many real world applications. It has been increasingly recognized that deriving syntax sensitive inconsistency measures for a belief base from its minimal inconsistent subsets is a natural way forward. Most of the current proposals along this line do not take the impact of the size of each minimal inconsistent subset into account. However, as illustrated by the well-known Lottery Paradox, as the size of a minimal inconsistent subset increases, the degree of its inconsistency decreases. Another lack in current studies in this area is about the role of free formulas of a belief base in measuring the degree of inconsistency. This has not yet been characterized well. Adding free formulas to a belief base can enlarge the set of consistent subsets of that base. However, consistent subsets of a belief base also have an impact on the syntax sensitive normalized measures of the degree of inconsistency, the reason for this is that each consistent subset can be considered as a distinctive plausible perspective reflected by that belief base,whilst eachminimal inconsistent subset projects a distinctive viewof the inconsistency. To address these two issues,we propose a normalized framework formeasuring the degree of inconsistency of a belief base which unifies the impact of both consistent subsets and minimal inconsistent subsets. We also show that this normalized framework satisfies all the properties deemed necessary by common consent to characterize an intuitively satisfactory measure of the degree of inconsistency for belief bases. Finally, we use a simple but explanatory example in equirements engineering to illustrate the application of the normalized framework.

Structural influence of gene networks on their inference: analysis of C3NET

Background: The availability of large-scale high-throughput data possesses considerable challenges toward their functional analysis. For this reason gene network inference methods gained considerable interest. However, our current knowledge, especially about the influence of the structure of a gene network on its inference, is limited.

Structural similarity of directed universal hierarchical graphs: A low computational complexity approach

In the present paper we mainly introduce an efficient approach to measure the structural similarity of so called directed universal hierarchical graphs. We want to underline that directed universal hierarchical graphs can be obtained from generalized trees which are already introduced. In order to classify these graphs, we state our novel graph similarity method. As a main result we notice that our novel algorithm has low computational complexity. (c) 2007 Elsevier Inc. All rights reserved.

A comparative analysis of multidimensional features of objects resembling sets of graphs

In the present paper, we introduce a notion of a style representing abstract, complex objects having characteristics that can be represented as structured objects. Furthermore, we provide some mathematical properties of such styles. As a main result, we present a novel approach to perform a meaningful comparative analysis of such styles by defining and using graph-theoretic measures. We compare two styles by comparing the underlying feature sets representing sets of graph structurally. To determine the structural similarity between the underlying graphs, we use graph similarity measures that are computationally efficient. More precisely, in order to compare styles, we map each feature set to a so-called median graph and compare the resulting median graphs. As an application, we perform an experimental study to compare special styles representing sets of undirected graphs and present numerical results thereof. (C) 2007 Elsevier Inc. All rights reserved.

Topological mappings between graphs, trees and generalized trees

We present novel topological mappings between graphs, trees and generalized trees that means between structured objects with different properties. The two major contributions of this paper are, first, to clarify the relation between graphs, trees and generalized trees, a graph class recently introduced. Second, these transformations provide a unique opportunity to transform structured objects into a representation that might be beneficial for a processing, e.g., by machine learning techniques for graph classification. (c) 2006 Elsevier Inc. All rights reserved.

Comparing large graphs efficiently by margins of feature vectors

Measuring the structural similarity of graphs is a challenging and outstanding problem. Most of the classical approaches of the so-called exact graph matching methods are based on graph or subgraph isomorphic relations of the underlying graphs. In contrast to these methods in this paper we introduce a novel approach to measure the structural similarity of directed and undirected graphs that is mainly based on margins of feature vectors representing graphs. We introduce novel graph similarity and dissimilarity measures, provide some properties and analyze their algorithmic complexity. We find that the computational complexity of our measures is polynomial in the graph size and, hence, significantly better than classical methods from, e.g. exact graph matching which are NP-complete. Numerically, we provide some examples of our measure and compare the results with the well-known graph edit distance. (c) 2006 Elsevier Inc. All rights reserved.