Re: [Seqan-dev] Memory allocation error with globalAlignmentScore() and globalAlignment()

[Rahn, René <rene.maerker@fu-berlin.de>]

Hi Johannes, 

if you only need the score without traceback then MeyersBitVector would be the choice. You can use the MeyersHirschberg version to get the traceback too. Note that both versions can only be applied to an edit distance cost scheme. 

For more complex scoring schemes you need the NeedlemanWunsch algorithm. Have a look at our tutorial pages to find out all about the alignment algorithms in SeqAn: http://trac.seqan.de/wiki/Tutorial/PairwiseSequenceAlignment.

The NeedlemanWunsch also works with the globalAlignmentScore function. In fact it computes no traceback at all, speeding up the algorithm a lot.

Kind regards, 

René

On Aug 21, 2013, at 1:55 PM, Johannes Dröge <johdro@mpi-inf.mpg.de>

 wrote:

Hi Manuel,

does the standard NeedlemanWunsch also work with globalAlignmentScore()? Is MyersBitVector the fastest among the global alignment algorithms in Seqan?

Gruß Johannes


Am 21.08.2013 13:48, schrieb Holtgrewe, Manuel:

Hi Johannes,

we will investigate this problem.

Meanwhile, you could use the globalAlignment() function without a tag. We do not have current benchmarks for MyerHirschberg vs. our new NeedlemanWunsch implementation but the latter is definitely more used and then less error prone.

HTH
Manuel
________________________________________
From: Johannes Dröge [johdro@mpi-inf.mpg.de]
Sent: Wednesday, August 21, 2013 12:54 PM
To: SeqAn Development
Subject: [Seqan-dev] Memory allocation error with globalAlignmentScore() and    globalAlignment()

Hello Seqan developers,

I just ported my software, which was using globalAlignment() extensively without problems, from a Seqan version from 2011 to the recent headers. I had to change the syntax related to the scoring until it compiled well. Anyway, now I got a segfault when running globalAlignment(). I then changed the code to use globalAlignmentsScore(), because I don't actually need the explicit alignment. The error is still persists and seems to be related to the data/types or similar.

1) Here is the original code fragment:

const seqan::Dna5String qseq = ...
seqan::Dna5String rseq = ...
seqan::Align< seqan::Dna5String > aln;
seqan::resize( seqan::rows( aln ), 2);
seqan::assignSource( seqan::row( aln, 0 ), qseq );
seqan::assignSource( seqan::row( aln, 1 ), rseq );
const int score = -seqan::globalAlignment( aln, seqan::SimpleScore(), seqan::MyersHirschberg() );

2) Here is the intermediate code:

const seqan::Dna5String qseq = ...
seqan::Dna5String rseq = ...
seqan::Align< seqan::Dna5String > aln;
seqan::resize( seqan::rows( aln ), 2);
seqan::assignSource( seqan::row( aln, 0 ), qseq );
seqan::assignSource( seqan::row( aln, 1 ), rseq );
const int score = -seqan::globalAlignment( aln, seqan::MyersHirschberg() );

3) Here is the current code:

const seqan::Dna5String qseq = ...
seqan::Dna5String rseq = ...
const int score = -seqan::globalAlignmentScore( qseq, rseq, seqan::MyersHirschberg() );

----------

This is what I get from (2) and (3):

