✦ LIBER ✦

Computational complexity of inferring phylogenies from dissimilarity matrices

✍ Scribed by William H.E. Day

Publisher: Springer
Year: 1987
Tongue: English
Weight: 439 KB
Volume: 49
Category: Article
ISSN: 1522-9602
DOI: 10.1016/s0092-8240(87)80007-1

No coin nor oath required. For personal study only.

✦ Synopsis

Molecular biologists strive to infer evolutionary relationships from quantitative macromolecular comparisons obtained by immunological, DNA hybridization, electrophoretic or amino acid sequencing techniques. The problem is to find unrooted phylogenies that best approximate a given dissimilarity matrix according to a goodness-of-fit measure, for example the least-squaresfit criterion or Farris's f statistic. Computational costs of known algorithms guaranteeing optimal solutions to these problems increase exponentially with problem size; practical computational considerations limit the algorithms to analyzing small problems. It is established here that problems of phylogenetic inference based on the least-squares-fit criterion and thef statistic are NP-complete and thus are so difficult computationally that efficient optimal algorithms are unlikely to exist for them.

📜 SIMILAR VOLUMES

Phylogeny of Cephalopods Inferred from M

Phylogeny of Cephalopods Inferred from Mitochondrial DNA Sequences

✍ Laure Bonnaud; Renata Boucher-Rodoni; Monique Monnerot 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 213 KB

## Sequences of partial mitochondrial cytochrome oxidase III gene (533 bp) were obtained for 17 species of cephalopods, 14 decapods, 2 octopods, and 1 vampyromorph. This study aimed to: (1) compare partial COII and COIII amino acid sequences of three species of cephalopods with other invertebrates

A Phylogeny of Freshwater Eels Inferred

A Phylogeny of Freshwater Eels Inferred from Mitochondrial Genes

✍ Yeong-Shin Lin; Yu-Ping Poh; Chyng-Shyan Tzeng 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 319 KB

The genus Anguilla Shaw of Family Anguillidae consists entirely of freshwater eels, including 15 species and 2 subspecies. Conventionally, variegated markings and the length of the dorsal fin are the major morphological features used for reconstruction of phylogenetic relationships. The evolutionary

The computational complexity of Steiner

The computational complexity of Steiner tree problems in graded matrices

✍ T. Dudás; B. Klinz; G.J. Woeginger 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 349 KB

## Communicated by M. Iri Abstract--We investigate the computational complexity of the Steiner tree problem in graphs when the distance matrix is graded, i.e., has increasing, respectively, decreasing rows, or increasing, respectively, decreasing columns, or both. We exactly characterize polynomia

Details of Gastropod Phylogeny Inferred

Details of Gastropod Phylogeny Inferred from 18S rRNA Sequences

✍ Birgitta Winnepenninckx; Gerhard Steiner; Thierry Backeljau; Rupert De Wachter 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 154 KB

Some generally accepted viewpoints on the phylogenetic relationships within the molluscan class Gastropoda are reassessed by comparing complete 18S rRNA sequences. Phylogenetic analyses were performed using the neighbor-joining and maximum parsimony methods. The previously suggested basal position o

Patterns of nucleotide substitutions inf

Patterns of nucleotide substitutions inferred from the phylogenies of the class I major histocompatibility complex genes

✍ Tadashi Imanishi; Takashi Gojobori 📂 Article 📅 1992 🏛 Springer 🌐 English ⚖ 923 KB

Patterns of nucleotide substitutions in human major histocompatibility complex (MHC) class I genes were estimated by using phylogenetic trees of DNA sequences. The pattern is defined as a set of 12 parameters, each of which represents the relative frequency of substitutions from a particular nucleot

Phylogeny of Cryptocercus Species (Blatt

Phylogeny of Cryptocercus Species (Blattodea: Cryptocercidae) Inferred from Nuclear Ribosomal DNA

✍ Shaon Hossain; Srinivas Kambhampati 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 56 KB

The wood-feeding cockroaches of the genus Cryptocercus occur in temperate forests. Of the seven known species, five occur in the United States and two in Eurasia. Until 1997, all populations in the United States were considered a single species. Populations in the western United States were elevated