Cargando…
A new pheromone trail-based genetic algorithm for comparative genome assembly
Gap closing is considered one of the most challenging and time-consuming tasks in bacterial genome sequencing projects, especially with the emergence of new sequencing technologies, such as pyrosequencing, which may result in large amounts of data without the benefit of large insert libraries for co...
Autores principales: | , , , |
---|---|
Formato: | Texto |
Lenguaje: | English |
Publicado: |
Oxford University Press
2008
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2425481/ https://www.ncbi.nlm.nih.gov/pubmed/18445633 http://dx.doi.org/10.1093/nar/gkn168 |
_version_ | 1782156265243279360 |
---|---|
author | Zhao, Fangqing Zhao, Fanggeng Li, Tao Bryant, Donald A. |
author_facet | Zhao, Fangqing Zhao, Fanggeng Li, Tao Bryant, Donald A. |
author_sort | Zhao, Fangqing |
collection | PubMed |
description | Gap closing is considered one of the most challenging and time-consuming tasks in bacterial genome sequencing projects, especially with the emergence of new sequencing technologies, such as pyrosequencing, which may result in large amounts of data without the benefit of large insert libraries for contig scaffolding. We propose a novel algorithm to align contigs with more than one reference genome at a time. This approach can successfully overcome the limitations of low degrees of conserved gene order for the reference and target genomes. A pheromone trail-based genetic algorithm (PGA) was used to search globally for the optimal placement for each contig. Extensive testing on simulated and real data sets shows that PGA significantly outperforms previous methods, especially when assembling genomes that are only moderately related. An extended version of PGA can predict additional candidate connections for each contig and can thus increase the likelihood of identifying the correct arrangement of each contig. The software and test data sets can be accessed at http://sourceforge.net/projects/pga4genomics/. |
format | Text |
id | pubmed-2425481 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2008 |
publisher | Oxford University Press |
record_format | MEDLINE/PubMed |
spelling | pubmed-24254812008-06-12 A new pheromone trail-based genetic algorithm for comparative genome assembly Zhao, Fangqing Zhao, Fanggeng Li, Tao Bryant, Donald A. Nucleic Acids Res Computational Biology Gap closing is considered one of the most challenging and time-consuming tasks in bacterial genome sequencing projects, especially with the emergence of new sequencing technologies, such as pyrosequencing, which may result in large amounts of data without the benefit of large insert libraries for contig scaffolding. We propose a novel algorithm to align contigs with more than one reference genome at a time. This approach can successfully overcome the limitations of low degrees of conserved gene order for the reference and target genomes. A pheromone trail-based genetic algorithm (PGA) was used to search globally for the optimal placement for each contig. Extensive testing on simulated and real data sets shows that PGA significantly outperforms previous methods, especially when assembling genomes that are only moderately related. An extended version of PGA can predict additional candidate connections for each contig and can thus increase the likelihood of identifying the correct arrangement of each contig. The software and test data sets can be accessed at http://sourceforge.net/projects/pga4genomics/. Oxford University Press 2008-06 2008-04-29 /pmc/articles/PMC2425481/ /pubmed/18445633 http://dx.doi.org/10.1093/nar/gkn168 Text en © 2008 The Author(s) http://creativecommons.org/licenses/by-nc/2.0/uk/ This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/2.0/uk/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Computational Biology Zhao, Fangqing Zhao, Fanggeng Li, Tao Bryant, Donald A. A new pheromone trail-based genetic algorithm for comparative genome assembly |
title | A new pheromone trail-based genetic algorithm for comparative genome assembly |
title_full | A new pheromone trail-based genetic algorithm for comparative genome assembly |
title_fullStr | A new pheromone trail-based genetic algorithm for comparative genome assembly |
title_full_unstemmed | A new pheromone trail-based genetic algorithm for comparative genome assembly |
title_short | A new pheromone trail-based genetic algorithm for comparative genome assembly |
title_sort | new pheromone trail-based genetic algorithm for comparative genome assembly |
topic | Computational Biology |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2425481/ https://www.ncbi.nlm.nih.gov/pubmed/18445633 http://dx.doi.org/10.1093/nar/gkn168 |
work_keys_str_mv | AT zhaofangqing anewpheromonetrailbasedgeneticalgorithmforcomparativegenomeassembly AT zhaofanggeng anewpheromonetrailbasedgeneticalgorithmforcomparativegenomeassembly AT litao anewpheromonetrailbasedgeneticalgorithmforcomparativegenomeassembly AT bryantdonalda anewpheromonetrailbasedgeneticalgorithmforcomparativegenomeassembly AT zhaofangqing newpheromonetrailbasedgeneticalgorithmforcomparativegenomeassembly AT zhaofanggeng newpheromonetrailbasedgeneticalgorithmforcomparativegenomeassembly AT litao newpheromonetrailbasedgeneticalgorithmforcomparativegenomeassembly AT bryantdonalda newpheromonetrailbasedgeneticalgorithmforcomparativegenomeassembly |