Publications - Published papers
Please find below publications of our group. Currently, we list 565 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
Fast local fragment chaining using sum-of-pair gap costs
Christian Otto, Steve Hoffmann, Jan Gorodkin, Peter F. Stadler
Download
Status: Published
Algorithms for Molecular Biology 2011, 6:4
Abstract
<b>Background:</b> Fast seed-based alignment heuristics such as <tt>blast</tt> and <tt>blat</tt> have become indispensable tools in comparative genomics for all studies aiming at the evolutionary relations of proteins, genes, and non-coding RNAs. This is true in particular for the large mammalian genomes. The sensitivity and specificity of these tools, however, crucially depend on parameters such as seed sizes or maximum expectation values. In settings that require high sensitivity the amount of short local match fragments often becomes intractable. Then, fragment chaining is a powerful leverage to quickly connect, score, and rank the fragments to improve the specificity.<br>
<b>Results:</b>
Here we present <tt>clasp</tt>, a fast and flexible fragment chainer that for the first time also supports a sum-of-pair gap cost model. This model has proven to achieve a higher accuracy and sensitivity in its own field of application. Utilizing a very time-efficient index structure <tt>clasp</tt> outperforms the only existing tool for fragment chaining under the linear gap cost model. It can easily be applied to the output generated by alignment tools such as <tt>blast</tt> or <tt>segemehl</tt>. As an example we consider homology-based searches for human and mouse snoRNAs demonstrating that a highly sensitive <tt>blast</tt> search with subsequent chaining is an attractive option. The sum-of-pair gap costs provide a substantial advantage is this context.<br>
<b>Conclusions:</b> Chaining of short match fragments helps to quickly and accurately identify regions of homology that may not be found using local alignment heuristics alone. By providing both the linear and the sum-of-pair gap cost model, a wider range of application can be covered.
<br>
The software <tt>clasp</tt> is available at
<a href="http://www.bioinf.uni-leipzig.de/Software/clasp/"><tt>http://www.bioinf.uni-leipzig.de/Software/clasp/</tt></a>
Keywords
fragment chaining, sum of pair score, homology search, snoRNAs