Victor Epain

Overlap Graph for Assembling and Scaffolding Algorithms: Paradigm Review and Implementation Proposals

Keywords:

Assembling Deoxyribonucleic Acid (DNA) fragments based on their overlaps remains the main assembly paradigm with long DNA fragments sequencing technologies, independently of the aim to resolve only one or several haplotypes. Since an overlap can be seen as a succession relationship between two oriented fragments, the directed graph structure has emerged as the more appropriate data structure for handling overlaps. However, this graph paradigm did not appear to take benefit of the reverse symmetry of the orientated fragments and their overlaps, which is a result of blind DNA doublestrand sequencing. Thus, the bi-directed graph paradigm was introduced to be the one that reduces the graph size by handling the reverse symmetry, and since becomes the mainly used graph paradigm. Nevertheless, graph paradigms have never been contrasted before, and no implementations were described. Here we make a complete review on the existing overlap graph paradigms. Furthermore, we present different implementations that are theoretically compared in terms of memory, and their impact on the design and on the time of some basic graph algorithms. We also show that by adapting close logic implementations, a graph paradigm can be switched to another.

Introduction

What is complementary strands? Double-stranded Deoxyribonucleic Acid (DNA) molecules still cannot be entirely sequenced. In fact, every sequencing technology (sequencer) generates numerous overlapping genomic fragments.

Reads

A DNA fragment obtained from a sequencing stage is denoted by read.

Definition 1.1: Raw reads

Let R aw be the set of raw reads. ∀r ∈ R aw , let define the following attributes:

-r rid ∈ N, the read's integer identifier (index) -r seq ∈ Σ + the read's sequence, where Σ = {A, T, G, C} is nucleotide alphabet A read can be sequenced from one strand or from its complement.

Axiom 1.1: Double-stranded DNA sequencing i. The two DNA strands are both sequenced.

ii. A strand is read in reverse order to the order of its complementary strand.

iii. Given two reads, it is not possible to know a priori it they have been sequenced from the same strand.

The Definition 1.2 formalises Axiom 1.1 point iii.:

Definition 1.2: Strand identifier

Let strand_iid : R aw → {0; 1} be the function which returns the DNA strand identifier for a read.

V. Epain

INTRODUCTION

Reads

Then Axiom 1.1 point iii. can be mathematically formalised:

∃ (q, r) ∈ R aw 2 , q = r | strand_iid(q) = strand_iid(r) Axiom 1.1 suggests that combining two reads may result in a chimaera mix of the two strands because all the reads have not been sequenced from the same strand. Furthermore, only keeping the original sequence of the reads can result in the loss of strand parts during the assembly stage that aims to reconstruct the longest true parts of one strand. To solve these issues, it is sometimes necessary to consider the complementary sequence of some reads (i.e. the sequences on the complementary strand). For this, the sequence of the concerned reads are reversed (the end becomes the beginning, and vice versa) and each of its nucleotides is complemented (A T, G C). Arbitrarily, the original sequence of a read is denoted as the forward, while the reverse denotes the reverse-complement. In the following, determining what sequence is taken for a read is defined as orienting it. Finally, it is necessary to consider both the forward and the reverse orientation for all the reads. Figure 1 explains the meaning of forward and reverse orientations in the context of sequencing technology.

Definition 1.3: Reversed reads

Let R ev = {u r | u f ∈ R aw } denote the set of reversed reads. Thus R = R aw ∪ R ev . Let u ∈ R aw be a read. Subscript is added to u to precise its orientation:

-u f means that u is read in forward orientation (i.e. the original sequence of u, hence u f ∈ R aw )

-u r means that u is read in reverse orientation (i.e. the reversecomplemented sequence of u, hence u r ∈ R ev )

Now the set of all oriented reads R was built, the reverse operation can be defined:

Definition 1.4: The reverse operation for reads

For a given read u ∈ R, u denotes its reverse, where:

-u rid = u rid (i.e. a read u and its reverse u have the same identifier)

-u seq = u seq = b 1 b 2 • • • b n = b n-1 • • • b 1
where n ∈ N is the length of the nucleotides sequence, and ∀i ∈ 1; n , b i is the i th nucleotide base and

INTRODUCTION

b i its complementary nucleotide base.

Note that u f = u r and u r = u f .

Figure 1 -Double-stranded DNA sequencing. u f , v f are two reads from the raw reads set R aw obtained from a double-stranded DNA sequencing stage. By default, f (forward) denotes the reading orientation of the raw reads' sequence that gives their sequence, while r (reverse) denotes the reading orientation of the raw reads' sequence that gives their reversed complemented sequence. In this illustration case, u f was sequenced from strand strand 0 (strand_iid(u f ) = 0) while v f was sequenced from strand strand 1 (strand_iid(v f ) = 1).

Axiom 1.2: Belonging to one strand

The definition of R set and Axiom 1.1 point ii. give the following statement:

∀r ∈ R, strand_iid(r) = 1 -strand_iid(r)

Overlaps

Reads must be assembled to reconstruct the entire genome since they are shorter than the length of the strand from which they have been sequenced (see Axiom 1.1). To assemble the reads means to find the original order of the (oriented) reads. Thus, the assembly stage is at least based on oriented reads alignments that define a succession relationship between them. One alignment type that answers this issue is overlap.

Definition 1.5: Overlap

-An overlap between two nucleotides sequences (u, v) is a semi-global alignment or a close mapping between the end of sequence u seq and the beginning of sequence v seq .

V. Epain All four scenarios for sequence overlap are depicted in Figure 2.

Property 1.1: Overlap reverse symmetry

One overlap between two sequences always implies one overlap between the reversed sequences:

∀(q, r) ∈ R 2 , (q, r) ∈ O ⇐⇒ r, q ∈ O Proof From Definition 1.
(a) (u f , v f ) ∈ O (b) (v f , u f ) ∈ O (c) (u f , v r ) ∈ O (d) (v r , u f ) ∈ O
(a) u f overlaps v f (hence v r overlaps u r ) (b) v f overlaps u f (hence u r overlaps v r ) (c) u f overlaps v r (hence v f overlaps u r ) (d) v r overlaps u f (hence u r overlaps v f ).
Analogously with Definition 1.4, Definition 1.6 extends the reverse operation to overlaps:

8 V. Epain 1.2 Overlaps 1 INTRODUCTION

Definition 1.6: The reverse operation for overlaps

For a given overlap (q, r) ∈ O, (q, r) denotes its reverse i.e. r, q .

2 Storing Overlaps in a Graph Structure

Overlaps between the reads can be represented in a graph structure. A graph is a mathematical object composed of vertices connected by edges. This graph structure would respect the following requirements: Given all reads, the overlaps between them could be represented in a squared sparse matrix (of size R 2 ). Sparse matrix compression as Compressed Sparse Row (CSR) or Compressed Sparse Column (CSC) are known for efficiently storing the matrix and enable fast overlap existence querying. Finally, they enable fast edges iteration, but suffer from requirements 2 and can not be immediately adapted for handling overlaps reverse symmetry.

Thus, adjacency list structure seems to be adapted to dynamically add vertices and edges. Sections 2.1 to 2.3 below offer a complete review of graph paradigms, while Sections 3.1 to 3.3 propose graph implementations for each graph paradigm in the way of its philosophy. Figure 3 summarises the different graph paradigms and their implementations.

V. Epain Blue boxes: they correspond to graph paradigms. They are described by the type of graph they represent, the number of vertices and edges if they have to be drawn. Green boxes: they correspond to discussed graph implementations. After their name, the second line gives the adjacency list(s) definition set(s), following by the description of the type it (they) contain(s), finally the last line give the length of the adjacency list(s) (i.e. the number of vertices for which the neighbours are given). Ungraph, digraph, and bigraph respectively stand for undirected graph, directed graph and bidirected graph.

Fix Oriented FragmentS Based and Tail-head FragmentS based

Directed Graph: Oriented Fragments Based

The directed graph structure was the first idea to represent oriented reads and their overlaps, as overlaps are succession relationships. As far as we know, this structure was first mentioned in 1991 by Kececioglu [START_REF] Dimitri | Exact and Approximation Algorithms for DNA Sequence Reconstruction[END_REF]. Later, it was also described by Chin et al. [START_REF] Chin | Phased diploid genome assembly with single-molecule real-time sequencing[END_REF], Kamath et al. [START_REF] Govinda | HINGE: Long-read assembly achieves optimal repeat resolution[END_REF], Andonov et al. [START_REF] Andonov | Complete assembly of circular and chloroplast genomes based on global optimization[END_REF], Shafin et al. [START_REF] Shafin | Nanopore sequencing and the Shasta toolkit enable efficient de novo assembly of eleven human genomes[END_REF] and Cheng et al. [START_REF] Cheng | Haplotype-resolved de novo assembly using phased assembly graphs with hifiasm[END_REF] in their respective assembly method.

Definition 2.1: Oriented fragment based directed graph

Let G = (V , E) a directed graph such that: -V is the set of vertices, where each v ∈ V represents an oriented read.

For each read, there are two vertices (one for the forward orientation, and one for the reverse orientation). Thus, each v ∈ V has the following attributes:

-v rid ∈ N the identifier of the read it represents -v or ∈ {0; 1} the orientation of the read it represents (equals to 0 if forward, else equals to 1 if reverse) -E is the set of edges, where each (u, v) ∈ E represents oriented read u overlapping oriented read v.

