Assembling contigs in draft genomes using reversals and block-interchanges

dc.contributor.author Li, Chi-Long
dc.contributor.author Chen, Kun-Tze
dc.contributor.author Lu, Chin L
dc.date.accessioned 2018-02-23T17:29:50Z
dc.date.available 2018-02-23T17:29:50Z
dc.date.issued 2013-04-10
dc.date.updated 2018-02-23T17:29:50Z
dc.description.abstract Abstract The techniques of next generation sequencing allow an increasing number of draft genomes to be produced rapidly in a decreasing cost. However, these draft genomes usually are just partially sequenced as collections of unassembled contigs, which cannot be used directly by currently existing algorithms for studying their genome rearrangements and phylogeny reconstruction. In this work, we study the one-sided block (or contig) ordering problem with weighted reversal and block-interchange distance. Given a partially assembled genome π and a completely assembled genome σ, the problem is to find an optimal ordering to assemble (i.e., order and orient) the contigs of π such that the rearrangement distance measured by reversals and block-interchanges (also called generalized transpositions) with the weight ratio 1:2 between the assembled contigs of π and σ is minimized. In addition to genome rearrangements and phylogeny reconstruction, the one-sided block ordering problem particularly has a useful application in genome resequencing, because its algorithms can be used to assemble the contigs of a draft genome π based on a reference genome σ. By using permutation groups, we design an efficient algorithm to solve this one-sided block ordering problem in O δ n time, where n is the number of genes or markers and δ is the number of used reversals and block-interchanges. We also show that the assembly of the partially assembled genome can be done in O n time and its weighted rearrangement distance from the completely assembled genome can be calculated in advance in O n time. Finally, we have implemented our algorithm into a program and used some simulated datasets to compare its accuracy performance to a currently existing similar tool, called SIS that was implemented by a heuristic algorithm that considers only reversals, on assembling the contigs in draft genomes based on their reference genomes. Our experimental results have shown that the accuracy performance of our program is better than that of SIS, when the number of reversals and transpositions involved in the rearrangement events between the complete genomes of π and σ is increased. In particular, if there are more transpositions involved in the rearrangement events, then the gap of accuracy performance between our program and SIS is increasing.
dc.identifier.citation BMC Bioinformatics. 2013 Apr 10;14(Suppl 5):S9
dc.identifier.uri http://dx.doi.org/10.1186/1471-2105-14-S5-S9
dc.identifier.uri http://rportal.lib.ntnu.edu.tw/handle/20.500.12235/80348
dc.language.rfc3066 en
dc.rights.holder Li et al.; licensee BioMed Central Ltd.
dc.title Assembling contigs in draft genomes using reversals and block-interchanges
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
12859_2013_Article_5777.pdf
Size:
1.38 MB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
0 B
Format:
Item-specific license agreed upon to submission
Description: