Tag Archives: Contigss

String Reconstruction

String Reconstruction Problem: Reconstruct a string from its k-mer composition
Input: An integer k and a collection Patterns of k-mers. (AAT ATG GTT TAA TGT)
Output: A string Text with k-mer composition equal to Patterns (if such a string exists).

TAA
   AAT
    ATG
     TGT
      GTT
 TAATGTT

1.The String Reconstruction Problem reduces to finding an Eulerian path in the de Bruijn graph generated from reads.  Solve the String Reconstruction Problem.
Input: The adjacency list of a directed graph that has an Eulerian path.
CTT -> TTA
ACC -> CCA
TAC -> ACC
GGC -> GCT
GCT -> CTT
TTA -> TAC
Output: An Eulerian path in this graph. GGCTTACCA
Read more of this post

Advertisement