We show that two important problems that have applications in computational biology are ASP-complete, which implies that, given a solution to a problem, it is NP-complete to decide if another solution exists. We show first that a variation of BETWEENNESS, which is the underlying problem of questions related to radiation hybrid mapping, is ASP-complete. Subsequently, we use that result to show that QUARTET COMPATIBILITY, a fundamental problem in phylogenetics that asks whether a set of quartets can be represented by a parent tree, is also ASP-complete. The latter result shows that Steel’s QUARTET CHALLENGE, which asks whether a solution to QUARTET COMPATIBILITY is unique, is coNP-complete.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1109/TCBB.2011.108 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
The influence of G-tract and loop length on the topological variability of putative five and six G-quartet DNA structures in the human genome.
Int J Biol Macromol
September 2024
Slovenian NMR Center, National Institute of Chemistry, Hajdrihova 19, SI-1000 Ljubljana, Slovenia. Electronic address:
Local variation of DNA structure and its dynamic nature play an essential role in the regulation of important biological processes. One of the most prominent noncanonical structures are G-quadruplexes, which form in vivo within guanine-rich regions and have been demonstrated to be involved in the regulation of transcription, translation and telomere maintenance. We provide an analysis of G-quadruplex formation in sequences with five and six guanine residues long G-tracts, which have emerged from the investigation of the gapless human genome and are associated with genes related to cancer and neurodegenerative diseases.
View Article and Find Full Text PDFLibERI-A portable and performant multi-GPU accelerated library for electron repulsion integrals via OpenMP offloading and standard language parallelism.
J Chem Phys
August 2024
Department of Chemistry, Iowa State University and Ames National Laboratory, Ames, Iowa 50011, USA.
A portable and performant graphics processing unit (GPU)-accelerated library for electron repulsion integral (ERI) evaluation, named LibERI, has been developed and implemented via directive-based (e.g., OpenMP and OpenACC) and standard language parallelism (e.
View Article and Find Full Text PDFDevelopment and Evaluation of a Flexible PVDF-Based Balloon Sensor for Detecting Mechanical Forces at Key Esophageal Nodes in Esophageal Motility Disorders.
Biosensors (Basel)
August 2023
Chongqing Engineering Research Center of Medical Electronics and Information Technology, Chongqing 400065, China.
Prevailing methods for esophageal motility assessments, such as perfusion manometry and probe-based function imaging, frequently overlook the intricate stress fields acting on the liquid-filled balloons at the forefront of the probing device within the esophageal lumen. To bridge this knowledge gap, we innovatively devised an infusible flexible balloon catheter, equipped with a quartet of PVDF piezoelectric sensors. This design, working in concert with a bespoke local key-node analytical algorithm and a sensor array state analysis model, seeks to shed new light on the dynamic mechanical characteristics at pivotal esophageal locales.
View Article and Find Full Text PDFG-Quadruplex Formation by DNA Sequences Deficient in Guanines: Two Tetrad Parallel Quadruplexes Do Not Fold Intramolecularly.
Chemistry
August 2021
Institute of Biophysics of the Czech Academy of Sciences, Královopolská 135, 612 65, Brno, Czech Republic.
Guanine quadruplexes (G4s) are noncanonical forms of nucleic acids that are frequently found in genomes. The stability of G4s depends, among other factors, on the number of G-tetrads. Three- or four-tetrad G4s and antiparallel two-tetrad G4s have been characterized experimentally; however, the existence of an intramolecular (i.
View Article and Find Full Text PDFmixIndependR: a R package for statistical independence testing of loci in database of multi-locus genotypes.
BMC Bioinformatics
January 2021
Department of Microbiology, Immunology and Genetics, University of North Texas Health Science Center, 3500 Camp Bowie Blvd, Fort Worth, TX, 76107, USA.
Background: Multi-locus genotype data are widely used in population genetics and disease studies. In evaluating the utility of multi-locus data, the independence of markers is commonly considered in many genomic assessments. Generally, pairwise non-random associations are tested by linkage disequilibrium; however, the dependence of one panel might be triplet, quartet, or other.
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!