A Caltech Library Service

Parametric Alignment of Drosophila Genomes

Dewey, Colin N. and Huggins, Peter M. and Woods, Kevin and Sturmfels, Bernd and Pachter, Lior (2006) Parametric Alignment of Drosophila Genomes. PLoS Computational Biology, 2 (6). Art. No. e73. ISSN 1553-734X. PMCID PMC1480539. doi:10.1371/journal.pcbi.0020073.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The classic algorithms of Needleman–Wunsch and Smith–Waterman find a maximum a posteriori probability alignment for a pair hidden Markov model (PHMM). To process large genomes that have undergone complex genome rearrangements, almost all existing whole genome alignment methods apply fast heuristics to divide genomes into small pieces that are suitable for Needleman–Wunsch alignment. In these alignment methods, it is standard practice to fix the parameters and to produce a single alignment for subsequent analysis by biologists. As the number of alignment programs applied on a whole genome scale continues to increase, so does the disagreement in their results. The alignments produced by different programs vary greatly, especially in non-coding regions of eukaryotic genomes where the biologically correct alignment is hard to find. Parametric alignment is one possible remedy. This methodology resolves the issue of robustness to changes in parameters by finding all optimal alignments for all possible parameters in a PHMM. Our main result is the construction of a whole genome parametric alignment of Drosophila melanogaster and Drosophila pseudoobscura. This alignment draws on existing heuristics for dividing whole genomes into small pieces for alignment, and it relies on advances we have made in computing convex polytopes that allow us to parametrically align non-coding regions using biologically realistic models. We demonstrate the utility of our parametric alignment for biological inference by showing that cis-regulatory elements are more conserved between Drosophila melanogaster and Drosophila pseudoobscura than previously thought. We also show how whole genome parametric alignment can be used to quantitatively assess the dependence of branch length estimates on alignment parameters.

Item Type:Article
Related URLs:
URLURL TypeDescription CentralArticle Paper
Pachter, Lior0000-0002-9164-6231
Additional Information:© 2006 Dewey et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. Received: December 7, 2005; Accepted: May 10, 2006; Published: June 23, 2006. CND was supported by the NIH (HG003150), PMH was supported by an ARCS Foundation fellowship, and KW was supported by the NSF (DMS-040214). BS was supported by the NSF (DMS-0456960), and LP was supported by the NIH (R01-HG2362-3 and HG003150) and an NSF CAREER award (CCF-0347992). Author Contributions: CND, PMH, KW, BS, and LP conceived and designed the experiments. CND and PMH performed the experiments. CND, PMH, KW, BS, and LP analyzed the data. CND, PMH, KW, BS, and LP wrote the paper. The authors have declared that no competing interests exist.
Funding AgencyGrant Number
Issue or Number:6
PubMed Central ID:PMC1480539
Record Number:CaltechAUTHORS:20170307-090954418
Persistent URL:
Official Citation:Dewey CN, Huggins PM, Woods K, Sturmfels B, Pachter L (2006) Parametric Alignment of Drosophila Genomes. PLoS Comput Biol 2(6): e73. doi:10.1371/journal.pcbi.0020073
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74833
Deposited By: Tony Diaz
Deposited On:07 Mar 2017 17:44
Last Modified:11 Nov 2021 05:30

Repository Staff Only: item control page