Screening synteny blocks in pairwise genome comparisons through integer programming

Persistent Link:
http://hdl.handle.net/10150/610221
Title:
Screening synteny blocks in pairwise genome comparisons through integer programming
Author:
Tang, Haibao; Lyons, Eric; Pedersen, Brent; Schnable, James; Paterson, Andrew; Freeling, Michael
Affiliation:
Department of Plant and Microbial Biology, University of California, Berkeley, CA, 94720, USA; iPlant, Department of Plant Sciences, University of Arizona, Tucson, 85721, USA; Plant Genome Mapping Laboratory, University of Georgia, Athens, GA, 30602, USA
Issue Date:
2011
Publisher:
BioMed Central
Citation:
Tang et al. BMC Bioinformatics 2011, 12:102 http://www.biomedcentral.com/1471-2105/12/102
Journal:
BMC Bioinformatics
Rights:
© 2011 Tang et al; licensee BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0)
Collection Information:
This item is part of the UA Faculty Publications collection. For more information this item or other items in the UA Campus Repository, contact the University of Arizona Libraries at repository@u.library.arizona.edu.
Abstract:
BACKGROUND:It is difficult to accurately interpret chromosomal correspondences such as true orthology and paralogy due to significant divergence of genomes from a common ancestor. Analyses are particularly problematic among lineages that have repeatedly experienced whole genome duplication (WGD) events. To compare multiple "subgenomes" derived from genome duplications, we need to relax the traditional requirements of "one-to-one" syntenic matchings of genomic regions in order to reflect "one-to-many" or more generally "many-to-many" matchings. However this relaxation may result in the identification of synteny blocks that are derived from ancient shared WGDs that are not of interest. For many downstream analyses, we need to eliminate weak, low scoring alignments from pairwise genome comparisons. Our goal is to objectively select subset of synteny blocks whose total scores are maximized while respecting the duplication history of the genomes in comparison. We call this "quota-based" screening of synteny blocks in order to appropriately fill a quota of syntenic relationships within one genome or between two genomes having WGD events.RESULTS:We have formulated the synteny block screening as an optimization problem known as "Binary Integer Programming" (BIP), which is solved using existing linear programming solvers. The computer program QUOTA-ALIGN performs this task by creating a clear objective function that maximizes the compatible set of synteny blocks under given constraints on overlaps and depths (corresponding to the duplication history in respective genomes). Such a procedure is useful for any pairwise synteny alignments, but is most useful in lineages affected by multiple WGDs, like plants or fish lineages. For example, there should be a 1:2 ploidy relationship between genome A and B if genome B had an independent WGD subsequent to the divergence of the two genomes. We show through simulations and real examples using plant genomes in the rosid superorder that the quota-based screening can eliminate ambiguous synteny blocks and focus on specific genomic evolutionary events, like the divergence of lineages (in cross-species comparisons) and the most recent WGD (in self comparisons).CONCLUSIONS:The QUOTA-ALIGN algorithm screens a set of synteny blocks to retain only those compatible with a user specified ploidy relationship between two genomes. These blocks, in turn, may be used for additional downstream analyses such as identifying true orthologous regions in interspecific comparisons. There are two major contributions of QUOTA-ALIGN: 1) reducing the block screening task to a BIP problem, which is novel; 2) providing an efficient software pipeline starting from all-against-all BLAST to the screened synteny blocks with dot plot visualizations. Python codes and full documentations are publicly available http://github.com/tanghaibao/quota-alignment webcite. QUOTA-ALIGN program is also integrated as a major component in SynMap http://genomevolution.com/CoGe/SynMap.pl webcite, offering easier access to thousands of genomes for non-programmers.
EISSN:
1471-2105
DOI:
10.1186/1471-2105-12-102
Version:
Final published version
Additional Links:
http://www.biomedcentral.com/1471-2105/12/102

Full metadata record