Figure 4 shows how each overlap case is represented in the directed graph.

V. Epain

(a) (u f , v f ) ∈ O (b) (v f , u f ) ∈ O (c) (u f , v r ) ∈ O (d) (v r , u f ) ∈ O Figure 4
-Overlap cases in the directed graph. u and v are two sequences represented by two vertices each (u f , u r and v f , v r ). Each subfigure illustrates one overlap impact on the directed graph:

(a) (u f , v f ) ∈ E (hence (v r , u r ) ∈ E) (b) (v f , u f ) ∈ E (hence (u r , v r ) ∈ E) (c) (u f , v r ) ∈ E (hence (v f , u r ) ∈ E) (d) (v r , u f ) ∈ E (hence (u r , v f ) ∈ E).

Property 2.1: Sizes of the oriented fragment based directed graph

Let G = (V , E) be an oriented fragment based directed graph:

-|V | = 2 × |R aw | = |R| -|E| = |O|
Because there are two vertices for each read, such that one of them represents the reverse of the other one, it is possible to define a reverse operation for this graph. Definition 2.2 extends Definitions 1.4 and 1.6:

Definition 2.2: The reverse operation for vertices and edges in the oriented fragment based directed graph

Vertices For a given vertex v ∈ V , v denotes its reverse, where:

-

v rid = v rid -v or = 1 -v or
Edges For a given edge e = (u, v) ∈ E, e = v, u denotes its reverse.

= v 0 v 1 • • • v n-1 ∈ V n | n ∈ N in the graph G = (V , E
) that respects the following criteria:

Contiguity Two consecutive vertices in the path must be connected by an edge in the graph:

∀i | 0 ≤ i < n -1, (v i , v i+1 ) ∈ E
Exclusive orientation There is at most one orientation for each vertex in path p:

∀v ∈ p, v / ∈ p
Note that walking in this graph is quite similar that walking in a classic directed graph, except that it is not possible to walk through a vertex and its reverse. Figure 5 gives an example of a valid walk in the directed graph. A valid walk that begins from vertex v f is coloured in red. This walk results in a path p = v f u f x r .

Finally, Property 2.2 suggests that this directed graph inherits a reverse symmetry property analogous to Property 1.1: Property 2.2: Reverse symmetry for the vertices and the edges

-∀v ∈ V , v ∈ V . -∀(u, v) ∈ E, (u, v) = v, u ∈ E.

V. Epain Proof

By construction (see Definition 2.1), the first point is immediate. Concerning the second point, it is sufficient to note that if (r, q) ∈ O (hence (u, v) ∈ E), then q, r ∈ O (hence v, u ∈ E), where r and q are two oriented reads in R, respectively represented by vertices u and v in V .

Bi-directed Graph: Oriented Walk Based

In order to avoid creating two vertices for each read (and thus creating two edges for each overlap), the bi-directed graph structure to store overlaps was introduced by E. W. Myers in 1995 [START_REF] Myers | Toward simplifying and accurately formulating fragment assembly[END_REF]. The key idea is to represent each read with only one vertex and keep the strict necessary overlap information between two reads on the edge connecting two vertices. Definition 2.4 provides a formal description. It was also described by Sommer et al. [START_REF] Daniel | Minimus: A fast, lightweight genome assembler[END_REF], Hernandez et al. [START_REF] Hernandez | De novo bacterial genome sequencing: Millions of very short reads assembled on a desktop computer[END_REF] and Salmela et al. [START_REF] Salmela | Fast scaffolding with small independent mixed integer programs[END_REF] in their respective assembly method.

Definition 2.4: Oriented walk based bi-directed graph

Let G = (V , E, or E , rel E ) a bi-directed graph such that:
-V is the set of vertices, where each v ∈ V represents a non-oriented read. For each read, there are only one vertex. Thus, each vertex v ∈ V has an identifier of the read it represents v rid ∈ N.

-E is the set of edges, where each (u, v) ∈ E represents an overlap between oriented read u and oriented read v. The overlap information are given by or uv and rel uv :

-the orientation of u relatively to this of v is given by edge attribute or E : if the orientations are the same, then or uv = 0, else or uv = 1

-given that u identifier is lexicographically less that this of v, rel uv = 0 if u in forward orientation overlaps v (in orientation given by or uv ), else, rel uv = 1 if v (in orientation given by or uv ) overlaps u in forward orientation While visually each edge has two extremities in the bi-directed graph, in memory the graph is undirected. Figure 6 shows how visually and how internally each overlap is stored in the bi-directed graph.

14

V. Epain

(a) (u f , v f ) ∈ O (b) (v f , u f ) ∈ O (c) (u f , v r ) ∈ O (d) (v r , u f ) ∈ O Figure 6
-Overlap cases in the bi-directed graph. u and v are two unoriented sequences. Each subfigure illustrates one overlap impact on the bi-directed graph. For each, the first subfigure corresponds to the visualisation of a bi-directed edge, and the second shows the same information but with an undirected edge with or uv and rel uv attributes. (a) u and v have the same orientation in the overlap hence or uv = 0, u in forward orientation overlaps v hence rel uv = 0 (b) u and v have the same orientation in the overlap hence or uv = 0, u in forward orientation is overlapped by v hence rel uv = 1 (c) u and v do not have the same orientation in the overlap hence or uv = 1, u in forward orientation overlaps v hence rel uv = 0 (d) u and v do not have the same orientation in the overlap hence or uv = 1, u in forward orientation is overlapped by v hence rel uv = 1

Property 2.3: Sizes of the oriented walks based bi-directed graph

Let G = (V , E) be an oriented walks based bi-directed graph:

-|V | = |R aw | = 1 2 × |R| -|E| = 1 2 × |O|
As the vertices represent unoriented reads and the overlaps are succession relationships between two oriented reads, it is necessary to define a variable for each vertex that gives its orientation:

Definition 2.5: Vertex orientation variable

At each vertex v ∈ V is associated a variable v or that gives its orientation.

Given an overlap between two oriented reads, the variables of the two vertices that correspond to them (but unoriented) must respect their orientation. Definition 2.6 formalises this constraint that named co-validity constraint:

V. Epain

Definition 2.6: Co-validity for the orientation variables of the edge' extremities

Let (u, v) ∈ E be an edge. The orientation variables u or and v or are co-valid according the edge's attributes when:

-they are co-valid for or uv attribute:

|u or -v or | = or uv
-they are co-valid for rel uv attribute:

u or = rel uv if u rid < v rid |(1 -or uv ) -rel uv | if u rid > v rid
To know if the orientation variables are co-valid, the identifiers of the two consecutive vertices have to be compared. To avoid this verification, one may remark that the attribute rel uv equals to 1 -rel vu , and can suggest a change in the attribute value, depending on the vertex u or v from which the edge (u, v) is considered. But this would contradict the bi-directed graph paradigm philosophy (which is a undirected graph paradigm) since having two different edge attributes rel uv and rel vu implies that the graph is directed.

As the graph is bi-directed, it is possible to define a reverse operation. Analogously to Definition 2.2, Definition 2.7 formalises the reverse operation in the bi-directed graph.

Definition 2.7: The reverse operation for vertices and edges in the oriented walk based bi-directed graph

Vertices For a given vertex v ∈ V and a fixed orientation variable v or , v denotes its reverse, where:

-

v rid = v rid -v or = 1 -v or
Edges For a given edge e = (u, v) ∈ E and fix co-valid orientation variables u or and v or , e = v, u denotes its reverse.

According to Definition 2.4, given (u, v) ∈ E and one orientation for u or for v, it is necessary to check rel uv value to determine the succession relationship between oriented u and oriented v. This particularity makes the bi-directed graph oriented 16

V. Epain walk dependent. Definition 2.8 specifies what a valid walk is in this graph.

Definition 2.8: Walking in oriented walk based bi-directed graph

A valid walk results in a path

p = v 0 v 1 • • • v n-1 ∈ V n | n ∈ N in the graph G = (V , E
, or E , rel E ) that respects the following criteria:

Contiguity

-Two consecutive vertices in the path must be connected by an edge in the graph:

∀i | 0 ≤ i < n -1, (v i , v i+1 ) ∈ E
-Given the vertices' orientation v ior and v i+1 or , they must be covalid.

Exclusive orientation At most one orientation is chosen for each vertex:

∀v i , v j ∈ p, v i = v j =⇒ i = j Figure 7
gives an example of a valid walk in the bi-directed graph. Note that walking in this graph is not similar to walking in a classical undirected graph because the orientation variables must be co-valid. A valid walk is coloured in red. As the graph is undirected, the resulting path can be read in two possible ways: from vertex v or from vertex x. Let p v = vux the one that begins from v such that v or = 0, u or = 0, x or = 1. Thus, p x = xuv is the one that begins from x such that x or = 0, u or = 1, v or = 1. Note that p x = p v . In (a) edges are drawn bidirected while in (b) they are drawn undirected.

Thanks to edges attributes or E and rel E , the bi-directed graph inherits a reverse symmetry property analogous to Property 1.1:

V. Epain

Property 2.4: Reverse symmetry for the edges

Given an edge (u, v) ∈ E and its attributes or uv and rel uv , an overlap and its reverse are encoded in the graph.

Proof

Without any loss of generality, let suppose that u identifier is lexicographically less that this of v.

-If or uv = 0:

