Iterative pass optimization of sequence data

Wheeler, Ward C.

Home/Archive/NASA NTRS

NASA NTRS · 20040087570

Iterative pass optimization of sequence data

Wheeler, Ward C.

View original source ↗Export metadata ↓

Abstract

The problem of determining the minimum-cost hypothetical ancestral sequences for a given cladogram is known to be NP-complete. This "tree alignment" problem has motivated the considerable effort placed in multiple sequence alignment procedures. Wheeler in 1996 proposed a heuristic method, direct optimization, to calculate cladogram costs without the intervention of multiple sequence alignment. This method, though more efficient in time and more effective in cladogram length than many alignment-based procedures, greedily optimizes nodes based on descendent information only. In their proposal of an exact multiple alignment solution, Sankoff et al. in 1976 described a heuristic procedure--the iterative improvement method--to create alignments at internal nodes by solving a series of median problems. The combination of a three-sequence direct optimization with iterative improvement and a branch-length-based cladogram cost procedure, provides an algorithm that frequently results in superior (i.e., lower) cladogram costs. This iterative pass optimization is both computation and memory intensive, but economies can be made to reduce this burden. An example in arthropod systematics is discussed. c2003 The Willi Hennig Society. Published by Elsevier Science (USA). All rights reserved.

Explore related subjects

NASA Discipline Evolutionary Biology Non-NASA Center Evolution Arthropods/classification/genetics Sequence Alignment/methods Sequence Homology Molecular Sequence Data Animals Algorithms Phylogeny Support, U.S. Gov't, Non-P.H.S

Keep this discovery

Explore connections, maps & timelines

BibTeX RIS

Wheeler, Ward C.. 2003-06-01. Iterative pass optimization of sequence data. https://ntrs.nasa.gov/citations/20040087570

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related reports

NASA NTRS2005

Origin of the Eumetazoa: testing ecological predictions of molecular clocks against the Proterozoic fossil record

Molecular clocks have the potential to shed light on the timing of early metazoan divergences, but differing algorithms and calibration points yield conspicuously discordant results. We argue here that competing molecular clock hypotheses should be testable in the fossil record, on the principle that fundamentally new grades of animal organization will have ecosystem-wide impacts. Using a set of seven nuclear-encoded protein sequences, we demonstrate the paraphyly of Porifera and calculate sponge/eumetazoan and cnidarian/bilaterian divergence times by using both distance [minimum evolution (ME)] and maximum likelihood (ML) molecular clocks; ME brackets the appearance of Eumetazoa between 634 and 604 Ma, whereas ML suggests it was between 867 and 748 Ma. Significantly, the ME, but not the ML, estimate is coincident with a major regime change in the Proterozoic acritarch record, including: (i) disappearance of low-diversity, evolutionarily static, pre-Ediacaran acanthomorphs; (ii) radiation of the high-diversity, short-lived Doushantuo-Pertatataka microbiota; and (iii) an order-of-magnitude increase in evolutionary turnover rate. We interpret this turnover as a consequence of the novel ecological challenges accompanying the evolution of the eumetazoan nervous system and gut. Thus, the more readily preserved microfossil record provides positive evidence for the absence of pre-Ediacaran eumetazoans and strongly supports the veracity, and therefore more general application, of the ME molecular clock.

NASA Discipline Evolutionary Biology↗

NASA NTRS2003

An ancient role for nuclear beta-catenin in the evolution of axial polarity and germ layer segregation

The human oncogene beta-catenin is a bifunctional protein with critical roles in both cell adhesion and transcriptional regulation in the Wnt pathway. Wnt/beta-catenin signalling has been implicated in developmental processes as diverse as elaboration of embryonic polarity, formation of germ layers, neural patterning, spindle orientation and gap junction communication, but the ancestral function of beta-catenin remains unclear. In many animal embryos, activation of beta-catenin signalling occurs in blastomeres that mark the site of gastrulation and endomesoderm formation, raising the possibility that asymmetric activation of beta-catenin signalling specified embryonic polarity and segregated germ layers in the common ancestor of bilaterally symmetrical animals. To test whether nuclear translocation of beta-catenin is involved in axial identity and/or germ layer formation in 'pre-bilaterians', we examined the in vivo distribution, stability and function of beta-catenin protein in embryos of the sea anemone Nematostella vectensis (Cnidaria, Anthozoa). Here we show that N. vectensis beta-catenin is differentially stabilized along the oral-aboral axis, translocated into nuclei in cells at the site of gastrulation and used to specify entoderm, indicating an evolutionarily ancient role for this protein in early pattern formation.

NASA Discipline Evolutionary Biology↗

NASA NTRS2003

Conservation of Endo16 expression in sea urchins despite evolutionary divergence in both cis and trans-acting components of transcriptional regulation

Evolutionary changes in transcriptional regulation undoubtedly play an important role in creating morphological diversity. However, there is little information about the evolutionary dynamics of cis-regulatory sequences. This study examines the functional consequence of evolutionary changes in the Endo16 promoter of sea urchins. The Endo16 gene encodes a large extracellular protein that is expressed in the endoderm and may play a role in cell adhesion. Its promoter has been characterized in exceptional detail in the purple sea urchin, Strongylocentrotus purpuratus. We have characterized the structure and function of the Endo16 promoter from a second sea urchin species, Lytechinus variegatus. The Endo16 promoter sequences have evolved in a strongly mosaic manner since these species diverged approximately 35 million years ago: the most proximal region (module A) is conserved, but the remaining modules (B-G) are unalignable. Despite extensive divergence in promoter sequences, the pattern of Endo16 transcription is largely conserved during embryonic and larval development. Transient expression assays demonstrate that 2.2 kb of upstream sequence in either species is sufficient to drive GFP reporter expression that correctly mimics this pattern of Endo16 transcription. Reciprocal cross-species transient expression assays imply that changes have also evolved in the set of transcription factors that interact with the Endo16 promoter. Taken together, these results suggest that stabilizing selection on the transcriptional output may have operated to maintain a similar pattern of Endo16 expression in S. purpuratus and L. variegatus, despite dramatic divergence in promoter sequence and mechanisms of transcriptional regulation.

NASA Discipline Evolutionary Biology↗