DC FieldValue Language
dc.contributor.authorTang, Haibaoen
dc.contributor.authorLyons, Ericen
dc.contributor.authorPedersen, Brenten
dc.contributor.authorSchnable, Jamesen
dc.contributor.authorPaterson, Andrewen
dc.contributor.authorFreeling, Michaelen
dc.date.accessioned2016-05-20T09:01:26Z-
dc.date.available2016-05-20T09:01:26Z-
dc.date.issued2011en
dc.identifier.citationTang et al. BMC Bioinformatics 2011, 12:102 http://www.biomedcentral.com/1471-2105/12/102en
dc.identifier.doi10.1186/1471-2105-12-102en
dc.identifier.urihttp://hdl.handle.net/10150/610221-
dc.description.abstractBACKGROUND:It is difficult to accurately interpret chromosomal correspondences such as true orthology and paralogy due to significant divergence of genomes from a common ancestor. Analyses are particularly problematic among lineages that have repeatedly experienced whole genome duplication (WGD) events. To compare multiple "subgenomes" derived from genome duplications, we need to relax the traditional requirements of "one-to-one" syntenic matchings of genomic regions in order to reflect "one-to-many" or more generally "many-to-many" matchings. However this relaxation may result in the identification of synteny blocks that are derived from ancient shared WGDs that are not of interest. For many downstream analyses, we need to eliminate weak, low scoring alignments from pairwise genome comparisons. Our goal is to objectively select subset of synteny blocks whose total scores are maximized while respecting the duplication history of the genomes in comparison. We call this "quota-based" screening of synteny blocks in order to appropriately fill a quota of syntenic relationships within one genome or between two genomes having WGD events.RESULTS:We have formulated the synteny block screening as an optimization problem known as "Binary Integer Programming" (BIP), which is solved using existing linear programming solvers. The computer program QUOTA-ALIGN performs this task by creating a clear objective function that maximizes the compatible set of synteny blocks under given constraints on overlaps and depths (corresponding to the duplication history in respective genomes). Such a procedure is useful for any pairwise synteny alignments, but is most useful in lineages affected by multiple WGDs, like plants or fish lineages. For example, there should be a 1:2 ploidy relationship between genome A and B if genome B had an independent WGD subsequent to the divergence of the two genomes. We show through simulations and real examples using plant genomes in the rosid superorder that the quota-based screening can eliminate ambiguous synteny blocks and focus on specific genomic evolutionary events, like the divergence of lineages (in cross-species comparisons) and the most recent WGD (in self comparisons).CONCLUSIONS:The QUOTA-ALIGN algorithm screens a set of synteny blocks to retain only those compatible with a user specified ploidy relationship between two genomes. These blocks, in turn, may be used for additional downstream analyses such as identifying true orthologous regions in interspecific comparisons. There are two major contributions of QUOTA-ALIGN: 1) reducing the block screening task to a BIP problem, which is novelen
dc.description.abstract2) providing an efficient software pipeline starting from all-against-all BLAST to the screened synteny blocks with dot plot visualizations. Python codes and full documentations are publicly available http://github.com/tanghaibao/quota-alignment webcite. QUOTA-ALIGN program is also integrated as a major component in SynMap http://genomevolution.com/CoGe/SynMap.pl webcite, offering easier access to thousands of genomes for non-programmers.en
dc.language.isoenen
dc.publisherBioMed Centralen
dc.relation.urlhttp://www.biomedcentral.com/1471-2105/12/102en
dc.rights© 2011 Tang et al; licensee BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0)en
dc.titleScreening synteny blocks in pairwise genome comparisons through integer programmingen
dc.typeArticleen
dc.identifier.eissn1471-2105en
dc.contributor.departmentDepartment of Plant and Microbial Biology, University of California, Berkeley, CA, 94720, USAen
dc.contributor.departmentiPlant, Department of Plant Sciences, University of Arizona, Tucson, 85721, USAen
dc.contributor.departmentPlant Genome Mapping Laboratory, University of Georgia, Athens, GA, 30602, USAen
dc.identifier.journalBMC Bioinformaticsen
dc.description.collectioninformationThis item is part of the UA Faculty Publications collection. For more information this item or other items in the UA Campus Repository, contact the University of Arizona Libraries at repository@u.library.arizona.edu.en
dc.eprint.versionFinal published versionen
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.