Paper Abstract and Keywords |
Presentation |
2012-09-03 11:25
Compressing de Bruijn Graphs Alexander Bowe (NII), Taku Onodera (Univ. of Tokyo), Kunihiko Sadakane (NII), Tetsuo Shibuya (Univ. of Tokyo) COMP2012-29 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
We propose a new succinct de Bruijn graph representation.
If the de Bruijn graph of $k$-mers in a DNA sequence of length $N$ has $m$ edges,
it can be represented in $4m + \order(m)$ bits.
This is much smaller than existing ones.
The numbers of outgoing and incoming edges of a node are computed in constant time, and
the outgoing and incoming edge with given label are found in constant time
and $\Order(k)$ time, respectively.
The data structure is constructed in $\Order(Nk \log m/\log\log m)$
time using no additional space. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
de Bruijn graph / genome assembly / succinct data structures / / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 112, no. 199, COMP2012-29, pp. 25-32, Sept. 2012. |
Paper # |
COMP2012-29 |
Date of Issue |
2012-08-27 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
COMP2012-29 |
Conference Information |
Committee |
COMP |
Conference Date |
2012-09-03 - 2012-09-03 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Hosei University |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
COMP |
Conference Code |
2012-09-COMP |
Language |
English (Japanese title is available) |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Compressing de Bruijn Graphs |
Sub Title (in English) |
|
Keyword(1) |
de Bruijn graph |
Keyword(2) |
genome assembly |
Keyword(3) |
succinct data structures |
Keyword(4) |
|
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Alexander Bowe |
1st Author's Affiliation |
National Institute of Informatics (NII) |
2nd Author's Name |
Taku Onodera |
2nd Author's Affiliation |
The University of Tokyo (Univ. of Tokyo) |
3rd Author's Name |
Kunihiko Sadakane |
3rd Author's Affiliation |
National Institute of Informatics (NII) |
4th Author's Name |
Tetsuo Shibuya |
4th Author's Affiliation |
The University of Tokyo (Univ. of Tokyo) |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-3 |
Date Time |
2012-09-03 11:25:00 |
Presentation Time |
35 minutes |
Registration for |
COMP |
Paper # |
COMP2012-29 |
Volume (vol) |
vol.112 |
Number (no) |
no.199 |
Page |
pp.25-32 |
#Pages |
8 |
Date of Issue |
2012-08-27 (COMP) |
|