Chaining algorithms for alignment of draft sequence.

Abstract

In this paper we propose a chaining method that can align a draft genomic sequence against a finished genome. We introduce the use of an overlap tree to enhance the state information available to the chaining procedure in the context of sparse dynamic programming, and demonstrate that the resulting procedure more accurately penalizes the various biological rearrangements. The algorithm is tested on a whole genome alignment of seven yeast species. We also demonstrate a variation on the algorithm that can be used for coassembly of two genomes and show how it can improve the current assembly of the Ciona savignyi (sea squirt) genome.

Publication
International Workshop on Algorithms in Bioinformatics, 2004
Date
Links