-if rel uv = 0, then: if u orientation is fixed forward, then overlap (u f , v f ) is obtained; while if u orientation is fixed reverse, then (v r , u r ) is obtained (because rel uv determines if oriented v is after or before u in forward orientation) -else: if u orientation is fixed forward, then overlap (v f , u f ) is obtained; while if u orientation is fixed reverse, then (u r , v r ) is obtained.
-Else:

-if rel uv = 0, then: if u orientation is fixed forward, then overlap

(u f , v r ) is obtained; while if u orientation is fixed reverse, then (v f , u r ) is obtained.
-else: if u orientation is fixed forward, then overlap (v r , u f ) is obtained; while if u orientation is fixed reverse, then (u r , v f ) is obtained.

Undirected Graph: Tail-Head Fragments Based

A new undirected graph structure was presented by E. W. Myers in 2005 [START_REF] Myers | The fragment assembly string graph[END_REF]: one read is represented by its tail and its head. Both the tail and the head are vertices, and there is one edge from the tail to the head. Passing through first the tail and then the head corresponds to choose the read in forward orientation, while passing through first the head and then the tail corresponds to choose it in reverse orientation. This new type of edges are called read-edges, at the opposite of overlap-edges that correspond to overlaps. A walk in the graph must alternate between read-edges and overlap-edges. This representation was also described in the Mäkinen et al.'s book [START_REF] Veli Mäkinen | Genome-Scale Algorithm Design[END_REF] and by Li [START_REF] Li | Minimap and miniasm: Fast mapping and de novo assembly for noisy long sequences[END_REF] for its assembly method.

Definition 2.9: Tail-head Fragments Based undirected graph

Let G = (V , E) a undirected graph such that:

-V is the set of vertices, where each v ∈ V represents one of the extremity of one read. For each read, there are two vertices v t , v h (respectively for the tail of the read, and for its head). Thus, each v ∈ V has the following attributes:

-v rid ∈ N the identifier of the read it represents -v ext ∈ {0; 1} the extremity of the read it represents (equals to 0 if it is the head, else equals to

1 if it is the tail a ) -E = E R ∪ E O
is the set of edges, such that:

-each undirected read-edge (v t , v h ) ∈ E R encodes the two possible read orientations (forward if from v t to v h , else reverse)

-each undirected overlap-edge (u, v) ∈ E O represents which extremity of read u is overlapping which extremity of read v a The values for the extremities are arbitrary: while selecting 0 for the tail and 1 for the head appears more natural, switching the values will be interesting later.

Figure 8 shows for all the overlap cases how they are represented in the undirected graph.

(a) (u f , v f ) ∈ O (b) (v f , u f ) ∈ O (c) (u f , v r ) ∈ O (d) (v r , u f ) ∈ O Figure 8
-Overlap cases in the undirected graph. u t , u h and v t , v h are respectively the tail and the head of reads u and v. Dashed edges correspond to read-edges while plain edges correspond to overlap-edges. Each subfigure illustrates one overlap impact on the undirected graph:

(a) (u h , v t ) ∈ E (b) (v h , u t ) ∈ E (c) (u h , v h ) ∈ E (d) (v t , u t ) ∈ E.

V. Epain

Property 2.5: Sizes of the tail-head fragment based undirected graph

Let G = (V , E) be an oriented walks based bi-directed graph:

-|V | = 2 × |R aw | = |R| -|E| = 1 2 × |O| + |R aw |
As for each read there are two vertices that represent their two extremities, it is possible to define a reverse operation. Analogously to Definitions 2.2 and 2.7, Definition 2.10 formalises the reverse operation in the undirected graph.

Definition 2.10: The reverse operation for vertices and edges in the tail-head fragment based undirected graph

Vertices For a given vertex v ∈ V , v denotes its reverse, where:

-

v rid = v rid -v or = 1 -v or
Edges For a given edge e = (u, v) ∈ E, e = (v, u) denotes its reverse.

Because of the partition of edges set E in two subsets, walking in this graph does not correspond to a traditional undirected graph walk. Definition 2.11 specifies what a valid walk is in this graph.

Definition 2.11: Walking in tail-head fragments based undirected graph

A valid walk results in a path

p = v 0 v 1 • • • v 2k-1 ∈ V 2k | k ∈ N in the graph G = V , E R ∪ E O that
respects the following criteria:

Contiguity Read-edges and overlap-edges alternate in the path:

-odd-numbered edges in the path are read-edges:

∀i | 0 ≤ i < k, (v 2i , v 2i+1 ) ∈ E R
-even-numbered edges in the path are overlap-edges:

∀i | 1 ≤ i < k, (v 2i-1 , v 2i ) ∈ E O
Exclusive orientation At most one orientation is chosen for each vertex:

∀v i , v j ∈ p, v i = v j =⇒ i = j 20 V. Epain
Note that walking in this graph is not similar that walking in a classic undirected graph, because a valid walk must alternate between read-edges and overlap-edges. Figure 5 gives an example of a valid walk in the undirected graph. A valid walk is coloured in red. As the graph is undirected, the resulting path can be read in two possible ways: from vertex v t or from vertex x t . Let p v = v t v h u t u h x h x t the one that begins from v t , thus p x = x t x h u h u t v h v t is the one that begins from x t . Note that p x = p v .

Because the set of vertices contains the two extremities of each read, the undirected graph inherits a reverse symmetry property analogous to Property 1.1:

Property 2.6: Reverse symmetry for the read-edges and the overlap-edges

Given one overlap-edge (u, v) ∈ E O and the two read-edges (u t , u h ) ∈ E R and (v t , v h ) ∈ E R , one overlap and its reverse are encoded in the graph.

-

∀(v t , v h ) ∈ E, (v h , v t ) ∈ E
, where v t corresponds to the tail of read v and v h corresponds to its head.

-

∀(u, v) ∈ E, (v, u) ∈ E. Proof -Read-edge (v t , v h ) corresponds to reading read v in forward orientation, hence (v h , v t
) correspond to reading it in reverse orientation.

-Let (u, v) ∈ E O be an overlap-edge, hence read-edges u, u and v, v are considered. Moreover, overlap-edge (v, u) is also in E O , hence read-edges u, u and v, v are considered, and they correspond to the V. Epain

Overlap Graph Implementations

For each graph paradigm in Section 2 at least one implementation is proposed in Sections 3.1 to 3.3. A map of all implementations and the graph paradigms they follow is illustrated in Figure 3.

In the following, let consider that all the overlaps in overlaps set O are kept, and reads in reads set R aw participate in at least one overlap. Also let suppose that min r∈Raw r rid = 0 and max r∈Raw r rid = |R aw | -1. The previous assertions permit to easily build an index on read identifiers rid. Also, mathematical terms as G = (V , E) remain the same as in Section 2.

Directed Graph: Oriented Fragments Based

Section 3.1.1 describes the first implementation idea for the oriented fragment based directed graph, while Sections 3.1.2 and 3.1.3 takes the benefits of reverse symmetry to build a more clever implementation.

All Oriented Fragments Directed Graph (DGA)

For each read, there are two vertices in the directed graph. Remind that each read identifier r rid corresponds to a unique integer identifier (it is an index, see Definition 1.1).

The All Oriented Fragments Directed Graph (DGA) implementation is the first and the simplest idea that follows a classical directed graph implementation. Thus, for each read r ∈ R aw there are two vertices v f , v r ∈ V such that the index of v f is equal to 2 × r rid and the index of v r is equal to 2 × r rid + 1. Definition 3.1 formalises indices sets. It is possible now to build the two adjacency lists: the first one for the predecessors, the second one for the successors. They both contain respectively the index of each predecessor, resp. of each successor vertices as the same way as a classic directed graph implementation. They also contain the index of the edge. Definition 3.2 details the way the implementation is built. add edge index Definition 3.2: DGA implementation DGA graph implementation is built by:

Predecessor list N - V ∀v ∈ V , ∀u ∈ N - v , u ind is the index of a predecessor of vertex v Successor list N + V ∀v ∈ V , ∀w ∈ N + v ,

Proposition 3.1: DGA memory consumption

The memory size of the graph M em(DGA) (in octets) is equals to:

M em(DGA) = 2 × (2 × |R aw | + 1) × P + 2 × |O| × 1 + log 2 |R aw | 8 + log 2 |O| 8
where P is the memory size of a memory address.

V. Epain

Figure 10 -All oriented fragments directed graph implementation. At the top left, the dot lined box corresponds to the legend for each of the four overlap cases. The grey mathematical formula above provides the overlap and its reverse symmetric overlap, under parenthesis, for the illustrated case. Under, there are the two adjacency lists (the first one contains the predecessors, the second one contains the successors): they both contain the indices of the predecessors/successors. At the top right, the grey box gives some graph properties.

Proof proof here

24

V. Epain

Only Oriented Fragments' Successors Directed Graph (DGS)

DGA implementation suffer from redundancies in the data because it does not take benefits from the reverse symmetry. Only Oriented Fragments' Successors Directed Graph (DGS) implementation takes benefits from the symmetry hence while the structure follows the one of DGA, only the successor list is kept. Definition 3.3 details how it is built in memory.

add edge index Definition 3.3: DGS implementation

DGS graph implementation is built by the successor list N + V such that ∀v ∈ V , ∀w ∈ N + v , w ind is the index of a successor of vertex v. Also, for each successor w of vertex v Figure 11 illustrates the impact of each overlap type on DGS implementation. For clarity's sake, only the indices of the successors are written, but not the edge indices.