aligning two sequences globally:
seq1: TAGCACTCAGGGAGAATGAGTGCTAAAACATAGAATGAGAAATGGAGGCGAGAGTATGGAGCTGACCAATCGAAAAAAGCGAATCCTGCGGGCCATTGTTGAGATCTATATCTCCACCGCGGAACCGGTAGGTTCCAAGGCCGTGGCAGAGCAGGCCGGACTGGACATCTCCACCGCCACCATACGAAATGAGATGGCCGACCTCACCGAACTGGGCTATCTGGAGCAGCCCCACACCTCGGCCGGACGGATTCCGTCCCCCATGGGCTACCGGCTCTACGTCAACGAGCTCATGGGTGAGCACCAGCTGACCATGCAGGAGACCCAGCGCATCAACGACGCGCTGAACCTGAAAATGGAGGAGCTGGACCGGGTCATCGACCGGGCGGGCAAGGTGCTCTCCCAGATCAGCGACTACCCCGTCTTTACCATGGCCCAGCCCAAGCAGCGGGTGACGGTAAAGCGGTACGACCTGCTGATGGTAGAGGAAAACGCCTTTATCGCTGTGGTGATGACCGACAACTCGGTGGTGCGCAACAAGCTTATCCACCTGTCCGATGAGCTTTCCGACACCCAGCTGCAGCTGCTGTCCACCGTTTTGAACAGCTCCTTTGTAGGTCTGACCGTGGAGGAAATGGAACAG
seq2: TATATTAGCACTCGGAAAGCGAGAGTGCCAACAGTCCGAAGCGGAGAGTGCTAACATGGCAATCAGTGAGAGGAAAAAGAAAATACTGGCGGCGGTGGTGGATGAATACATCCGCACGGCAGAGCCGGTAGGCAGCAAGGCCATCGCCCAGAGCGGCGGGCTGAACTGCTCCTCGGCCACCATCCGCAACGAGCTGGCGGAGCTGGTCGCCATGGGCTATCTGGAGCAGCCCCACACCTCTGCGGGCCGGGTGCCCACCCCCATGGGCTACCGCATGTACGTCAACGAGCTCATGGAGAAGCAGAAGATGAGCCTGGAGGAGACGGAGGAGATGAACCGCCGCCTGAACCAGAAGCTCCAGGAGCTGGACGACACCATCCGGGACGTGAGCAAGCTGGCTTCCCAGCTGACGAATTATCCCGCCCTGGCCCTGACGGCCCAGAGCTCCGTCACGGTAAAGCGCTTCGACCTGATCTATGTGGACGCCAACAACTTCATCATCGTGCTGATGCTGTCCAACAACAGCGTAAAGAGCAAGCTGGTGCATCTGCCGGTGTCCGTGGACCAGGACATGATCAAGCGCCTTTCCACCCTCTTCAACGCCAGCTTTACCGGCGTGGAGGATCAGCAGATCACGCCG
prog: malloc.c:4631: _int_malloc: Assertion `(unsigned long)(size) >= (unsigned long)(nb)' failed.

----------

GDB backtrace:

0x00007ffff6a7d1b5 in raise () from /lib/libc.so.6
(gdb) bt
#0  0x00007ffff6a7d1b5 in raise () from /lib/libc.so.6
#1  0x00007ffff6a7ffc0 in abort () from /lib/libc.so.6
#2  0x00007ffff6ab35bb in ?? () from /lib/libc.so.6
#3  0x00007ffff6abce16 in ?? () from /lib/libc.so.6
#4  0x00000000004f13ce in seqan::deallocate<seqan::String<unsigned int, seqan::Alloc<void> >, unsigned int, unsigned long, seqan::AllocateStorage_> (data="">      at seqan/basic/allocator_interface.h:329
#5  0x00000000004ecc09 in seqan::_deallocateStorage<unsigned int, void, unsigned int, unsigned long> (me=..., ptr=0x832831460, capacity=32)
     at seqan/sequence/string_alloc.h:402
#6  0x00000000004e76d6 in ~String (this=0x7fffede12e80, __in_chrg=<value optimized out>)
     at seqan/sequence/string_alloc.h:177
#7  0x00000000004e1ebd in seqan::_globalAlignment<seqan::String<seqan::SimpleType<unsigned char, seqan::Dna5_>, seqan::Alloc<void> >, seqan::Tag<seqan::ArrayGaps_>, seqan::String<seqan::SimpleType<unsigned char, seqan::Dna5_>, seqan::Alloc<void> >, seqan::Tag<seqan::ArrayGaps_> > (gapsH=..., gapsV=..., algorithmTag=...)
     at seqan/align/global_alignment_myers_hirschberg_impl.h:745
#8  0x00000000004df9ea in seqan::_globalAlignment<seqan::String<seqan::SimpleType<unsigned char, seqan::Dna5_>, seqan::Alloc<void> >, seqan::Tag<seqan::ArrayGaps_>, seqan::String<seqan::SimpleType<unsigned char, seqan::Dna5_>, seqan::Alloc<void> >, seqan::Tag<seqan::ArrayGaps_> > (gapsH=..., gapsV=..., algorithmTag=...)
     at seqan/align/global_alignment_myers_hirschberg_impl.h:183
#9  0x00000000004db18c in seqan::globalAlignment<seqan::String<seqan::SimpleType<unsigned char, seqan::Dna5_>, seqan::Alloc<void> >, seqan::Tag<seqan::ArrayGaps_> > (align=...,
     algorithmTag=...) at seqan/align/global_alignment_specialized.h:93
#...

Could this be related to the differing sequence lengths or am I doing something else wrong?

Gruß Johannes

_______________________________________________
seqan-dev mailing list
seqan-dev@lists.fu-berlin.de
https://lists.fu-berlin.de/listinfo/seqan-dev

_______________________________________________
seqan-dev mailing list
seqan-dev@lists.fu-berlin.de
https://lists.fu-berlin.de/listinfo/seqan-dev

_______________________________________________
seqan-dev mailing list
seqan-dev@lists.fu-berlin.de
https://lists.fu-berlin.de/listinfo/seqan-dev

---

René Rahn

Ph.D. Student

---------------------------------

Mail:  rene.rahn@fu-berlin.de

Phone: +49 (0)30 838 75 277

---------------------------------

Algorithmic Bioinformatics (ABI)

Department of Computer Science 

Room  018

---------------------------------

Freie Universität Berlin

Takustraße 9 

14195 Berlin

---------------------------------