Sequence Alignment This page intentionally left blank Sequence Alignment Methods, Models, Concepts, and Strategies Edited by Michael S. Rosenberg UNIVERSITY OF CALIFORNIA PRESS Berkeley . Los Angeles . London University of California Press, one of the most distinguished university presses in the United States, enriches lives around the world by advancing scholarship in the humanities, social sciences, and natural sciences. Its activities are supported by the UC Press Foundation and by philanthropic contributions from individuals and institutions. For more information, visit www.ucpress.edu. University of California Press Berkeley and Los Angeles, California University of California Press, Ltd. London, England © 2009 by The Regents of the University of California Library of Congress Cataloging-in-Publication Data Sequence alignment: methods, models, concepts, and strategies/edited by Michael S. Rosenberg. p.; cm. Includes bibliographical references and index. ISBN 978-0-520-25697-2 (cloth: alk. paper) 1. Bioinformatics. 2. Computational biology. I. Rosenberg, Michael S., 1972- [DNLM: 1. Sequence Alignment—methods. QU 450 S479 2009] QH324.2.S47 2009 572.80285—dc22 2 0 0 8 0 2 9 2 2 2 Manufactured in the United States 16 15 14 13 12 11 10 09 08 10 9 8 7 6 5 4 3 2 1 The paper used in this publication meets the minimum requirements of ANSI/NISO Z39.48-1992 (R 1997) (Permanence of Paper). Contents Contributors vii Preface xi 1. Sequence Alignment: Concepts and History 1 2. Insertion and Deletion Events, Their Molecular Mechanisms, and Their Impact on Sequence Alignments 23 3. Local versus Global Alignments 39 4. Computing Multiple Sequence Alignment with Template-Based Methods 55 5. Sequence Evolution Models for Simultaneous Alignment and Phylogeny Reconstruction 71 6. Phylogenetic Hypotheses and the Utility of Multiple Sequence Alignment 95 7. Structural and Evolutionary Considerations for Multiple Sequence Alignment of RNA, and the Challenges for Algorithms That Ignore Them 105 8. Constructing Alignment Benchmarks 151 9. Simulation Approaches to Evaluating Alignment Error and Methods for Comparing Alternate Alignments 179 v vi Contents 10. Robust Inferences from Ambiguous Alignments 209 11. Strategies for Effi cient Exploitation of the Informational Content of Protein Multiple Alignments 271 References 297 Index 333 Contributors Roland Fleißner Center for Integrative Bioinformatics, Vienna, Austria [email protected] Anne Friedrich Institut de Génétique et de Biologie Moléculaire et Cellulaire, France [email protected] Joseph J. Gillespie University of Maryland, Baltimore County Virginia Bioinformatics Institute, Virginia Tech [email protected] Gonzalo Giribet Harvard University [email protected] Karl Kjer Rutgers University [email protected] Liam J. McGuffin University of Reading, United Kingdom l.j.mcguffi [email protected] vii viii Contributors Dirk Metzler Ludwig-Maximilians-Universität, Munich, Germany [email protected] Burkhard Morgenstern University of Göttingen, Germany [email protected] Luc Moulinier Institut de Génétique et de Biologie Moléculaire et Cellulaire, France [email protected] Cédric Notredame Centre for Genomic Regulation, Spain [email protected] T. Heath Ogden Idaho State University [email protected] Olivier Poch Institut de Génétique et de Biologie Moléculaire et Cellulaire, France [email protected] Benjamin Redelings North Carolina State University [email protected] Michael S. Rosenberg Arizona State University [email protected] Usman Roshan New Jersey Institute of Technology [email protected] Marc A. Suchard University of California, Los Angeles [email protected] Contributors ix Julie D. Thompson Institut de Génétique et de Biologie Moléculaire et Cellulaire, France [email protected] Ward Wheeler American Museum of Natural History [email protected]