(1) Department of Mathematics, Iowa State University, Ames, IA 50011.
(2) Department of Computer Science, Iowa State University, Ames, IA 50011.
The quality of the alignments obtained by sequence comparison programs depends heavily on parameters such as the score of a match, and the mismatch, gap, and gap extension penalties (3). In an attempt to address the uncertainty surrounding the choice of these values, parametric sequence alignment obtains optimum solutions across whole ranges of values. The result of parametric analysis is a decomposition of the space of all parameter values into a finite set of regions, within each of which the cost function is unique. By examining this decomposition and the alignments associated with the various regions, researchers can visually determine the best parameter choices for their applications.
Previous researchers have devised tools for constructing and visualizing the decomposition and for one- and two-parameter problems (7, 4, 8), but, to our knowledge, no one has addressed the problems arising in studying the effects of simultaneously varying three or more parameters. We shall present an efficient and numerically stable program for the analysis of three or more parameter problems. The construction of the decomposition extends earlier work (2), and relies on ideas developed for state-of-the-art geometric software (1). The program allows visualization of the results either through conventional web browsers, using VRML (6), or through the more sophisticated capabilities of Geomview (5).
Bibliography
[1] C.B. Barber, D.P. Dobkin, and H.Huhdanpaa. The quickhull algorithm for convex hulls. ACM Trans. on Mathematical Software, 22(4):469--483, 1996.
[2] David Fernandez-Baca and S.Srinivasan. Constructing the minimization diagram of a two-parameter problem. Operations Research Letters, 10:87--93, 1991.
[3] Walter M. Fitch and Temple F. Smith. Optimal sequence alignments. Proc. Natl. Acad. Sci. USA, 80:1382--1386, 1983.
[4] Dan Gusfield and Paul Stelling. Parametric and inverse-parametric sequence alignment with XPARAL volume 266 of Methods in Enzymology, pages 481--494. Academic Press, 1996.
[5] The Center for Computation and Visualization of Geometric Structures, Geomview, 1996. http://freeabel.geom.umn.edu/software/download/geomview.html
[6] The VRML consortium, VRML specification, http://www.vrml.org, 1997.
[7] Michael S. Waterman, M. Eggert, and Eric Lander. Parametric sequence comparisons. Proc. Natl. Acad. Sci. USA, 89:6090--6093, 1992.
[8] R. Zimmer and Th. Lengauer. Fast and numerically stable parametric alignment of biosequences. Proceedings of RECOMB 97, Santa Fe, NM}, pages 344--353. ACM Press,1997.
Notes:
(*) Supported in part by the National Science Foundation under an REU supplement to grant CCR-9520946 (amendment 3). E-mail address: bolson@cs.iastate.edu
(**) Supported in part by the National Science Foundation under grant CCR-9520946. E-mail address: fernande@cs.iastate.edu