Maximum common subgraph: some upper bound and lower bound results.

Maximum common subgraph: some upper bound and lower bound results. Research Abstract Details 

Research Abstract Table of Contents

Jump to the:

Maximum common subgraph: some upper bound and lower bound results. Abstract Text:

Xiuzhen Huang,Jing Lai,Steven F Jennings,

BACKGROUND: Structure matching plays an important part in understanding the functional role of biological structures. Bioinformatics assists in this effort by reformulating this process into a problem of finding a maximum common subgraph between graphical representations of these structures. Among the many different variants of the maximum common subgraph problem, the maximum common induced subgraph of two graphs is of special interest. RESULTS: Based on current research in the area of parameterized computation, we derive a new lower bound for the exact algorithms of the maximum common induced subgraph of two graphs which is the best currently known. Then we investigate the upper bound and design techniques for approaching this problem, specifically, reducing it to one of finding a maximum clique in the product graph of the two given graphs. Considering the upper bound result, the derived lower bound result is asymptotically tight. CONCLUSION: Parameterized computation is a viable approach with great potential for investigating many applications within bioinformatics, such as the maximum common subgraph problem studied in this paper. With an improved hardness result and the proposed approaches in this paper, future research can be focused on further exploration of efficient approaches for different variants of this problem within the constraints imposed by real applications.

Maximum common subgraph: some upper bound and lower bound results. Publishing Authors By Initials

X Huang,J Lai,SF Jennings,

For similar investigative techniques: genetic techniques: sequence analysis research abstracts see: investigative techniques: genetic techniques: sequence analysis research

PUBMED ID PMID:

MEDLINE DATE:

Maximum common subgraph: some upper bound and lower bound results. Journal Published:

PUBLICATION TYPE: Research Support, N.I.H., Extr

Journal: BMC bioinformatics

VOLUME: 7 Suppl 4

Page Numbers: S6

Journal Abbreviation: BMC Bioinformatics

ISSN: 1471-2105

DAY: 12

MONTH: 12

YEAR: 2006

Maximum common subgraph: some upper bound and lower bound results. Information

Number of References:

LANGUAGE: eng

NlmUniqueID: 100965194

Maximum common subgraph: some upper bound and lower bound results. Keywords Mesh Terms:

KEYWORDS: Sequence Analysis

MESH TERMS: methods

Chemical & Substance for Abstract: Maximum common subgraph: some upper bound and lower bound results. Information

Substance Name: Biopolymers

Registry Number: 0

Grant and Affiliation Information for Maximum common subgraph: some upper bound and lower bound results.

AFFILIATION: Department of Computer Science, Arkansas State University, State University, Arkansas 72467, USA. xzhuang@csm.astate.edu

Country: England

AGENCY: United States NCRR

GRANT: P20 RR-16460

ACRONYM: RR

MEDLINETA: BMC Bioinformatics

REFSOURCE:

DATABASENAME:

ACCESSION NUMBER:

Number Hits: 0

Maximum common subgraph: some upper bound and lower bound results Related Publications

• A Highly Stereoselective TMSOTf-Mediated Catalytic Carbocupration of Alkynoates.
• A bacteriologic survey of the reproductive tract of infertile cows.
• A case of an isolated gastric variceal bleed secondary to a pancreatic neuroendocrine tumour.
• A novel disulfide bond in the SH2 Domain of the C-terminal Src kinase controls catalytic activity.
• Amino acid sequence of a ferredoxin from Chlorobium thiosulfatophilum strain Tassajara, a photosynthetic green sulfur bacterium.
• An advanced solventless column test for capillary GC columns.
• Brucellosis: Consideration of Its Epidemiology, Diagnosis and Control.
• Characterization of the OxyR regulon of Neisseria gonorrhoeae.
• Chlorophyll ring deformation modulates Qy electronic energy in chlorophyll-protein complexes and generates spectral forms.
• Data briefing. Efficiency efforts begin to pay off.
• Growth and structure of surface-initiated poly(n-alkylnorbornene) films.
• Haemophilus influenzae phasevarions have evolved from type III DNA restriction systems into epigenetic regulators of gene expression.
• Inflammatory cytokines induce MAdCAM-1 in murine hepatic endothelial cells and mediate alpha-4 beta-7 integrin dependent lymphocyte endothelial adhesion in vitro.
• Kinetics of pH response for copolymer films with dilute carboxylate functionality.
• Localization of P2X2 and P2X3 receptors in rat trigeminal ganglion neurons.
• MR cholangiopancreatography in children: feasibility, safety, and initial experience.
• Maximum common subgraph: some upper bound and lower bound results.
• MitoNEET is a uniquely folded 2Fe 2S outer mitochondrial membrane protein stabilized by pioglitazone.
• New directions in nursing home ethics.
• Peritoneal dialysis catheters: laparoscopic versus traditional placement techniques and outcomes.
• Phase variable type III restriction-modification systems of host-adapted bacterial pathogens.
• Protective effects of exercise and phosphoinositide 3-kinase(p110alpha) signaling in dilated and hypertrophic cardiomyopathy.
• Public Health Engineering: The Practical Application of Milk Control.
• Resistance to arranged marriage among Nubian youth: ideology and changing times.
• Secretory signal sequence non-optimal codons are required for expression and export of beta-lactamase.
• The most wonderful organ-not!
• The rough energy landscape of superfolder GFP is linked to the chromophore.
• Thromboembolism; prophylaxis and treatment.
• Transferred NOE and saturation transfer difference NMR studies of novobiocin binding to EnvZ suggest binding mode similar to DNA gyrase.
• [2]Pseudorotaxane and [2]rotaxane molecular shuttles: self-assembly through second-sphere coordination of thiocyanate ligands.