Standard

Approximating shortest superstring problem using de Bruijn graphs. / Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan.

Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings. 2013. p. 120-129 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7922 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Golovnev, A, Kulikov, AS & Mihajlin, I 2013, Approximating shortest superstring problem using de Bruijn graphs. in Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7922 LNCS, pp. 120-129, 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013, Bad Herrenalb, Germany, 17/06/13. https://doi.org/10.1007/978-3-642-38905-4_13

APA

Golovnev, A., Kulikov, A. S., & Mihajlin, I. (2013). Approximating shortest superstring problem using de Bruijn graphs. In Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings (pp. 120-129). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7922 LNCS). https://doi.org/10.1007/978-3-642-38905-4_13

Vancouver

Golovnev A, Kulikov AS, Mihajlin I. Approximating shortest superstring problem using de Bruijn graphs. In Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings. 2013. p. 120-129. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-38905-4_13

Author

Golovnev, Alexander ; Kulikov, Alexander S. ; Mihajlin, Ivan. / Approximating shortest superstring problem using de Bruijn graphs. Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings. 2013. pp. 120-129 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{caca192b148c496d9459f2d01d5523cc,
title = "Approximating shortest superstring problem using de Bruijn graphs",
abstract = "The best known approximation ratio for the shortest superstring problem is 211/23 (Mucha, 2012). In this note, we improve this bound for the case when the length of all input strings is equal to r, for r ≤ 7. E.g., for strings of length 3 we get a 11/3-approximation. An advantage of the algorithm is that it is extremely simple both to implement and to analyze. Another advantage is that it is based on de Bruijn graphs. Such graphs are widely used in genome assembly (one of the most important practical applications of the shortest common superstring problem). At the same time these graphs have only a few applications in theoretical investigations of the shortest superstring problem.",
author = "Alexander Golovnev and Kulikov, {Alexander S.} and Ivan Mihajlin",
year = "2013",
month = sep,
day = "24",
doi = "10.1007/978-3-642-38905-4_13",
language = "English",
isbn = "9783642389047",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "120--129",
booktitle = "Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings",
note = "24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013 ; Conference date: 17-06-2013 Through 19-06-2013",

}

RIS

TY - GEN

T1 - Approximating shortest superstring problem using de Bruijn graphs

AU - Golovnev, Alexander

AU - Kulikov, Alexander S.

AU - Mihajlin, Ivan

PY - 2013/9/24

Y1 - 2013/9/24

N2 - The best known approximation ratio for the shortest superstring problem is 211/23 (Mucha, 2012). In this note, we improve this bound for the case when the length of all input strings is equal to r, for r ≤ 7. E.g., for strings of length 3 we get a 11/3-approximation. An advantage of the algorithm is that it is extremely simple both to implement and to analyze. Another advantage is that it is based on de Bruijn graphs. Such graphs are widely used in genome assembly (one of the most important practical applications of the shortest common superstring problem). At the same time these graphs have only a few applications in theoretical investigations of the shortest superstring problem.

AB - The best known approximation ratio for the shortest superstring problem is 211/23 (Mucha, 2012). In this note, we improve this bound for the case when the length of all input strings is equal to r, for r ≤ 7. E.g., for strings of length 3 we get a 11/3-approximation. An advantage of the algorithm is that it is extremely simple both to implement and to analyze. Another advantage is that it is based on de Bruijn graphs. Such graphs are widely used in genome assembly (one of the most important practical applications of the shortest common superstring problem). At the same time these graphs have only a few applications in theoretical investigations of the shortest superstring problem.

UR - http://www.scopus.com/inward/record.url?scp=84884327431&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-38905-4_13

DO - 10.1007/978-3-642-38905-4_13

M3 - Conference contribution

AN - SCOPUS:84884327431

SN - 9783642389047

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 120

EP - 129

BT - Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings

T2 - 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013

Y2 - 17 June 2013 through 19 June 2013

ER -

ID: 49826021