Proposition 3.2 gives the amount of octet DGS implementation consumes.

Proposition 3.2: DGS memory consumption

The memory size of the graph M em(DGS) (in octets) is equals to:

M em(DGS) = (2 × |R aw | + 1) × P + |O| × 1 + log 2 |R aw | 8 + log 2 |O| 8
where P is the memory size of a memory address.

Proof

For each vertex there is a pointer to its successor list, hence At the top left, the dot lined square corresponds to the legend for each of the four overlap cases. The grey mathematical formula above provides the overlap and its reverse symmetric overlap, under parenthesis, for the illustrated case. Under, there is the successor list: it contains the indices of the successors. At the top right, the grey square gives some graph properties. Proposition 3.3 answer the issue of getting the predecessors.

Proposition 3.3: DGS reverse symmetry to retrieve predecessors

For each vertex v ∈ V : i. its predecessors are the reverse of its reverse' successors

26

V. Epain

ii. the edge index of (u, v) ∈ E is the reverse of this of v, u ∈ E

Proof

Let v ∈ V be a vertex. Let u ∈ V such that (u, v) ∈ E. Thus: i. v, u ∈ E, hence u is the successor of v that is the reverse of v.

Finally, u = u, that is the predecessor of v.

ii. If e ind is the edge index of edge v, u , then e ind = e ind + c (where c = 1 if e ind is even, else c = -1) corresponds to the edge index of the reverse of v, u hence the edge index of (u, v).

Forward Fragments Directed Graph (DGF)

As for DGS implementation, the last implementation of the directed graph structure, Forward Fragments Directed Graph (DGF), takes benefits from the reverse symmetry. DGF focuses only on the neighbours of the vertices that represent the reads in forward orientation (hence the reads in raw reads set R aw ). Therefore, the vertices indices set is not build as previously. Hence for each read r ∈ R aw , let v ind = r rid be the index of the vertex that represents it. Because an overlap involves two oriented reads, the neighbours' orientation must be included to the adjacency lists. Hence for each neighbour v ∈ V in the predecessors/successor lists of a forward vertex, let v indor = (v ind,vor ) be its oriented neighbour. Definition 3.4 describes the different sets, and Definition 3.5 details the DGF implementation. For clarity's sake, only the indices of the predecessors/successors are written, but not the edge indices.

Definition 3.4: Graph indices set for DGA

Let V ind = 0; |R aw | be the set of indices for the vertices:

- Predecessor list for the forward

|V ind| = |R aw | -∀v ind ∈ V ind, v ind = v rid ,
N - V f ∀v ∈ V f , ∀u ∈ N - v ,
u ind is the index of a predecessor of vertex v, and u or gives its orientation

Successor list for the forward N

+ V f ∀v ∈ V f , ∀w ∈ N + v ,
w ind is the index of a successor of vertex v, and w or gives its orientation

Proposition 3.4: DGF memory consumption

The memory size of the graph M em(DGF ) (in octets) is equals to:

M em(DGF ) = 2 × (|R aw | + 1) × P + |O| × 1 + log 2 |R aw | 8 + log 2 |O| 8
where P is the memory size of a memory address.

Proof

For each (forward) vertex there is a pointer to its predecessor and successor lists, hence 2×|R aw | pointers, and there is one pointer to the vertices' predecessor and successor lists (hence +2). Then, for each predecessor/successor, its index and a boolean orientation value are provided ( log 2 2 × |R aw | bits), and the edge index is provided too ( log 2 |O| bits). These numbers are divided by eight and rounded up to the nearest integer to get the number of

V. Epain

Figure 12 -Forward fragments directed graph implementation. At the top left, the dot lined square corresponds to the legend for each of the four overlap cases. The grey mathematical formula above provides the overlap and its reverse symmetric overlap, under parenthesis, for the illustrated case. Under, there are the two adjacency lists for the forward (the first one contains the predecessors, the second one contains the successors): they both contain the couples index-orientation of the predecessors/successors. At the top right, the grey square gives some graph properties.

octets. Then the sum is multiplied by the number of overlaps (|O|). verify if same with commented

V. Epain

Note that in contrast to Proposition 3.2, the memory consumption of adjacency lists pointers is equals to 2×(|R aw | + 1) (versus (2 × |R aw | + 1)). In fact, the extra P is due to an extra adjacency list. Proposition 3.5 answer the issue of getting the predecessors/successors of the reverse.

Proposition 3.5: DGF reverse symmetry to retrieve predecessors

For each vertex v ∈ V r : i. its predecessors are the reverse of its reverse' successors ii. its successors are the reverse of its reverse' predecessors iii. the edge index of (u, v) ∈ E is the reverse of this of v, u ∈ E Proof Let v ∈ V [ r] be a vertex that represents a reverse read.

-Let u ∈ V such that (u, v) ∈ E. Thus: i. v, u ∈ E, hence u is the successor of v that is the reverse of v.

Finally, u = u, that is the predecessor of v.

ii. If e ind is the edge index of edge v, u , then e ind = e ind + c (where c = 1 if e ind is even, else c = -1) corresponds to the edge index of the reverse of v, u hence the edge index of (u, v).

-Let w ∈ V such that (v, w) ∈ E. Thus: i. w, v ∈ E, hence w is the predecessor of v that is the reverse of v. Finally, w = w, that is the successor of v.

ii. If e ind is the edge index of edge w, v , then e ind = e ind +c (where c = 1 if e ind is even, else c = -1) corresponds to the edge index of the reverse of w, v hence the edge index of (v, w).

30

V. Epain

Bi-directed Graph: Oriented Walk Based

Forward Fragments Bi-directed Graph (BG)

In the bi-directed graph, there is one vertex for each raw read in R aw . Hence for each vertex v is associated an index v ind = v rid . An overlap and its reverse are represented by only one edge that carries strictly necessary overlap attributes, as described in Definition 2.4. Remind that the bi-directed graph is equivalent to a undirected graph: that's implemented by Unoriented Fragments Bi-directed Graph (BG) implementation. Definition 3.4 describes the different sets, and Definition 3.5 details the DGF implementation. For clarity's sake, only the indices of the predecessors/successors are written, but not the edge indices.

Definition 3.6: Graph indices set for BG

Let V ind = 0; |R aw | be the set of indices for the vertices:

- At the top, the dot lined square corresponds to the legend for the four overlap cases. The mathematical formula above the line is the overlap such that u is in forward orientation, and the reverse symmetric overlap is under parenthesis. Under the line, there is the one list that contains, in order, the index of the neighbour, the value of or uv and the value of rel uv .

|V ind| = |R aw | -∀v ind ∈ V ind, v ind = v rid ,

Proposition 3.6: BG memory consumption

The memory size of the graph M em(BG) (in octets) equals:

M em(BG) = (|R aw | + 2) × P + |O| × log 2 |R aw | 8 + log 2 |O| -1 8 + |O| 8 32 V. Epain
where P is the memory size of a memory address.

Proof

For each (unoriented) vertex there is a pointer to its neighbour list, hence |R aw | pointers, and there is one pointer to the vertices' neighbour list and one to the edges attribute list (hence +2). Then, for each neighbour, its index is provided ( log 2 |R aw | bits), and the edge index is provided too ( log 2 1 2 × |O| bits). These numbers are divided by eight and rounded up to the nearest integer to get the number of octets. Then the sum is multiplied by the number of overlaps (|O|). Finally, for each edge index ( 12 × |O|), there are two boolean edge attributes. 1 2 × |O| × 2 is divided by eight and rounded up to get the number of octets.

verify if same as comments

The four combinations of edges' attributes or and rel let representing all the overlap cases and their reverse without any redundancy. To verify the reverse symmetry, it is sufficient (and easier) to choose an orientation of u and calculate the overlap case with the edges' attributes. For each read, there are two vertices in the directed graph. Remind that each read identifier r rid correspond to a unique integer identifier (it is an index, V. Epain see Definition 1.1). Thus, for each read r ∈ R aw there are two vertices v f , v r ∈ V such that the index of v f is equal to 2×r rid and the index of v r is equal to 2×r rid +1.

Forward Fragments Directed Graph (DGF)

It is possible now to build the adjacency lists (one list for the predecessors, and another one for the successors). At the top left, the dot lined square corresponds to the legend for the four overlap cases. The grey mathematical formula above is the overlap such that u is in forward orientation, and the reverse symmetric overlap is under parenthesis. Under, there are the two adjacency lists (the first one contains the neighbours for overlap-edges, the second one contains the neighbours for read-edge): they both contain the indices of the neighbours. Top right grey square gives some graph properties. list ind ← 0 V. Epain preds.append(u, e ind )

for (u, u or , e ind ) ∈ N + v do 7:

preds.append(u, 1 -u or , e ind ) if v or = 0 then 6:

if rel uv = 1 then u f → v f or u r → v f 7:
preds.append(u, orientations[or uv ], 2 × e ind )

8:

else if rel uv = 0 then u f → v r or u r → v r 9:
preds.append(u, orientations[1 -or uv ], 2 × e ind + 1)

10:

else if v or = 0 then 11:

if or uv = 0 then 12:

if rel uv = 0 then u f → v f 13:
preds.append(u, 0, 2 × e ind )

14:

