fn() chainSeedsGlobally
Global chaining of seeds.

Defined in <seqan/seeds.h>
Signature void chainSeedsGlobally(target, seedSet, tag);


target A container to append the seeds to.
seedSet The SeedSet object to get the seeds from.
tag The tag to select the algorithm with (currently only SparseChaining is supported).

Detailed Description

Chaining of seeds between two sequences can be performed using sparse chaining as defined in (Gusfield, 1997).


The following example demonstrates how to use the chainSeedsGlobally() function. First, a SeedSet is built and filled with SimpleSeed object. Then, a String of SimpleSeed objects is defined and filled using the chainSeedsGlobally() function.

#include <iostream>
#include <seqan/seeds.h>

using namespace seqan;

int main()
    // Build SeedSet.
    SeedSet<Seed<Simple>, Unordered> seedSet;
    addSeed(seedSet, Seed<Simple>(0, 93, 281, 342), Single());
    addSeed(seedSet, Seed<Simple>(3, 237, 127, 364), Single());
    addSeed(seedSet, Seed<Simple>(3, 284, 86, 368), Single());
    addSeed(seedSet, Seed<Simple>(5, 146, 239, 374), Single());
    addSeed(seedSet, Seed<Simple>(299, 352, 405, 460), Single());

    // Perform sparse chaining, uses time O(n log n).
    String<Seed<Simple> > chain;
    chainSeedsGlobally(chain, seedSet, SparseChaining());

    // Print results to stdout.
    for (unsigned i = 0; i < length(chain); ++i)
        std::cout << "Seed(" << beginPositionH(chain[i]) << ", "
                  << beginPositionV(chain[i]) << ", " << endPositionH(chain[i])
                  << ", " << endPositionV(chain[i]) << ")\n";

    return 0;

The output is as follows. Only the first and last seeds are written to std::cout.

Seed(0, 93, 281, 342)
Seed(299, 352, 405, 460)


  • Dan Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, January 1997.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.