DIMACS s Series in Discrete Mathematics and Theoretical Computer Science Volume 47 Mathematical Support for Molecular Biology Papers Related to the Special Year in Mathematical Support for Molecular Biology 1994-1998 Martin Farach-Colton Fred S. Roberts Martin Vingron Michael Waterman Editors American Mathematical Society Digitized by the Internet Archive in 2019 with funding from Kahle/Austin Foundation https://archive.org/details/mathematicalsupp0047unse Selected Titles in This Series 47 Martin Farach-Colton, Fred S. Roberts, Martin Vingron, and Michael Waterman, Editors, Mathematical Support for Molecular Biology 46 Peng-Jun Wan, Ding-Zhu Du, and Panos M. Pardalos, Editors, Multichannel Optical Networks: Theory and Practice 45 Marios Mavronicolas, Michael Merritt, and Nir Shavit, Editors, Networks in Distributed Computing 44 Laura F. Landweber and Eric B. Baum, Editors, DNA Based Computers II 43 Panos Pardalos, Sanguthevar Rajasekaran, and Jose Rohm, Editors, Randomization Methods in Algorithm Design 42 Ding-Zhu Du and Frank K. Hwang, Editors, Advances in Switching Networks 41 David Aldous and James Propp, Editors, Microsurveys in Discrete Probability 40 Panos M. Pardalos and Dingzhu Du, Editors, Network Design: Connectivity and Facilities Location 39 Paul W. Beame and Samuel R Buss, Editors, Proof Complexity and Feasible Arithmetics 38 Rebecca N. Wright and Peter G. Neumann, Editors, Network Threats 37 Boris Mirkin, F. R. McMorris, Fred S. Roberts, and Andrey Rzhetsky, Editors, Mathematical Hierarchies and Biology 36 Joseph G. Rosenstein, Deborah S. Franzblau, and Fred S. Roberts, Editors, Discrete Mathematics in the Schools 35 Dingzhu Du, Jun Gu, and Panos M. Pardalos, Editors, Satisfiability Problem: Theory and Applications 34 Nathaniel Dean, Editor, African Americans in Mathematics 33 Ravi B. Boppana and James F. Lynch, Editors, Logic and Random Structures 32 Jean-Charles Gregoire, Gerard J. Holzmann, and Doron A. Peled, Editors, The Spin Verification System 31 Neil Immerman and Phokion G. Kolaitis, Editors, Descriptive Complexity and Finite Models 30 Sandeep N. Bhatt, Editor, Parallel Algorithms: Third DIMACS Implementation Challenge 29 Doron A. Peled, Vaughan R. Pratt, and Gerard J. Holzmann, Editors, Partial Order Methods in Verification 28 Larry Finkelstein and William M. Kantor, Editors, Groups and Computation II 27 Richard J. Lipton and Eric B. Baum, Editors, DNA Based Computers 26 David S. Johnson and Michael A. Trick, Editors, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge 25 Gilbert Baumslag, David Epstein, Robert Gilman, Hamish Short, and Charles Sims, Editors, Geometric and Computational Perspectives on Infinite Groups 24 Louis J. Billera, Curtis Greene, Rodica Simion, and Richard P. Stanley, Editors, Formal Power Series and Algebraic Combinatorics/Series Formelles et Combinatoire Algebrique, 1994 23 Panos M. Pardalos, David I. Shalloway, and Guoliang Xue, Editors, Global Minimization of Nonconvex Energy Functions: Molecular Conformation and Protein Folding 22 Panos M. Pardalos, Mauricio G. C. Resende, and K. G. Ramakrishnan, Editors, Parallel Processing of Discrete Optimization Problems 21 D. Frank Hsu, Arnold L. Rosenberg, and Dominique Sotteau, Editors, Interconnection Networks and Mapping and Scheduling Parallel Computations 20 William Cook, Laszlo Lovasz, and Paul Seymour, Editors, Combinatorial Optimization 19 Ingemar J. Cox, Pierre Hansen, and Bela Julesz, Editors, Partitioning Data Sets (See the AMS catalog for earlier titles) % \ DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 47 Mathematical Support for Molecular Biology Papers Related to the Special Year in Mathematical Support for Molecular Biology 1994-1998 Martin Farach-Colton Fred S. Roberts Martin Vingron Michael Waterman Editors NSF Science and Technology Center in Discrete Mathematics and Theoretical Computer Science A consortium of Rutgers University, Princeton University, AT&T Labs, Bell Labs, Bellcore, and NEC Research Institute American Mathematical Society J. Thomas Bata Library TRENT UNIVERSITY PETERBOROUGH, ONTARIO <3 V > Ob ^ oCX V 0s ChOs *s This DIMACS volume contains papers related to the 1994-1998 “Special Year” in Mathematical Support for Molecular Biology. 1991 Mathematics Subject Classification. Primary 92Bxx, 05-xx, 05Cxx. Library of Congress Cataloging-in-Publication Data DIMACS “Special Year” in Mathematical Support for Molecular Biology (1994-1998) Mathematical support for molecular biology : papers related to the special year in mathematical support for molecular biology 1994-1998 / Martin Farach-Colton ... [et al.] editors. p. cm. — (DIMACS series in discrete mathematics and theoretical computer science, ISSN 1052-1798 ; v. 47) “DIMACS ‘Special Year’ in Mathematical Support for Molecular Biology”-Pref. Includes bibliographical references. ISBN 0-8218-0826-5 (alk. paper) 1. Molecular biology-Mathematics. I. Farach-Colton, Martin. II. Title. III. Series. QH506.D56 1999 98-32095 572.8,01/51—dc21 CIP Copying and reprinting. Material in this book may be reproduced by any means for educational and scientific purposes without fee or permission with the exception of reproduction by services that collect fees for delivery of documents and provided that the customary acknowledgmenbof the source is given. This consent does not extend to other kinds of copying for general distribution, for advertising or promotional purposes, or for resale. Requests for permission for commercial use of material should be addressed to the Assistant to the Publisher, American Mathematical Society, P. O. Box 6248, Providence, Rhode Island 02940-6248. Requests can also be made by e-mail to [email protected]. Excluded from these provisions is material in articles for which the author holds copyright. In such cases, requests for permission to use or reprint should be addressed directly to the author(s). (Copyright ownership is indicated in the notice in the lower right-hand corner of the first page of each article.) © 1999 by the American Mathematical Society. All rights reserved. The American Mathematical Society retains all rights except those granted to the United States Government. Printed in the United States of America. . @ The paper used in this book is acid-free and falls within the guidelines established to ensure permanence and durability. Visit the AMS home page at LTRL: http://www.ams.org/ 10 987654321 04 03 02 01 00 99 Contents Foreword vq Preface ix An introduction to molecular biology for mathematicians and computer programmers Walter M. Fitch 1 New uses for uniform lifted alignments Dan Gusfield and Lusheng Wang 33 Sequence alignment and phylogeny construction Martin Vingron 53 A new look at tree models for multiple sequence alignment Dannie Durand 65 Sequence alignment in molecular biology Alberto Apostolico and Raffaele Giancarlo 85 Formal language theory and biological macromolecules David B. Searls 117 Global optimization approaches in protein folding and peptide docking C. A. Floudas, J. L. Klepeis, and P. M. Pardalos 141 The topologically driven strand separation transition in DNA - Methods of analysis and biological significance Craig J. Benham 173 Parallel strategies for DNA manipulation analysis Cassandra L. Smith, Takeshi Sano, Natalia E. Broude, and Charles R. Cantor 199 A column-generation based branch-and-bound algorithm for sorting by reversals Alberto Caprara, Giuseppe Lancia, and See-Kiong Ng 213 Visualizing measures of genetic distance Eric M. Jordan 227 Fragment assembly system for DNA sequencing projects L. Milanesi, M. Marsilli, G. Mauri, C. Rolfi, and L. Uboldi 241 V VI CONTENTS Performance of the CAP2 sequence assembly program Xiaoqiu Huang 259 A simple toolkit for DNA fragment assembly Joao Meidanis 271