else if rel uv = 1 then u r → v f 15:
preds.append(u, 1, 2 × e ind + 1)

16:

else if or uv = 0 then 17:

if rel uv = 1 then u r → v r 18:
preds.append(u, 1, 2 × e ind + 1)

19:

else if rel uv = 0 then u f → v r 20:
preds.append(u, 0, 2 × e ind ) orientations ← (0, 1) forward/reverse orientations ind_edges is the number of edges. It is always even. ind_edges is the number of edges. It is always even.

N V .append(empty_list( )) 3: return |N V | -1 V. Epain
3: if u or = 0 then u f → v f or u f → v r 4:
N + u .append(v, v or , ind_edges)

5: else u f ← v f or u f ← v r 6: N - u .append(v, 1 -v or , ind_edges + 1) 7: if v or = 0 then u f → v f or u r → v f 8:
N - v .append(u, u or , ind_edges)

9: else u f ← v f or u r ← v f 10: N + v .append(u, 1 -u or , ind_edges + 1)
11:

ind_edges ← ind_edges + 2 ind_edges is the number of edges. E attr is a list of edges attributes. adj_ind ← get_index(N + u_rev , e ind , 1)

7: if adj_ind = N + u_rev -1 then 8:
Just delete the last element Replace the edge by the last in the neighbour list V. Epain Delete the whole vertex 28:

if v = N + V -2 then 29:
It is the last, just pop it and its reverse 30:

N + V .pop( ) 31: N + V .pop( ) 32:
else 33:

Replace it and its reverse by the last and its reverse 34:

N + v_rev ← N + V .pop( ) 35: N + v ← N + V .
if v = |N V | -1 then 13:
It is the last, just pop it The last (the greatest) identifier becomes a fewer and breaks the identifier order

+ u \ edge| = |N + u | -1 and |N - v \ edge| = |N - v | -1. 1: function dgs_delete_edge(G, u, v, e ind ) 2:
Remove v from u's successors |list| Delete all the list for i ∈ a; b do x (b -a + 1) × c(x) For loop best, worst and average cases are respectively rather lower and upper bounds, and equiprobable independent event's costs

if adj_ind = |N + u | -1 then V. Epain

Costs for Subfunctions

Best

Worst Average

DGS 5 × o - v + 2 DGF o - v + 1 4 × o - v + 3 2.5 × o - v + 2 BGU 3 × o v 6 × o v 4.75 × o v (

Costs for Dynamics

Table 4 gives the algorithmic costs of Algorithms 9 to 14. Table 5 gives the algorithmic costs of Algorithms 18 to 20. Table 6 gives the algorithmic costs of Algorithms 15 to 17.

× o v + 6 × R aw -3 2 × R aw × o z + 3 2 × u∈N - v ∪N + v o - u 2 + o + u 2 + 6 × R aw -3 4 × R aw × x∈N - z ∪N + z o - x 2 + o + x 2 - 1 2 ×   u∈N - v 1 o + u + w∈N + v 1 o - w   + 6 × R aw -1 R aw 5 × o v + 3 × R aw -3 R aw × o z +

Figure 2 -

 2 Figure 2 -Overlap cases between two sequences u and v are two sequences, represented by an arrow that shows the forward orientation. Each subfigure illustrates one overlap case: (a)u f overlaps v f (hence v r overlaps u r ) (b) v f overlaps u f (hence u r overlaps v r ) (c) u f overlaps v r (hence v f overlaps u r ) (d) v r overlaps u f (hence u r overlaps v f ).

Figure 3 -

 3 Figure3-Graph paradigms and their implementations respectively ordered chronologically and by logical adaptation. Blue boxes: they correspond to graph paradigms. They are described by the type of graph they represent, the number of vertices and edges if they have to be drawn. Green boxes: they correspond to discussed graph implementations. After their name, the second line gives the adjacency list(s) definition set(s), following by the description of the type it (they) contain(s), finally the last line give the length of the adjacency list(s) (i.e. the number of vertices for which the neighbours are given). Ungraph, digraph, and bigraph respectively stand for undirected graph, directed graph and bidirected graph.

Figure 5 -

 5 Figure 5 -Valid walk example in the oriented fragment based directed graph.A valid walk that begins from vertex v f is coloured in red. This walk results in a path p = v f u f x r .

Figure 4

 4 Figure 4 also illustrates Property 2.2.

Figure 7 -

 7 Figure 7 -Valid walk example in the oriented walks based bi-directed graph.A valid walk is coloured in red. As the graph is undirected, the resulting path can be read in two possible ways: from vertex v or from vertex x. Let p v = vux the one that begins from v such that v or = 0, u or = 0, x or = 1. Thus, p x = xuv is the one that begins from x such that x or = 0, u or = 1, v or = 1. Note that p x = p v . In (a) edges are drawn bidirected while in (b) they are drawn undirected.

Figure 9 -

 9 Figure 9 -Valid walk example in the tail-head fragment based undirected graph.A valid walk is coloured in red. As the graph is undirected, the resulting path can be read in two possible ways: from vertex v t or from vertex x t . Let p v = v t v h u t u h x h x t the one that begins from v t , thus p x = x t x h u h u t v h v t is the one that begins from x t . Note that p x = p v .

3. 1

 1 Digraph: Oriented Fragments Based reverse of the previous read-edges.

Figure 8

 8 Figure 8 also illustrates Property 2.6.

Definition 3 . 1 :

 31 Graph indices set for DGALet V ind = 0; 2 × |R aw | be the set of indices for the vertices:-|V ind| = 2 × |R aw | 22 V. Epain -∀v ind ∈ V ind, v ind = 2 × v rid + v or ,where v rid corresponds to the read's identifier and v or ∈ {0; 1} its orientation Let Eind = 0; |O| be the set of indices for the edges: -|Eind| = |O| -∀e ind ∈ Eind, e ind corresponds to the index of edge e, such that e ind -e ind = 1

Figure 10

 10 Figure 10 illustrates the impact of overlap cases on the structure. For clarity's sake, only the indices of the predecessors (successors) are written. Proposition 3.1 gives the amount of octet DGA implementation consumes.

Figure 11 -

 11 Figure 11 -Only oriented fragments successors directed graph implementation.At the top left, the dot lined square corresponds to the legend for each of the four overlap cases. The grey mathematical formula above provides the overlap and its reverse symmetric overlap, under parenthesis, for the illustrated case. Under, there is the successor list: it contains the indices of the successors. At the top right, the grey square gives some graph properties.

  where v rid corresponds to the read's identifier Let V indor = 0; |R aw | × {0; 1} be the set of indices enriched by a boolean value for the oriented vertices:-|V indor| = 2 × |R aw | V. Epain -∀v indor ∈ V indor, v indor = (v rid , vor ), where v rid corresponds to the read's identifier and v or to its orientation Let Eind = 0; |O| be the set of indices for the edges: -|Eind| = |O| -∀e ind ∈ Eind, e ind corresponds to the index of edge e, such that e ind -e ind = 1 add edge index Definition 3.5: DGF implementation DGF graph implementation is built by:

1 Definition 3 . 7 :

 137 where v rid corresponds to the read's identifier Let Eind = 0; 1 2 × |O| be the set of indices for the edges: -|Eind| = 1 2 × |O| -∀e ind ∈ Eind, e ind corresponds to the index of edge e put paragraph in definition Concerning the edge indices e ind , it is possible to use their euclidean quotient by two e ind in memory and retrieving them thanks to the orientation of the fewer vertex index (let say u). In fact, if the considered overlap uses u f , then e ind = 2 × e ind , else e ind = 2 × e ind + BG implementation BG graph implementation is built by: Neighbours list for the forward N V ∀v ∈ V , ∀w ∈ N v , w ind is the index of a neighbour of vertex v Edges attributes for each neighbour w of a vertex v two boolean values are provided: or vw and rel vw (see Definition 2.4)V. Epain

Figure 13 -

 13 Figure[START_REF] Li | Minimap and miniasm: Fast mapping and de novo assembly for noisy long sequences[END_REF] -caption title All four overlap cases structured in the bidirected graph. At the top, the dot lined square corresponds to the legend for the four overlap cases. The mathematical formula above the line is the overlap such that u is in forward orientation, and the reverse symmetric overlap is under parenthesis. Under the line, there is the one list that contains, in order, the index of the neighbour, the value of or uv and the value of rel uv .

description ref figure from digraph implementation revsymg memory 3 . 3

 33 Undirected Graph: Tail-Head Fragments Based 3.3.1 All Oriented Fragments Undirected Graph (UGA) fix for ungraph

Figure 14 -

 14 Figure 14 -caption title All four overlap cases structured in the directed graph.At the top left, the dot lined square corresponds to the legend for the four overlap cases. The grey mathematical formula above is the overlap such that u is in forward orientation, and the reverse symmetric overlap is under parenthesis. Under, there are the two adjacency lists (the first one contains the neighbours for overlap-edges, the second one contains the neighbours for read-edge): they both contain the indices of the neighbours. Top right grey square gives some graph properties.

Algorithm 1 :- 1 Algorithm 2 : 2 Require:

 1122 Reverse operation on indexRequire: Vertex/edge index ind. Ensure: Returns index of the reverse vertex/edge. 1: function rev(ind) For clarity's sake, rev(ind) = ind. Find place of edge index in the neighbour list. Cost: worst 3 × |list|, best 3, average 3 × |list| List of tuple list, edge index e ind , index t ind of the place of edge index in the tuple contained in list. The edge index must be in a tuple. Ensure: Returns the index of the tuple containing e ind in list. 1: function get_index(list, e ind , t ind ) 2:

3 :do 4 : 5 :list ind 4 . 1 . 2 Algorithm 3 : 3 :Algorithm 4 : 2 :then v forward 3 :

 34541233423 while list[list ind ][t ind ] = e ind and list ind < |list| -1 list ind ← list ind + 1 return Iterating Over the Predecessors Iterate over the predecessors for DGS Require: Graph G = (V , E), vertex v ∈ V , empty list preds. Ensure: The returned list contains the predecessors of v in graph G and the corresponding edge index. 1: function dgs_preds(G, v, preds) 2: for (u, e ind ) ∈ N + v do preds.append(u, e ind ) Iterate over the predecessors for DGF Require: Graph G = (V , E), vertex v ∈ V , orientation of v v or ∈ {0; 1}, empty list preds. Ensure: The returned list contains the predecessors of v in graph G and the corresponding edge index. 1: function dgf_preds(G, v, v or , preds) if v or = 0 for (u, e ind ) ∈ N - v do 4:

Algorithm 5 :

 5 Iterate over the predecessors for BGURequire: Graph G = (V , E), vertex v ∈ V , orientation of v v or ∈ {0; 1},empty list preds. Ensure: The returned list contains the predecessors of v in graph G and the corresponding edge index. 36 V. Epain

1 :

 1 function bgu_preds(G, v, v or , preds)

Algorithm 6 : 2 : 3 :Algorithm 7 :

 6237 Iterate over the successors for DGS Require: Graph G = (V , E), vertex v ∈ V , empty list succs. Ensure: The returned list contains the successors of v in graph G. 1: function dgs_succs(G, v, succs) for (w, e ind ) ∈ N + v do succs.append(w, e ind ) Iterate over the successors for DGF Require: Graph G = (V , E), vertex v ∈ V , orientation of v v or ∈ {0; 1}, empty list succs. Ensure: The returned list contains the successors of v in graph G.V. Epain

1 : 2 :then v forward 3 :do 4 : 6 :do 7 :Algorithm 8 :

 1234678 function dgf_succs(G, v, v or , succs) if v or = 0 for (w, e ind ) ∈ N + v succs.append(w, e ind ) for (w, w or , e ind ) ∈ N - v succs.append(w, 1 -w or , e ind ) Iterate over the successors for BGU Require: Graph G = (V , E), vertex v ∈ V , orientation of v v or ∈ {0; 1}, empty list succs. Ensure: The returned list contains the successors of v in graph G. 1: function bgu_succs(G, v, v or , succs) 2:

4. 1 . 5

 15 Adding an EdgeAlgorithm 12: Add a new edge and its reverse in the graph for DGS Require: Graph G = (V , E), (u, v) ∈ V 2 . Note that the vertices are already in the graph. Ensure: Returns the new edge's index (in forward orientation if there is the choice). 1: function dgs_add_edge(G, u, v) 2:

3 :rel ← 1 -v or 8 :return 2 × 2 : 4 : 5 :

 3182245 or ← |u or -v or | N u .append(v, ind_edges) 9: N v .append(u, ind_edges) 10: E attr .append(or, rel) (ind_edges -1) 4.1.6 Deleting a Vertex Algorithm 15: Delete a vertex for DGS Require: Graph G = (V , E), vertex v ∈ V (in forward orientation). Ensure: Delete the vertex and its reverse such that V = V \ v, v , and ∀v ∈ V , 0 ≤ v ind ≤ |V | -2. 1: function dgs_delete_vertex(G, v) Delete it from its predecessors 3: v_rev ← v + 1 for (u, e ind ) ∈ N + v_rev do

2 : 4 : 8 :

 248 for (w, e ind ) ∈ N v do 3: adj_ind ← get_index(N w , e ind , 1) if adj_ind = |N w | -Replace the edge by the last in the neighbour list 9: N w [adj_ind] ← N w .pop( )

  , e ind ) ∈ N v do 20: adj_ind ← get_index(N w , e ind , 1) 21: N w [adj_ind] ← (v, e ind )

