Search

Rich club is a special phenomenon in complex networks. It refers to the nodes with high degrees (i.e., rich nodes) that tend to connect with each other to form a "rich club". This phenomenon exists in many real networks, especially in social networks. However, there are also some networks not having this phenomenon, for example, in many biological networks. Thus, a natural question comes up: do these rich nodes contact with each other through an "agent"? Two rich nodes do not connect directly, but they can establish a connection by an "agent", i.e., they can connect with each other within two steps. If the rich nodes tend to connect with each other within two steps, we say that they form a "2-step rich club". The traditional rich club is then called "1-step rich club". In this paper, we aim to design one method to detect the "2-step rich club" phenomenon in real networks and check whether this new "2-step rich club" phenomenon commonly exists in real networks. We find that most networks with "1-step rich club" will also have "2-step rich club". However, there also exist few networks having "2-step rich club" structure while not having "1-step rich club" structure. In particular, either 1-step rich-club phenomenon or 2-step rich-club phenomenon exists in most social networks. [ABSTRACT FROM AUTHOR]

Byline: Xingqin Qi, Jichang Wu, Shuguang Li, Guojun Li For the first time, we study the sorting of permutations by length-weighted transpositions under a wide class of cost functions, namely f(l)=lα, where l is the length of the transposition. For different α, we give corresponding upper and lower bounds of the cost of sorting any binary sequences or any permutations. Furthermore, an O(log n) approximation algorithm and an exact algorithm are given to determine the optimal transposition series of sorting a permutation of length n when 1 < α < 2 and α ≥ 2 respectively. Our work poses some interesting questions to both biologists and computer scientists and suggests some new bioinformatic insights that are currently being studied.

Within graph theory and network analysis, centrality of a vertex measures the relative importance of a vertex within a graph. The centrality plays key role in network analysis and has been widely studied using different methods. Inspired by the idea of vertex centrality, a novel centrality guided clustering (CGC) is proposed in this paper. Different from traditional clustering methods which usually choose the initial center of a cluster randomly, the CGC clustering algorithm starts from a "LEADER"--a vertex with the highest centrality score--and a new "member" is added into the same cluster as the "LEADER" when some criterion is satisfied. The CGC algorithm also supports overlapping membership. Experiments on three benchmark social network data sets are presented and the results indicate that the proposed CGC algorithm works well in social network clustering.

Sequence comparison is a primary technique for the analysis of DNA sequences. In order to make quantitative comparisons, one devises mathematical descriptors that capture the essence of the base composition and distribution of the sequence. Alignment methods and graphical techniques (where each sequence is represented by a curve in high-dimension Euclidean space) have been used popularly for a long time. In this contribution we will introduce a new nongraphical and nonalignment approach based on the frequencies of the dinucleotide XY in DNA sequences. The most important feature of this method is that it not only identifies adjacent XY pairs but also nonadjacent XY ones where X and Y are separated by some number of nucleotides. This methodology preserves information in DNA sequence that is ignored by other methods. We test our method on the coding regions of exon-1 of β-globin for 11 species, and the utility of this new method is demonstrated.

The problem of sorting by reciprocal translocations (abbreviated as SBT) arises from the field of comparative genomics, which is to find a shortest sequence of reciprocal translocations that transforms one genome Pi into another genome Gamma, with the restriction that Pi and Gamma contain the same genes. SBT has been proved to be polynomial-time solvable, and several polynomial algorithms have been developed. In this paper, we show how to extend Bergeron's SBT algorithm to include insertions and deletions, allowing to compare genomes containing different genes. In particular, if the gene set of Pi is a subset (or superset, respectively) of the gene set of Gamma, we present an approximation algorithm for transforming Pi into Gamma by reciprocal translocations and deletions (insertions, respectively), providing a sorting sequence with length at most OPT + 2, where OPT is the minimum number of translocations and deletions (insertions, respectively) needed to transform Pi into Gamma; if Pi and Gamma have different genes but not containing each other, we give a heuristic to transform Pi into Gamma by a shortest sequence of reciprocal translocations, insertions, and deletions, with bounds for the length of the sorting sequence it outputs. At a conceptual level, there is some similarity between our algorithm and the algorithm developed by El Mabrouk which is used to sort two chromosomes with different gene contents by reversals, insertions, and deletions.