dorsal/arxiv
View SchemaParametric Alignment of Drosophila Genomes
| Authors | Colin Dewey, Peter Huggins, Kevin Woods, Bernd Sturmfels, Lior Pachter |
|---|---|
| Categories | |
| ArXiv ID | q-bio/0512008 |
| URL | https://arxiv.org/abs/q-bio/0512008 |
| DOI | 10.1371/journal.pcbi.0020073 |
Abstract
The classic algorithms of Needleman--Wunsch and Smith--Waterman find a maximum a posteriori probability alignment for a pair hidden Markov model (PHMM). In order 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 which 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. Our main result is the construction of a whole genome parametric alignment of Drosophila melanogaster and Drosophila pseudoobscura. Parametric alignment resolves the issue of robustness to changes in parameters by finding all optimal alignments for all possible parameters in a PHMM. Our 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. The alignment polytopes, software, and supplementary material can be downloaded at http://bio.math.berkeley.edu/parametric/.
{
"annotation_id": "9e6adf55-8c72-4a4a-b0c0-06be922d0cc2",
"date_created": "2026-03-02T18:01:35.127000Z",
"date_modified": "2026-03-02T18:01:35.127000Z",
"file_hash": "4e161444704107cffaff80cf5f10c9bf3f17212d96f9d600f0ec69010849e2aa",
"private": false,
"record": {
"abstract": "The classic algorithms of Needleman--Wunsch and Smith--Waterman find a\nmaximum a posteriori probability alignment for a pair hidden Markov model\n(PHMM). In order to process large genomes that have undergone complex genome\nrearrangements, almost all existing whole genome alignment methods apply fast\nheuristics to divide genomes into small pieces which are suitable for\nNeedleman--Wunsch alignment. In these alignment methods, it is standard\npractice to fix the parameters and to produce a single alignment for subsequent\nanalysis by biologists.\n Our main result is the construction of a whole genome parametric alignment of\nDrosophila melanogaster and Drosophila pseudoobscura. Parametric alignment\nresolves the issue of robustness to changes in parameters by finding all\noptimal alignments for all possible parameters in a PHMM. Our alignment draws\non existing heuristics for dividing whole genomes into small pieces for\nalignment, and it relies on advances we have made in computing convex polytopes\nthat allow us to parametrically align non-coding regions using biologically\nrealistic models. We demonstrate the utility of our parametric alignment for\nbiological inference by showing that cis-regulatory elements are more conserved\nbetween Drosophila melanogaster and Drosophila pseudoobscura than previously\nthought. We also show how whole genome parametric alignment can be used to\nquantitatively assess the dependence of branch length estimates on alignment\nparameters.\n The alignment polytopes, software, and supplementary material can be\ndownloaded at http://bio.math.berkeley.edu/parametric/.",
"arxiv_id": "q-bio/0512008",
"authors": [
"Colin Dewey",
"Peter Huggins",
"Kevin Woods",
"Bernd Sturmfels",
"Lior Pachter"
],
"categories": [
"q-bio.GN",
"math.CO",
"q-bio.QM"
],
"doi": "10.1371/journal.pcbi.0020073",
"title": "Parametric Alignment of Drosophila Genomes",
"url": "https://arxiv.org/abs/q-bio/0512008"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "17a2225e-a9ea-44b7-92b3-ab8ad6ccfc7c",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}