E

  attr [e ind ] ← (E attr [e ind ][0], 1 -E attr [e ind ][1]) 4.1.7 Deleting an Edge Algorithm 18: Delete an edge for DGS Require: Graph G = (V , E), edge (u, v) ∈ E and the edge's index e ind . Ensure: |N

3 :

 3 adj_ind ← get_index(N + u , e ind , 1)4:

+ 5 × 4 BGU 5 ×

 545 (o z + 1) DGF 9 × o v + 4 × o z + 3 × o v + 3 × o z + 3 × Average cases (DGS, DGF and BGU) 10 × o v + 10 × R aw -5 2 × R aw × o z + 3 ×

alignment

  Nucleotide comparison between at least two sequences 7, 8

1

  Introduction 1.1 Reads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Overlaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Storing Overlaps in a Graph Structure 2.1 Directed Graph: Oriented Fragments Based . . . . . . . . . . . . . . . 2.2 Bi-directed Graph: Oriented Walk Based . . . . . . . . . . . . . . . . 2.3 Undirected Graph: Tail-Head Fragments Based . . . . . . . . . . . . . Deleting an Edge . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Time Complexities . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Complexities Calculus Details . . . . . . . . . . . . . . . . . . . 4.2.2 Costs for Subfunctions . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Iterating Over the Neighbours . . . . . . . . . . . . . . . . . . . 4.2.4 Costs for Dynamics . . . . . . . . . . . . . . . . . . . . . . . .

3 Overlap Graph Implementations 3.1 Directed Graph: Oriented Fragments Based . . . . . . . . . . . . . . . 3.1.1 All Oriented Fragments Directed Graph (DGA) . . . . . . . . . . 3.1.2 Only Oriented Fragments' Successors Directed Graph (DGS) . . . . 3.1.3 Forward Fragments Directed Graph (DGF) . . . . . . . . . . . . 3.2 Bi-directed Graph: Oriented Walk Based . . . . . . . . . . . . . . . . 3.2.1 Forward Fragments Bi-directed Graph (BG) . . . . . . . . . . . . 3.2.2 Forward Fragments Directed Graph (DGF) . . . . . . . . . . . . 3.3 Undirected Graph: Tail-Head Fragments Based . . . . . . . . . . . . . 3.3.1 All Oriented Fragments Undirected Graph (UGA) . . . . . . . . . 3.3.2 Read-edges Jump Directed Graph (DGS) . . . . . . . . . . . . . 4 Memory and Time Costs 4.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Subfunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Iterating Over the Predecessors . . . . . . . . . . . . . . . . . . 4.1.3 Iterating Over the Successors . . . . . . . . . . . . . . . . . . . 4.1.4 Adding a Vertex . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.5 Adding an Edge . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.6 Deleting a Vertex . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.7

Definition 2.3: Walking in oriented fragment based directed graph

	A valid walk results in a valid path p
	Definition 2.3 specifies what a valid walk (and a valid path) is in this graph:
	12	V. Epain

Algorithm 13: Add a new edge and its reverse in the graph for DGF Require:

  Graph G = (V , E), (u, v) ∈ V 2 , with their orientation (u or , v or ) ∈ {0; 1} 2 . Note that the vertices are already in the graph. Ensure: Returns the new edge's index (in forward orientation if there is the choice). 1: function dgf_add_edge(G, u, u or , v, v or )

	3: 4:	N + u .append(v, ind_edges) N + v .append(u, ind_edges + 1)
	5:	ind_edges ← ind_edges + 2
	6:	card_edges ← card_edges + 2
	7:	return ind_edges -2
	2:

Add a new edge and its reverse in the graph for BGU Require:

  Graph G = (V , E), (u, v) ∈ V 2 , with their orientation (u or , v or ) ∈ {0; 1} 2 . Note that the vertices are already in the graph. Ensure: Returns the new edge's index (in forward orientation if there is the choice). 1: function bgu_add_edge(G, u, u or , v, v or )

	Algorithm 14: 2:
	12:	card_edges ← card_edges + 2
	13:	return ind_edges -2
	40	V. Epain

  pop( ) Delete the vertex and its reverse such that V = V \ v, v , and ∀v ∈ V , 0 ≤ v ind ≤ |V | -2.

	Ensure:
	36:	Update the vertex index
	37:	for (w, e ind ) ∈ N + v do
	38:	w_rev ← w
	39:	e ind _rev ← e ind
	40:	adj_ind ← get_index(N + w_rev , e ind _rev, 1)
	41:	N + w_rev [adj_ind] ← (v_rev, e ind _rev)
	42:	for (w, e ind ) ∈ N + v_rev do
	43:	w_rev ← w
	44:	e ind _rev ← e ind
	45:	adj_ind ← get_index(N + w_rev , e ind _rev, 1)
	46:	N + w_rev [adj_ind] ← (v, e ind _rev)
	42	V. Epain

1: function bgu_delete_vertex(G, v)

Table 1 -

 1 Calculus detail of basic operations costs. c(x) is the cost of element x.

	4.2 Time Complexities
	4.2.1 Complexities Calculus Details
	Table 1 details the calculus of algorithmic costs.
	Operation	Cost Description
	x	0 Memory access
	x ± y	1 + c(x) + c(y) Basic operation
	x ← y	c(y) Affectation
	|x|	1 + c(x) Absolute value or element's length
	if x y	1 + c(x) + c(y) Conditional
	empty_list()	1 Empty list constructor
	list.append(x)	1 + c(x) Add x to the end of the list list
	list.pop()	1 Delete the last element of the list list
	delete(list)

