Search

It is known that the function of a protein is determined by its structure. Thus, structural similarity between proteins plays an important role as a good predictor of functional similarity. Many methods focus on solving the protein structure alignment problem. In this paper, we propose a graph-based approach to measure the similarity of two proteins. We first transfer a protein into a labeled graph according to its secondary structures, chemical properties, and 3D topology. For two graphs, we then find their maximum common edge subgraph for measuring the structural similarity of the corresponding proteins. By using a practical technique, the maximum common edge subgraph of two graphs can be found efficiently. Finally, by a backtracking, we can find the common substructure of the given proteins. Experimental results show that our method outperforms the RMSD method. This graph-based approach provides a practical direction for measuring protein structural similarity. [ABSTRACT FROM AUTHOR]

The minimum vertex ranking spanning tree problem on graph G is to find a spanning tree T of G such that the minimum vertex ranking of T is minimum among all possible spanning trees of G. In this paper, we propose a linear-time algorithm for this problem on permutation graphs. It improves a previous result that runs in O(n3) time where n is the number of vertices in the input graph. [ABSTRACT FROM AUTHOR]

The ]> -width of a class of graphs ]> is defined as follows. A graph G has ]> -width k if there are k independent sets ]> in G such that G can be embedded into a graph ]> such that for every edge e in H which is not an edge in G, there exists an i such that both endpoints of e are in ⇔i. For the class ]> of block graphs we show that ]> -width is NP-complete and we present fixed-parameter algorithms. [ABSTRACT FROM AUTHOR]

Discrimination using genetic diversity provides a significant support in genetic research and applications. Mostly, DNA markers indicate a process of determining the genotype presented at specific locations along the DNA molecule. Some developed DNA marker methods are RFLP, RAPD, AP-PCR, DAF, and AFLP. For these systems, enzymes play an important role. In this paper, we propose a mechanism to verify the enzyme efficacy for pathotyping. A procedure is given to inspect the validation on cleavage pattern by restriction enzymes, adapting the concept of genetic algorithm to quasispecies model – a genetic evolutionary processes of self-replicating macromolecules. The proposed mechanism is applied to viral strains of HPV (Papillomaviridae), including mutated strains from quasispecies model of homozygous, heterozygous, and various genetic variations. In the analysis of full length DNA strain PCR-RFLP subtyping, results showed that if digested patterns of HPV can be discriminated by specific enzyme set from non-high-risk and other papillomavirus, then it is also can be discriminated by the same enzyme set, under the condition of mutated simulation with quasispecies model. In addition, a measure of genetic diversity also evaluates the utility for PCR-RFLP markers in pathotyping, depending on the degree of digestion variation. We provide a specific and valid mechanism of examination on PCR-based pathotyping. Our approach offers a practical and verifiable direction for genomic pathotyping. [ABSTRACT FROM AUTHOR]

The Orthomyxoviridae is a family of single strained RNA viruses including five genera: Influenza virus A, Influenza virus B, Influenza virus C, Thogotovirus, and Isavirus. Usually, Influenza viruses are identified by antigenic differences in their nucleoprotein and matrix protein. In this paper, we propose an algorithm to determine a set of suitable restriction enzymes for producing recognizable restriction maps on Orthomyxoviridae. Our method is applied to viral strains of highly pathogenic avian influenza (HPAI), containing potentially homozygous, heterozygous, and various genetic variations. In the analysis of CAPS (Cleaved Amplified Polymorphic Sequence) subtyping, our method outperforms the RNA coding of representative and epidemiologically significant human wild-type viruses, including H3N8, H5N1, H5N9, H7N1, H7N7, and H9N2. These isolates are analyzed by CAPS with enzymes AgeI, EciI, KpnI, and XbaI. The HPAI strains show a different RFLP (Restriction Fragment Length Polymorphism) profile by comparing with other low pathogenic avian influenza (LPAI) strains. We provide a rapid, specific, and reproducible identification of the genotypes on Orthomyxoviridae. It permits us to quickly confirm subtypes of Orthomyxoviridae. [ABSTRACT FROM AUTHOR]

Given a class of graphs, ]> , a graph G is a probe graph of ]> if its vertices can be partitioned into two sets, ℙ (the probes) and ⇔ (the nonprobes), where ⇔ is an independent set, such that G can be embedded into a graph of ]> by adding edges between certain nonprobes. In this paper we study the probe graphs of ptolemaic graphs when the partition of vertices is unknown. We present some characterizations of probe ptolemaic graphs and show that there exists a polynomial-time recognition algorithm for probe ptolemaic graphs. [ABSTRACT FROM AUTHOR]

Microarray techniques play an important role for testing some reactions of diseases which are caused by viruses. Probes in microarray are one kind of the most important materials. Usually, scientists use a unique probe for marking a special target sequence. Thus, for identifying n different viruses, we need n different probes. Recently, some researchers study non-unique probes to identify viruses by using less number of probes. In this case, a virus can be identified by a combination of some probes. In this paper, we study the problem of finding a set of probes that can identify all the given targets. We consider the k-fault tolerance selection of probes. That is, if any k probes fail, then we still can identify each target. We propose a practical algorithm for this k-fault tolerance probe selection problem. Some experiments are studied on SARS, H5N1, and so on. [ABSTRACT FROM AUTHOR]

High sequence similarity of two proteins does not imply the relation in their structural similarity. In this paper, we propose a protein secondary structure prediction method based on Ramachandran maps. According to the distribution of Ramachandran plot on φ and ψ backbone conformational angles, the series of backbone dihedral angles are regarded as a sequence of input states. Individual residues are classified into different secondary structures. In one of our results, protein hemoglobin 1A6M aligns 2FAM sequence sharing 11.74% similarity. However, 1A6M shares 81.82% of the common structure with 2FAM. Results display that our proposed method provides a promotive advantage on protein secondary structure prediction, without depending on sequence similarity. [ABSTRACT FROM AUTHOR]

A vertex ranking of a graph G is a labeling of the vertices of G with positive integers such that every path between two vertices with the same label i contains a vertex with label j > i. A vertex ranking is minimum if the largest label used in it is the smallest among all possible vertex rankings of G. The minimum vertex ranking spanning tree problem on G is to find a spanning tree T of G such that the minimum vertex ranking of T is minimum among all possible spanning trees of G. In this paper, we show that the minimum vertex ranking spanning tree problem on interval graphs, split graphs, and cographs can be solved in linear time. It improves a previous result that runs in O(n3) time on interval graphs where n is the number of vertices in the input graph. [ABSTRACT FROM AUTHOR]

In this paper we explore the biclique structure of a biconvex bipartite graph G. We define two concatenation operators on bicliques of G. According to these operations, we show that G can be decomposed into two chain graphs GL and GR, and a bipartite permutation graph GP. Using this representation, we propose linear-time algorithms for the treewidth and pathwidth problems on biconvex bipartite graphs. [ABSTRACT FROM AUTHOR]

In this paper we consider the recognition of some probe graph classes. Given a class of graphs $\mathcal{G}$, a graph G is a probe graph of $\mathcal{G}$ if its vertices can be partitioned into a set $\mathbb{P}$ of probes and an independent set $\mathbb{N}$ of nonprobes, such that G can be extended to a graph of $\mathcal{G}$ by adding edges between certain nonprobes. We show that there are polynomial-time recognition algorithms for probe cographs, probe P4-reducible graphs, probe P4-sparse graphs, and probe splitgraphs. [ABSTRACT FROM AUTHOR]