Engineering topics

Wheeler, Ward C.

Publications and source records attributed to Wheeler, Ward C..

4 records

NASA NTRS2003

Search-based optimization

The problem of determining the minimum cost hypothetical ancestral sequences for a given cladogram is known to be NP-complete (Wang and Jiang, 1994). Traditionally, point estimations of hypothetical ancestral sequences have been used to gain heuristic, upper bounds on cladogram cost. These include procedures with such diverse approaches as non-additive optimization of multiple sequence alignment, direct optimization (Wheeler, 1996), and fixed-state character optimization (Wheeler, 1999). A method is proposed here which, by extending fixed-state character optimization, replaces the estimation process with a search. This form of optimization examines a diversity of potential state solutions for cost-efficient hypothetical ancestral sequences and can result in greatly more parsimonious cladograms. Additionally, such an approach can be applied to other NP-complete phylogenetic optimization problems such as genomic break-point analysis. c2003 The Willi Hennig Society. Published by Elsevier Science (USA). All rights reserved.

Non-NASA Center↗

NASA NTRS2003

Implied alignment: a synapomorphy-based multiple-sequence alignment method and its use in cladogram search

A method to align sequence data based on parsimonious synapomorphy schemes generated by direct optimization (DO; earlier termed optimization alignment) is proposed. DO directly diagnoses sequence data on cladograms without an intervening multiple-alignment step, thereby creating topology-specific, dynamic homology statements. Hence, no multiple-alignment is required to generate cladograms. Unlike general and globally optimal multiple-alignment procedures, the method described here, implied alignment (IA), takes these dynamic homologies and traces them back through a single cladogram, linking the unaligned sequence positions in the terminal taxa via DO transformation series. These "lines of correspondence" link ancestor-descendent states and, when displayed as linearly arrayed columns without hypothetical ancestors, are largely indistinguishable from standard multiple alignment. Since this method is based on synapomorphy, the treatment of certain classes of insertion-deletion (indel) events may be different from that of other alignment procedures. As with all alignment methods, results are dependent on parameter assumptions such as indel cost and transversion:transition ratios. Such an IA could be used as a basis for phylogenetic search, but this would be questionable since the homologies derived from the implied alignment depend on its natal cladogram and any variance, between DO and IA + Search, due to heuristic approach. The utility of this procedure in heuristic cladogram searches using DO and the improvement of heuristic cladogram cost calculations are discussed. c2003 The Willi Hennig Society. Published by Elsevier Science (USA). All rights reserved.

Non-NASA Center↗

NASA NTRS2003

Iterative pass optimization of sequence data

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.

NASA Discipline Evolutionary Biology↗

NASA NTRS2002

Phylogeny and systematic position of Opiliones: a combined analysis of chelicerate relationships using morphological and molecular data

The ordinal level phylogeny of the Arachnida and the suprafamilial level phylogeny of the Opiliones were studied on the basis of a combined analysis of 253 morphological characters, the complete sequence of the 18S rRNA gene, and the D3 region of the 28S rRNA gene. Molecular data were collected for 63 terminal taxa. Morphological data were collected for 35 exemplar taxa of Opiliones, but groundplans were applied to some of the remaining chelicerate groups. Six extinct terminals, including Paleozoic scorpions, are scored for morphological characters. The data were analyzed using strict parsimony for the morphological data matrix and via direct optimization for the molecular and combined data matrices. A sensitivity analysis of 15 parameter sets was undertaken, and character congruence was used as the optimality criterion to choose among competing hypotheses. The results obtained are unstable for the high-level chelicerate relationships (except for Tetrapulmonata, Pedipalpi, and Camarostomata), and the sister group of the Opiliones is not clearly established, although the monophyly of Dromopoda is supported under many parameter sets. However, the internal phylogeny of the Opiliones is robust to parameter choice and allows the discarding of previous hypotheses of opilionid phylogeny such as the "Cyphopalpatores" or "Palpatores." The topology obtained is congruent with the previous hypothesis of "Palpatores" paraphyly as follows: (Cyphophthalmi (Eupnoi (Dyspnoi + Laniatores))). Resolution within the Eupnoi, Dyspnoi, and Laniatores (the latter two united as Dyspnolaniatores nov.) is also stable to the superfamily level, permitting a new classification system for the Opiliones. c2002 The Willi Hennig Society.

NASA Discipline Evolutionary Biology↗