Table 2

 2 gives the algorithmic costs of subfunctions in Algorithms 1 and 2.

Table 2 -

 2 Algorithmic costs for subfunctions.

		Best	Worst	Average
	rev		2
	get_index	3	3 × |list|	3 ×	|list| 2
	4.2.3 Iterating Over the Neighbours

Table 3

 3

	gives the algorithmic costs of Algorithms 3 to 8.
	48	V. Epain

Table 3 -

 3 Algorithmic costs of iterating over the neighbours for DGS, DGF and BGU.

	(a) Iterate over the predecessors

  b) Iterate over the successors

		Best	Worst	Average
	DGS		o + v
	DGF	o + v + 1	4 × o + v + 3	2.5 × o + v + 2
	BGU	3 × o v	6 × o v	4.75 × o v

Table 4 -

 4 Algorithmic costs of adding a vertex or an edge for DGS, DGF and BGU.

		Add a vertex		Add an edge
	Best	Worst	Average	Best	Worst	Average
	DGS	5			8
	DGF	5		6	10	8
	BGU	3			9

Table 5 -

 5 Algorithmic costs of deleting an edge for DGS, DGF and BGU.

						(a) Best and Worst cases
						Best				Worst
				DGS			17	3 × (o + u + o -v ) + 13
				DGF			17	3 × (o -u + o + v ) + 17
				BGU			14	3 × (o u + o v ) + 10
						(b) Average case
	DGS							3 ×		o + u 2	+	o -v 2	+ 13 -	1 o + u	-	1 o -v
	DGF	3 2	×	o -u 2	+	o + u 2	+	o -v 2	+	o + v 2		+ 13 -2 ×	1 o u	+	1 o v
	BGU							3 ×	o u 2	+	o v 2	+ 11 -	1 o u	-	1 o v
	50														V. Epain

Table 6 -

 6 Algorithmic costs of deleting a vertex for DGS, DGF and BGU.

  3 × Forward orientation 6-8, 12, 13, 15, 18, 19, 22, 28, 34, 37, 38, 40, see forward ind Index 22, 23, 25, 27, 28, 30, 31, 35-38, 41-47 indor Index with boolean orientation 27, 28 or Orientation 11, 12, 15-17, 20, 22, 23, 27, 28, 36-38, 40, 41, 43, 44, 46, 47, see forward & reverse r Reverse orientation 6-8, 12, 13, 15, 18, 19, 22, 30, 34, 37, 38, 40, see reverse rid Read identifier 5, 6, 11, 12, 14, 16, 19, 20, 22, 27, 28, 31, 33, 34 Graph G Graph object 11-13, 15, 17, 20, 22, 36-41, 43-47, see undirected graph, directed graph, bi-directed graph, vertex & edge V Vertices set 11-17, 19, 20, 22, 23, 25-28, 30, 31, 34, 36-47, see vertex E Edges set 11-23, 27, 28, 30, 31, 36-41, 43-47, see edge N Neighbours set 31, 37-39, 41, 45, 47, 51, see edge N -Predecesors set 23, 28, 36, 38-40, 43-47, 51, see edge, N & N + N + Successors set 23, 25, 28, 36-47, 51, see edge, N & N - The set of natural (positive) integer 5, 6, 11, 13, 14, 17, 19, 20 O Set of overlaps 8, 9, 12, 14, 15, 19-23, 25, 28, 29, 31-33 R aw Set of raw reads 5-7, 12, 15, 20, 22, 23, 25, 27, 28, 30-34, 51 R Set of reads 6-9, 12, 14, 15, 19-21 R ev Set of reversed raw reads 6

	SYMBOLS	SYMBOLS
	w∈Nv BG Unoriented Fragments Bi-directed Graph 31, 32 o w 2 B | C | D B C CSC Compressed Sparse Column 9 CSR Compressed Sparse Row 9 D DGA All Oriented Fragments Directed Graph 22, 23, 25, 27 + 3 × R aw + 3 2 × R aw -w∈Nv 1 o w + DGF Forward Fragments Directed Graph 27, 28, 30, 31 DGS Only Oriented Fragments' Successors Directed Graph 25-27 DNA Deoxyribonucleic Acid 1, 5, 7 Symbols Attributes | Functions | Graph | Operations | Sets Attributes f seq Nucleotide sequence 5-7 Functions strand_iid Read identifier function 5-7 Operations • Reverse operation 6-9, 12-14, 16, 17, 20, 21, 23, 27, 28, 30, 35, 36, 38, 40-47, × y∈Nz o y 2 4 × R aw -1 R aw see reverse & rev Sets N Σ Alphabet set 5 V. Epain Acronyms V. Epain i ii V. Epain

  assembly Method used to reconstruct genomes from fragments 1, 6, 7, 11, 14 assembly graph One of the output of genome assembly method see assembler B bi-directed graph Graph that contains 3 edge types 1, 11, 14-17, 20, 31, 32 Graph where the edges are directed 1, 11-13, 22-24, 26, 27, 29, 33, 34

	E
	edge Component of a graph that connects two vertices 9, 11-23, 25, 27, 28, 30, 31,
	33, 34, see graph & vertex
	F
	forward Original sequence orientation 6-8, 11, 14, 15, 18, 19, 21, 27-29, 31, 32, 34,
	see reverse
	fragment Generic nucleotide fragment 1, 5, 11-13, 20-22, 24, 26, 29
	G
	genome Entire set of DNA instructions found in a cell 7
	graph Object composed of vertices connected by edges 1, 9, 11-14, 16-18, 20-29,
	31, 34, see vertex & edge
	V. Epain	iii

C

contig Merge, consensus of reads obtain by assembly method(s) see assembler

D directed graph

V. Epain

Algorithm 16: Delete a vertex for DGF Require: Graph G = (V , E), vertex v ∈ V (in forward orientation). Ensure: Delete the vertex and its reverse such that V = V \ v, v , and

Delete it from its predecessors 3: for (u, u or , e ind ) ∈ N - v do 4:

if u or = 0 then 5:

adj_ind ← get_index(N + u , e ind , 1)

6:

Just delete the last element 8:

N + u .pop( )

else 10:

Replace the edge by the last in the neighbour list 11:

adj_ind ← get_index(N - u , e ind , 1)

Just delete the last element Replace the edge by the last in the neighbour list 19:

card_edges ← card_edges -2

21:

delete(N - v )

22:

Delete it from its successors 23:

for (w, w or , e ind ) ∈ N + v do

24:

if w or = 0 then 25:

adj_ind ← get_index(N - w , e ind , 1)

Just delete the last element

It is the last, just pop it and its reverse 45:

else 48:

Replace it and its reverse by the last and its reverse 49:

Update the vertex index 52:

Algorithm 17: Delete a vertex for BGU

V. Epain

5:

Just delete the last element 6:

Replace the edge by the last in the neighbour list 9:

Remove u from v's predecessors.

11:

adj_ind ← get_index(N + v_rev , e ind , 1)

13:

Just delete the last element 15:

Replace the edge by the last in the neighbour list 18:

Algorithm 19: Delete an edge for DGF Require: Graph G = (V , E), edge (u, v) ∈ E, with their orientation (u or , v or ) ∈ {0; 1} 2 , and the edge's index e ind . Ensure:

Remove v from u's successors Remove u from v's predecessors.

Euclidian division

3:

Remove v from u's neighbours.

4:

adj_ind ← get_index(N u , e ind , 1)

Just delete the last element 7:

N u .pop( )

Replace the edge by the last in the neighbour list 10:

Remove u from v's neighbours.

12:

adj_ind ← get_index(N v , e ind , 1)

Just delete the last element 15:


Jerome Lebrun
email: lebrun@i3s.unice.fr

Michel Buffa
email: michel.buffa@univ-cotedazur.fr

Jordan Sintes
email: jordan.sintes@gmail.com

From blues to rock to jazz : three different web audio tube guitar amplifier simulator plugins

We propose to present a set of web audio plugins specialized in three kinds of sounds…. The first one targets blues / classic rock sounds and proposes a drop down menu with presets that go from clean warm blues like the tones used by BB King, to more classic rock/blues distorted sounds used by Jimmy Hendrix or AC/DC. The second one is aimed to Hi Gain/Metal sounds similar Mesa Boogie type sounds, and the third one is an acoustic guitar simulator (use an electric guitar and get an acoustic folk guitar sound). These plugins are partially available in open source, but the versions we propose to demo are commercialized by our laboratory (French CNRS/SATT Sud-Est) and included in some commercial DAWs.

Introduction and related works

In 2012, Google Chrome proposed for the first time a low-latency opportunity to get live audio from a microphone or other audio inputs. Soon, Opera, Firefox and Microsoft Edge also implemented this. Chris Wilson's "Input Effects" demo was one of the first to show real-time sound processing effects written with Web Audio, and proposed implementations of famous effects such as delay, distortion, wah, etc. This impressive demo proved that low latency processing was achievable. Getting close to the real sound of an analog guitar amplifier remained nevertheless quite a challenge that Chris Wilson's examples did not fully address.

