A new pheromone trail-based genetic algorithm for comparative genome assembly

@article{citeulike:2767287, abstract = {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/. 10.1093/nar/gkn168}, author = {Zhao, Fangqing and Zhao, Fanggeng and Li, Tao and Bryant, Donald A. }, citeulike-article-id = {2767287}, doi = {http://dx.doi.org/10.1093/nar/gkn168}, journal = {Nucl. Acids Res.}, keywords = {assembly, bioinformatics, genome, genomics}, month = {April}, pages = {gkn168+}, posted-at = {2008-05-07 21:28:04}, priority = {0}, title = {A new pheromone trail-based genetic algorithm for comparative genome assembly}, url = {http://dx.doi.org/10.1093/nar/gkn168}, year = {2008} }

TY - JOUR ID - citeulike:2767287 L3 - citeulike-article-id:2767287 TI - A new pheromone trail-based genetic algorithm for comparative genome assembly JF - Nucl. Acids Res. SP - gkn168 N2 - 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/. 10.1093/nar/gkn168 KW - assembly KW - bioinformatics KW - genome KW - genomics AU - Zhao, Fangqing AU - Zhao, Fanggeng AU - Li, Tao AU - Bryant, Donald PY - 2008/04/29/ UR - http://dx.doi.org/10.1093/nar/gkn168 ER -