banded alignment unstable on two node graph

[ekg]

I'm experiencing instability in the banded aligner.

I add this to src/unittest/banded_global_aligner.cpp

 SECTION( "Banded global aligner produces correct alignment for a graph with two nodes") {

    VG graph;

    QualAdjAligner aligner = QualAdjAligner();

    Node* n0 = graph.create_node("A");
    Node* n1 = graph.create_node("G");

    graph.create_edge(n0, n1);

    string read = string("C");
    Alignment aln;
    aln.set_sequence(read);

    int band_width = 1;
    BandedGlobalAligner banded_aligner = BandedGlobalAligner(aln,
                                                             graph.graph,
                                                             band_width);


    banded_aligner.align(aligner.score_matrix, aligner.nt_table, aligner.gap_open,
                         aligner.gap_extension);

    //cerr << pb2json(aln) << endl;                                                      
    const Path& path = aln.path();
    cerr << pb2json(path) << endl;

    // follows correct path                                                              
    REQUIRE(path.mapping(0).position().node_id() == 1);

}

Sometimes it runs.

-> % vg test
{"mapping": [{"position": {"node_id": 1}, "edit": [{"from_length": 1}], "rank": 1}, {"position": {"node_id": 2}, "edit": [{"to_length": 1, "from_length": 1, "sequence": "C"}], "rank": 2}]}
===============================================================================
All tests passed (4959 assertions in 13 test cases)

Often it doesn't:

-> % vg test
error:[BandedGlobalAligner] traceback stuck at node boundary
vg: src/banded_global_aligner.cpp:1274: void vg::BandedGlobalAligner::BAMatrix::traceback_internal(vg::BandedGlobalAligner::BABuilder&, vg::BandedGlobalAligner::AltTracebackStack&, int64_t, int64_t, vg::BandedGlobalAligner::matrix_t, bool, int8_t*, int8_t*, int8_t, int8_t, bool, int8_t): Assertion `0' failed.

vg test is a Catch v1.5.6 host application.
Run with -? for options

---

Banded global aligner produces correct alignments with all types of edits

Banded global aligner produces correct alignment for a graph with two nodes

src/unittest/banded_global_aligner.cpp:22
...............................................................................

src/unittest/banded_global_aligner.cpp:78: FAILED:
due to a fatal error condition:
SIGABRT - Abort (abnormal termination) signal

test cases: 5 | 4 passed | 1 failed
assertions: 107 | 106 passed | 1 failed

@jeizenga  Any ideas?

[jeizenga]

I can reproduce it locally, so I'm taking a look now.

[jeizenga]

@ekg Fixed in this PR, I hope.

[jeizenga]

On a related note, it occurred to me that we'll probably need to take care of the case of an insertion relative to the reference outside of the banded aligner. In that case, you might end up passing an empty Graph to the aligner, in which case the aligner doesn't have enough information to make a Path because it doesn't know which node to call the insertion on.