Many papers have been written about vacuum-tube guitar amplifiers modeling and about the characteristics of linear and nonlinear distortion effects suited for guitars [START_REF] Chang | DESC9115: Digital Audio Systems-Final Project Overdrive/Distortion[END_REF][START_REF] Macak | Real-time guitar tube amplifier simulation using an approximation of differential equations[END_REF][START_REF] Yeh | Numerical methods for simulation of guitar distortion circuits[END_REF][START_REF] Difilippo | Audio anecdotes: Tools, tips, and techniques for digital audio[END_REF]. Two main approaches are usually considered for the simulation of the different parts of a guitar amplifier: one is called the technique of virtual analog aka physical modeling. It consists in processing the electronic schematics using tools like the industry standard SPICE analog circuit simulator to translate the circuit into equations to be solved hopefully in real-time. These general equations are typically nonlinear differential algebraic equations and may be solved using integration methods, roots solver algorithms, and sparse matrix techniques. SPICE can even produce C++ code ready to be executed. However, it is often necessary to make huge simplifications and optimizations to achieve real-time processing. This is particularly the case with the modeling of the vacuum tubes used in guitar amplifiers and their interactions with other parts of the circuitry (see [START_REF] Pakarinen | A review of digital techniques for modeling vacuum-tube guitar amplifiers[END_REF] and [START_REF] Yeh | Discretization of the'59 Fender Bassman tone stack[END_REF] for a review of common techniques, and [START_REF] Macak | Real-time digital simulation of guitar amplifiers as audio effects[END_REF] for the method used by authors of the Guitarix.org project).

Another technique consists in a higher-level emulation, in which "logical" parts are identified (filters, tubes, etc.) and may be emulated manually or by machine learning [START_REF] Rollo | Black-Box modelling of nonlinear audio circuits[END_REF][START_REF] Eichas | Block-oriented modeling of distortion audio effects using iterative minimization[END_REF][START_REF] Eichas | Block-oriented gray box modeling of guitar amplifiers[END_REF][START_REF] Schmitz | Nonlinear modeling of the guitar signal chain enabling its real-time emulation[END_REF][START_REF] Wright | Real-Time guitar amplifier emulation with deep learning[END_REF] (as with the Kemper profiler/Guitar Rig 6 from Native Instruments, with Neural DSP's gears or Deepmind's WaveNet music generators) using separate or global, explicit or hidden models to achieve perceptual equivalence.

When we started to tackle this problem five years ago [START_REF] Buffa | Real time tube guitar amplifier simulation using WebAudio[END_REF], the separate, explicit approach was clearly the simpler and more adapted one to the Web Audio ecosystem esp. its limitations at the time (e.g. custom processing on audio samples was not usable without introducing latency or glitches, AudioWorklet node was not available). Furthermore, the Web Audio API provides highlevel nodes (such as the WaveShaper node and the biquad filter node) that can be used for an easy, quite accurate modelisation of tubes and filters. Namely, when properly used, waveshaping techniques associated with oversampling and appropriate filtering give quite good results [START_REF]G2 Workshops and tutorials: Waveshaping and distortion[END_REF]. The famous pod XT effect processor by Line 6 relies on such techniques [START_REF] Yeh | Numerical methods for simulation of guitar distortion circuits[END_REF].

Anyhow, we followed this "perceptual" approach consisting in emulating the different parts of the electronic circuit of this amplifier using Web Audio, implementing the necessary signal processing algorithms using the available API, and finding adequate solutions to circumvent some limitations specific to the Web browser environment (thread priority, latency, JavaScript API limitations). Finally, we extensively compared (quantitatively and qualitatively) our realization with the state of the art, i.e. native simulations, mostly commercial, written in C++, and not having the constraints of webapps. These results exceeded our expectations. Meanwhile, we went on refining the models used in the simulation, and designed a new framework to reproduce different electronic architectures present in various tube amplifiers found in many musicians' equipment [START_REF] Buffa | WebAudio virtual tube guitar amps and pedal board design[END_REF]. We can now simulate for example a Fender, a Vox or a Mesa Boogie amplifier, etc. or even create new original designs. These customizable simulations have been tested by professional guitarists, are being used by music schools on an experimental basis and are the subject of a marketing contract by the CNRS in order to be included as plugins [START_REF] Buffa | WAP: Ideas for a Web Audio plug-in standard[END_REF][START_REF] Buffa | Guitarists will be happy: guitar tube amp simulators and FX pedals in a virtual pedal board, and more![END_REF] in an online commercial DAW (AmpedStudio.com, see Fig. 2).

Since 2017, we have been developing Web Audio tube guitar amplifier simulations and tools, including an "amp sim designer" that can generate configurations used by an amp sim plugin engine that facilitates the process of creating end user plugins for musicians. To create each amp sim plugins presented in this demo, we proceeded as followed: we experimented with all the internals of our simulation : preamp, tonestack, power amp, reverb, speaker simulation stages, by adjusting gains, filters, tube types, number of tubes, internal topography of the audio graph, speaker impulse types, etc. Some stages of these plugins might not be based on high level audio nodes, in particular when sample accuracy DSP processing is needed (like in the power amp stage, where a negative feedback loop is present). In that case we used the FAUST DSL to generate WebAssembly code [START_REF] Ren | Using Faust DSL to develop custom, sample accurate DSP code and audio plugins for the Web browser[END_REF]. In a second step we created the GUI of the plugin, and in a third step we adjusted manually the ranges of the different parameters/knobs, by testing and fine tuning the plugin behavior. The plugins have been developed following the Web Audio Modules 2.0 plugin standard [START_REF] Buffa | Web Audio Modules 2.0, an open Web Audio plugin standard[END_REF].

Sound quality of our simulations

The plugins we developed can be tried with the AmpedStudio.com DAW (Fig 3) by creating a track and by adding in the plugin chain the AmpSim Utility plugin (Fig. 1) that is useful for adjusting gains, selecting the left/right channel (as the guitar signal is generally mono), and for activating a WebAssembly multi-channel noise gate., then one of the amplifier simulators, eventually with other audio effects for guitarists.

It is possible to get a taste of the sound quality provided by these plugins by visiting a web page we prepared with dry guitar sounds and the same sounds recorded with our plugins 1 . Only the plugins from Fig. 2 and Fig. 3 have been used. In addition, several videos are available online, showing these plugins in action :

• The Blues Machine : https://youtu.be/iZLTLNierAY

Settings for the demo

Figure 1 :

 1 Figure 1 : The AmpSim Utility plugin is useful for adjusting input gain and merging/muting left and right channels. It also includes a multi-channel noise gate.

Figure 2 :

 2 Figure 2 : guitar amp sim plugins in AmpedStudio DAW

Figure 3 :

 3 Figure 3 : the three guitar amplifier simulators WAM plugins

plugins in the Wasabi Pedalboard host :

			https://www.youtube.com/watch?v=qYzd5WGEbrM
		•	The Metal Machine: https://youtu.be/4epxLuaVuMQ and
			https://youtu.be/dLDoNquJYbc
		•	These plugins in the AmpedStudio DAW:
			https://www.youtube.com/watch?v=js_YOthpyuo
		•	These
	•	The Clean Machine (acoustic guitar simulator, in the video
		the guitar has regular non-piezo pickups):
		https://youtube.com/shorts/VM_mrTegeVA and

https://www.youtube.com/watch?v=rViUD9VWFFM

These plugins are now commercialized by our laboratory. They can be seen as "premium versions with extra features" of other open source projects we already published

[START_REF] Buffa | Real time tube guitar amplifier simulation using WebAudio[END_REF][START_REF] Buffa | WebAudio virtual tube guitar amps and pedal board design[END_REF][START_REF] Buffa | WAP: Ideas for a Web Audio plug-in standard[END_REF][START_REF] Buffa | Guitarists will be happy: guitar tube amp simulators and FX pedals in a virtual pedal board, and more![END_REF]

. For example, the Amp Designer that has been used for designing these plugins, as well as a previous version of the Blues Machine amp simulator (named Distortion Machine) plugin are available as open source projects

2

and you can see other videos of these versions 3 .

  GarageBand amp simulations and withGuitarix, an open source native amp simulator. The referenced papers contain user evaluations showing that the sound quality, latency and feeling guitar in hands of these simulations are comparable to the state of the art from the native world. https://www.youtube.com/watch?v=-NdMdJQx2Bw (amp designer, useful to create new amp sim plugins, https://www.youtube.com/watch?v=zBhn7odezUQ (dynamic transfer curves adjustment for tubes, for simulating tube nonlinear temporal behavior), https://www.youtube.com/watch?v=CPDgbRpLcBM (lowlatency + very fast hi-gain demo with live guitar playing)

Our simulation can be played real-time with a real guitar. As of today, we recommend for the best experience to use MacOS and a low latency sound card. By using a real guitar, we propose to compare our Web Audio based tube amp simulation with native simulations such as Guitar Rig by Native Instruments (used by many musicians and guitarists), with

http://mainline.i3s.unice.fr/distortionBook/sounds/

https://github.com/webaudiomodules/wam-examples, and https://mainline.i3s.unice.fr/AmpSim5/

https://www.youtube.com/watch?v=PiOD7n3g-Qs (demo of higains distortion in our amp simulations), https://www.youtube.com/watch?v=DUM99xQt5fg and https://www.youtube.com/watch?v=lIfm9ZMtG-I (professional guitar players using the amp sim),

4.