In many bioinformatics applications the task is to identify biologically significant locations in an individual genome. In our work, we are interested in finding high-density clusters of such biologically meaningful locations in a graph representation of a pangenome, which is a collection of related genomes. Diferent formulations of finding such clusters were previously studied for sequences. In this work, we study an extension of this problem for graphs, which we formalize as finding a set of vertex-disjoint paths with a maximum score in a weighted directed graph. We provide a linear-time algorithm for a special class of graphs corresponding to elastic-degenerate strings, one of pangenome representations. We also provide a ifxed-parameter tractable algorithm for directed acyclic graphs with a special path decomposition of a limited width.
in a single DNA sequence is to assign a score to each
The rapid decreases in the cost of genome sequencing base which is positive for bases with the property of
led to a shift in genomics and bioinformatics from an- interest and negative for other bases, and then look of
alyzing a single representative genome per species to high-scoring intervals in the resulting sequence of scores.
analyzing genomes of many individuals. A collection of Miklós Csűrös [
Introduction of pangenome graphs gave rise to a need the basis of the approach outlined in this article.
to extend many bioinformatics algorithms from working Namely, we generalize the maximum-scoring
segwith single sequences (strings) to graphs representing a ment set problem [
maximum density segment problem [17].
bubble graphs In this work, we will consider a weighted directed graph with vertex set , edge set ⊆ 2 and weight function : → R. We will first introduce graph terminology and notation used in this work. For each edge In this section, we present a linear-time algorithm based (, ) ∈ we call a predecessor of and a suc- on dynamic programming for a special class of directed cessor of . The set of all predecessors of is denoted acyclic graphs, which we call -layered bubble graphs. − (). The subgraph of induced by set ⊆ is the Definition 3.1 (-layered bubble). A -layered bubble is graph ′ = (, ∩ 2). A path is a sequence of dis- a directed acyclic graph with a start vertex , an end vertex tinct vertices (1, 2, . . . , ) such that (, +1) ∈ and non-empty vertex-disjoint directed paths, referred for = 1, 2, . . . , − 1. A cycle is a path such that to as layers, connecting and . (, 1) ∈ . If does not contain a cycle, we call it a directed acyclic graph (DAG). Vertices of each DAG can Definition 3.2 (-layered bubble graph). An -layered be ordered topologically as 1, . . . , so that for each bubble graph is a graph that can be constructed by taking edge (, ) ∈ we have < . a sequence of vertices 1, . . . , and connecting each pair
We are now ready to state our problem. The goal of of and +1 by an edge or by a -layered bubble with the maximum-score disjoint paths problem is for a given the start vertex and the end vertex +1 and with 2 ≤ graph and penalty ∈ R+ to find a set of vertex- ≤ . disjoint paths with the maximum sum of scores. The score of a single path = (1, 2, . . . , ) is defined An example of a 3-layered bubble graph can be seen as ∑︀=1 () − . Figure 1 shows an example of the in the bottom part of Figure 2. input and output for this problem.
Note that the maximum-score disjoint paths problem Connection to elastic degenerate strings.
Alis NP-hard for arbitrary weighted directed graphs. The though the structure of the -layered bubble graphs is
NP-hardness can be easily proved by a reduction from very simple, they correspond to a well-studied
representhe Hamiltonian path problem. If we set the weight of tation of pangenomes called elastic-degenerate strings
each vertex to 1 and penalty also to 1, the graph has (EDSs) [12]. An EDS is a string containing
elastica Hamiltonian path if and only if the maximum-score degenerate symbols. An elastic degenerate symbol is
dedisjoint paths problem has a solution with score | | − 1. fined as a set of strings, potentially of diferent lengths.
We will concentrate on DAGs. Our algorithms are an Thus the EDS represents a set of strings, each obtained by
extension of the dynamic programming algorithm by choosing one of the strings from each elastic degenerate
Csűrös [
An algorithm for a simple path. Before giving the
full algorithm for -layered bubble graphs, we will
consider the algorithm for a simple path (1, . . . , ). This
algorithm is very similar to the dynamic programming
algorithm given by Csűrös [
The algorithm fills a two-dimensional matrix . For sets , and ,, where , contains ver1 ≤ ≤ and ∈ {0, 1}, value (, ) is the score tices from that do not have a predecessor in , and of the optimal solution using only vertices 1, . . . , . , = ∖ ,.
If = 1, we further constrain the solution to include In our algorithm we will process the vertices in orthe last vertex in one of the selected paths. If = 0, der = 1, . . . , | |, which is a topological order of we place no further constraints on the solution. Values the graph, and in which for each bubble we first list its (, ) are computed for increasing values of using vertices from 1, then from 2 and so on. the following equations: Our dynamic programming algorithm fills a threedimensional matrix of scores (, , ℓ), where ∈ , (1, 1) = (1) − ∈ {0, 1} is a selection value, and ℓ ∈ {, } is a path (1, 0) = max{0, (1, 1)} continuation value. Value (, , ℓ) is the best score among all sets of disjoint paths within some induced sub (, 1) = () + max{ ( − 1, 0) − , ( − 1, 1)} graph of satisfying some additional properties speci (, 0) = max{ ( − 1, 0), (, 1)} ifed below.
The induced subgraph considered in (, , ℓ) is deifned as follows:
For = 1, we always use vertex with score (). One option is that it starts a new path, incurring penalty of . The rest of the solution will use only • for ∈ ∪ ∪ 1: nodes 1, . . . , − 1, thus having score ( − 1, 0). If the subgraph induced by {1, . . . , }, vertex continues an existing path, we instead use sub- • for ∈ , 2 ≤ ≤ in a bubble : problem ( − 1, 1) ensuring that such a path exists. the subgraph induced by {1, . . . , } ∩ ∩ . For = 0, we consider the case when was used in the Thus the score in the first layer of the bubble contains path, which has score (, 1) and the case when it was information about all previous vertices of the graph, not used, which has score ( − 1, 0). whereas in the remaining layers, we compute only local scores along one path of the bubble.
(1, 0, ) = max{0, (1, 1, )} Since 1 ∈ , we have (1, 0, ) = (1, 1, ) = −∞ .
Let us now consider some vertex for ≥ 2. We will distinguish several cases. If ∈/ , it has a single predecessor, which we denote . The simplest case is analogous to the algorithm operating on a single path, and applies to three cases: (1) ∈ and ℓ = , (2) ∈ , for any and any ℓ ∈ {, }, and (3) ∈ 1,, ℓ = . (, 1, ℓ) = () + max{ (, 0, ℓ) − , (, 1, ℓ)} (, 0, ℓ) = max{ (, 0, ℓ), (, 1, ℓ)}
the bubble.
The next case is ∈ 1, and ℓ = . Value ℓ = means that the path from the predecessor (start of the bubble) continues to some other layer of the bubble, and thus we always apply the penalty if is included in a path. Also, the predecessor is constrained to be on a path, and thus we use (, 1, ) instead of (, 0, ). (, 1, ) = () + (, 1, ) − (, 0, ) = max{ (, 1, ), (, 1, )}
same way as in the simpler algorithm for a single path: • = 1 means is selected in a path, • = 0 means may or may not be selected in a
path (no constraint),
The constraint imposed by the path continuation value ℓ depends on the type of the vertex and allows us to ensure that a path entering a bubble from its start vertex will continue in at most one layer of the bubble. For ∈ 1: • ℓ = : there is no selected path which contains both the bubble’s start vertex and the subsequent vertex from , where > 1 (no constraint on 1,). • ℓ = : the bubble’s start vertex is selected on a path which continues with a vertex from , where > 1.
For ∈ , > 1: • ℓ = : the path from the bubble’s start vertex continues on layer , i.e. both the bubble’s start vertex and the , vertex of the current bubble are selected; • ℓ = : there is no path containing both the current bubble’s start vertex and the , vertex of the current bubble.
(1, 1, ) = (1) −
In both cases, value ℓ = means that the path from the start of the bubble continues along the path to which In case of ∈ , for > 1, we will not use the the current vertex belongs. The possibility that the scores computed for the predecessor, because those are path does not continue to any of the paths of the bubble propagated along the first layer. For ℓ = we use similar is included in case ℓ = for the first layer 1. Value formulas as for 1. For ℓ = the path has to continue ℓ = always includes all cases not considered for ℓ = . from to , leading to more constrained formulas.
For ∈ ∪ , we will use only ℓ = , and we will not impose any additional constraint. Value (, , ) is not defined and can be considered as being −∞ . (, 1, ) = ()
To initialize the algorithm for the first node 1 in or- (, 0, ) = (, 1, ) dering , we use similar formulas, as for the simpler case of a single path: (, 1, ) = () − (, 0, ) = max{0, (, 1, )} ,, 1 ≤
≤
Finally, we will consider the most complex case ∈ , that is, the end vertex of a processed bubble with layers.
Vertex has in this case predecessors denoted here as 1 , . . . , , where is in layer . The values stored in score matrix for 1, . . . , were calculated for disjoint subgraphs, and thus to get the score for , the algorithm has to sum up the scores for 1, . . . , , while ensuring that both at the start and end of the bubble the penalties for new paths are applied properly.
To ensure that the selected path from the bubble’s start vertex continues with at most one vertex ∈
, we have to use ℓ = for exactly one predecessor and ℓ = for all the others. Recall that the score for 1 when ℓ = also includes the possibility that the selected path does not continue to any of the layers from the bubble’s start vertex.
groups of sums are created and their maximum is used as (, 1, ).
The first group corresponds to the situation where starts a new path and incurs a penalty. Therefore it is not important which of the predecessors, if any, were included in some paths. ̸=
̸=
⎛
⎛ 1 = max ⎝ (, 0, ) + ∑︁ (, 0, )⎠−
The maximum in 1 goes over sums, each having path continuation value for a diferent predecessor . The value 1 can be calculated in () time. First, the sum (1, 0, ) + (2, 0, ) + · · ·
+ (, 0, ) − is calculated. Then the algorithm changes exactly one addend at a time from (, 0, ) to (, 0, ) and chooses the maximum sum.
the path containing continues from some predecessor without incurring a penalty, and ℓ = for the same predecessor :
2 = max ⎝ (, 1, ) + ∑︁ (, 0, )⎠ Similarly as for 1, the value 2 can be calculated in () time by first calculating the sum (1, 0, ) + (2, 0, ) + · · · then always changing exactly one addend at a time from (, 0, ) to (, 1, ) and choosing the maximum + (, 0, ), and sum at the end.
The third group corresponds to the situation when the path through continues from some predecessor without incurring a penalty, and ℓ = for another predecessor where ̸= . This means that the path from the start of the bubble continues through a diferent path than the path leading to the end of the bubble. ⎞ ⎞ ̸=
︃( 3 = max (, 1, ) + ( , 0, ) +
∑︁ ̸=,̸=
⎞ (, 0, )⎠
In this case, Θ(2) sums of length need to be calculated and compared. This could be done in (2) time similarly as above, only considering all pairs of predecessors and . However, with some care, the maximum sum can be calculated in () time as follows. The algorithm first calculates the sum (1, 0, ) + (2, 0, ) + · · · it finds addends
+ (, 0, ) as in group 2. Then (, 0, ) and (, 0, ) which when replaced with (, 0, ) and (, 1, ) maximize the sum.
To do this, the algorithm first finds ) for which the diference
(, 0, ) − is the largest and second largest, respectively. Next, it finds (, 1, ) − and ( ̸= ) for which the diference (, 0, ) is the largest and second largest, respectively. Both these computations can be done in () time. Finally we use these values to assemble the final value for 3. If ̸= , then the addend (, 0, ) is replaced with (, 0, ), and (, 0, ) with (, 1, ). If = , then one of the addends is replaced by (, 0, ) or ( , 1, ) instead, whichever results in a larger sum.
Finally, the value of (, 1, ) is derived in the fol and ( ̸= (, 0, ) lowing way: ⎪ ⎨ ⎧1
2 ⎪⎩3 (, 1, ) = () + max
(, 1, ) representing the case that is selected and the value 4 representing the case that is not selected. The value of 4 is computed similarly as 1, except that the penalty term − is not applied. For ∈ , value (, 0, ) and (, 1, ) are not defined and can be considered as being −∞
.
, the overall score can be found in (| |, 0, ). Note the the last vertex | | belongs to ∪ , and thus the value for ℓ = does not pose any constraint on the selected paths.
score, we can store for each value of matrix which case was used to obtain it and then follow these values from (| |, 0, ) all the way to (1, ?, ).
Regarding the time complexity of the algorithm, calculating the scores for each vertex outside of is done in (1) time. Calculating the scores for a vertex ∈ with indegree takes () time, but this can be amor- definition does not seem to lead to an eficient algorithm tized among the predecessors of , each of which has for our problem. indegree 1. Therefore both the time and space complexity The following lemma shows a useful property of a of the algorithm is (| |). directed path decomposition.
In the previous section, we described an algorithm for the maximum-score disjoint paths problem on -layered bubble graphs. Although such graphs can provide a representation of a pangenome, their power is limited. In this section, we provide a fixed-parameter tractable algorithm for a general DAG, which can solve the problem in time (2 · · | |) if it is provided with a special directed path decomposition with the width bounded by parameter . In the rest of the section, we first define this decomposition and then describe the algorithm.
Definition 4.1 (Directed path decomposition). Let = (, ) be a directed graph. A directed path decomposition of is a sequence of subsets (1, . . . , ) of (we refer to them as bags of vertices), with three properties: (i) For each edge (, ) ∈ , there exists an ∈ {1, . . . , } such that both and belong to bag . (ii) For every three bags , and such that 1 ≤ ≤ ≤ ≤ we have ∩ ⊆ . (iii) For each edge (, ) ∈ if ∈ then there exists a bag containing where ≤ .
Lemma 4.1. Let = (, ) be a directed graph and = (1, . . . , ) its directed path decomposition. Assume is the bag where vertex appears for the first time in , i.e. ∈ and ∈/ where < . Then bag contains all predecessors of .
predecessor of has to be in some bag ℎ for ℎ ≤ . Based on () in Definition 4.1, there exists a bag containing vertices and . Since is the bag where appears for the first time in , ≤ . Based on () in Definition 4.1, contains ∈ ℎ ∩ .
at least the maximum indegree of , where the indegree of vertex is the number of ’s predecessors | − ()|.
rected path decomposition, in which a single new node is added in each bag. Below we define it formally and show that any directed path decomposition can be eficiently converted into this form without increasing the width.
= (, ) be a DAG and = (1, . . . , ) its directed path decomposition. We consider 0 = ∅. We call an incremental path decomposition if | ∖ − 1| = 1 for 1 ≤ ≤ . The vertex in ∖ − 1 is called the incremental vertex.
=
max∈{1,...,} || − 1. = (, ) consists of exactly | | bags, as exactly one
One can also define the directed pathwidth of graph vertex is added in each bag and each vertex needs to be as the minimum value such that has a path de- added exactly once. composition with width .
Our definitions of a directed path decomposition and Lemma 4.2. Let = (, ) be a DAG and = a directed pathwidth are extensions of the well-studied (1, . . . , ) its directed path decomposition of width . path decomposition for undirected graphs [18]. The path It can be converted to an incremental path decomposition decomposition of graph can be interpreted as a thick- for with a width at most in ( · | |) time. ened path graph. The path width is a value describing how much this path is thickened to get . To adapt the undirected path decomposition for our purposes, we added the third condition. It allows the algorithm to process bags in order and ensure that predecessors of each node are already processed when we process the first bag with this node.
A diferent path decomposition for directed graphs was previously studied [19, 20], which omits the first condition and uses a less strict version of the third condition as follows: “For each edge (, ) ∈ there exists ≤ such ∈ and ∈ ”. However, such a relaxed Proof. Let us assume that | ∖ − 1| = . If = 0 then ⊆ − 1, and therefore, can be left out of the path decomposition without breaking properties (), () and () from Definition 4.1. If > 1, we create a path decomposition ′ = 1, . . . − 1, , , . . . where | ∖ − 1| = 1 and | ∖ | = − 1. By repeating these steps, we get an incremental path decomposition.
To construct , we consider a topological order of vertices in and select the vertex which is the first in this topological order among vertices in ∖ − 1.
This means that has no predecessor in ∖ − 1. Bag is constructed as = (− 1 ∩ ) ∪ {}. Clearly, decomposition ′ satisfies all properties from Definition First, if ∈/ , then the incremental vertex is not 4.1. Also notice that | | ≤ | |, i.e. the width of the path used in any path because it is not the last vertex of any decomposition was not increased. path, and it cannot be in the middle of a path, as it does
Finally, set can be constructed in () time, and not have any successors in . Therefore we copy some as we repeat this process at most | | times, the total score computed for − 1 to (, ). However, we need running time is ( · | |). The topological order can be to consider multiple configurations for − 1 as there computed in (| | + ||) time. Note that || ≤ · | | can be multiple vertices in − 1 which are not part of as each vertex has at most incoming edges. . These vertices can be part of a configuration for − 1 but are no longer relevant for . To this end, for An algorithm that uses an incremental decomposi- each configuration of we will define set (, ) of tion. We now describe an algorithm for solving the configurations of − 1 that agree with on the vertices maximum-score disjoint paths problem for a DAG = shared between − 1 and . Formally, (, ) and penalty . The input to the algorithm is an incremental path decomposition = (1, . . . , ) of . The algorithm runs in (2 · · | |) time where Score (, ) can then computed as follows: is the width of . Let be the subgraph of induced by vertices in 1 ∪ · · · ∪ . (, ) = max ( − 1, )
The algorithm processes individual bags in the decom- ∈(,) position one at a time. When processing bag the algorithm computes maximum scores of solutions in the In the second case, ∈ . The path containing can subgraph . In the first algorithm, we have considered be either a single vertex, in which case we apply penalty for each ending vertex solutions for diferent settings , or can follow some vertex ∈ − 1. In that case of binary variables and ℓ. Here we will consider 2|| must be in the configuration for − 1, because it was diferent solutions, each corresponding to a diferent sub- the last vertex before addition of . But it is not in set ⊆ . We will call these subsets configurations . the configuration for , because it is now followed by Configuration determines which vertices from are . We consider all possibilities for predecessor of the last vertices in individual paths contained in a solu- which is not in and for configuration for − 1 which tion of the problem. The algorithm thus computes a score contains , but otherwise agrees with on the vertices matrix (, ) which contains the score of the best set shared between − 1 and . Note that all predecessors of paths within such that if is the set of last vertices of are in both (according to Lemma 4.1) and − 1 of these paths, then = ∩ . (because only a single vertex is added to ).
Let us assume that the scores for − 1 are already (, ) = ()+ known, and we want to calculate scores for . Let be the incremental vertex of . Consider a configuration {︃max∈(,) ( − 1, ) − max ⊆ . We will consider two cases. max∈− ()∖ max∈(,∪{}) ( − 1, ) (, ) = { ⊆ − 1 | − 1∩∩ = − 1∩∩}.
To initialize the algorithm, we set (0, ∅) = 0. The final (). To fulfill property () in Definition 4.1, we find the score is the maximum of (| |, ) among all configu- ifrst and last occurrence of each vertex in the bags, rations of | |. The paths can be again reconstructed and add vertex into the bags in between. This does not by keeping track of which configuration was used to break property () and () from Definition 4.1 and it compute each score in matrix . fulfills property (). The complexity of this algorithm is
The above formulas are not convenient for implemen- ( · | |). tation because we need to iterate over multiple config- The resulting path decomposition is incremental. urations ⊆ − 1 for each configuration ⊆ . It Namely, bag is the first bag where vertex appears, is easier to organize computation in a forward fashion, and therefore, | ∖− 1| ≥ 1. The diference of the sets where we first initialize (, ) to −∞ for all and cannot be 2 or more, as then the other additional vertex then iterate over all configurations of − 1 and use has to be where < which means it appeared already ( − 1, ) to update up to + 2 relevant values of in bag , and due to condition () from Definition 4.1 (, ), as shown in Algorithm 1. The algorithm clearly it means ∈ − 1. works in (2 · · | |) time, provided that sets and can be manipulated in (1) time, which is a reasonable assumption since they are used to address the matrix and 5. Experiments thus presumably fit into a single computer word.
for -layered bubble graphs from Section 3; this
imAlgorithm 1 Computation of matrix given an incre- plementation can be found at https://github.com/evicy/
mental path decomposition 1, . . . , | | and incremen- thesis. We tested our implementation on the task of
idental vertices 1, . . . , . tifying GC-rich regions in a pangenome of Escherichia
(0, ∅) = 0 coli bacterium. The GC content of DNA sequences, i.e.
for all ∈ {1, . . . , | |} do the percentage of guanine (G) and cytosine (C) bases, is
for all ⊆ do a frequently used statistic when analyzing genomes. It
(, ) ← −∞ has been well studied across organisms, revealing
conend for nections between the GC content and various genomic
for all ⊆ − 1 do characteristics [21]. GC-rich regions were also used in the
← ∩ study of the maximum segment sum problem by Csűrös
(, ) = max{ (, ), ( − 1, )} [
Used genomes only the reference [22] ID 0 and SRR10058833 ID 1 and SRR10058834 ID 2 and SRR10058835 ID 3 and SRR10058836 ID 4 and SRR10058837 ID 5 and SRR10058838 ID 6 and SRR10058839 ID 7 and SRR10058840
| | ent biological questions stemming from comparative or functional genomics.
Note that our algorithms are purely combinatorial,
while many existing approaches for single genomes use
statistical methods [29, 10, 30, 31, 32, 33], Csűrös [
From a more theoretical point of view, it would be interesting to characterize the complexity of our problem on diferent classes of directed graphs besides the two studied in this work.
tive score, while the GC content of the E. coli genome is 50.8% on average. The penalty ensures that the length of each selected path is at least .
In Figure 5, we can see the coverage, i.e. the percentage of the graph that is covered by the selected paths. As expected, the coverage decreases with increasing penalty. By adding genomic sequences to the pangenome, the coverage is increasing, because some of the new variants will introduce ’s and ’s that can be used by the selected paths.
In this work, we have defined the maximum-score disjoint paths problem and provided two algorithms for solving it. The first algorithm runs in linear time on layered bubble graphs, which can represent pangenomes expressed as elastic-degenerate strings. The second algorithm runs on general DAGs in time (2 · · | |) where is the width of a special directed path decomposition defined in this work. We also show the results of a prototype implementation of our first algorithm. In future work, we plan to apply our algorithms to diferysis of DNA sequences, Computers & Chemistry [22] Bethesda (MD): National Library of Medicine (US), 26 (2002) 491–510. National Center for Biotechnology Information, As[8] X. Wu, S. Liu, G. Liang, Detecting clusters of tran- sembly ASM584v2, Escherichia coli str. K-12 substr. scription factors based on a nonhomogeneous pois- MG1655 (E. coli), https://www.ncbi.nlm.nih.gov/ son process model, BMC Bioinformatics 23 (2022) assembly/GCF_000005845.2/, 2013. Accessed: 2023535. 04-10. [9] N. Stojanovic, L. Florea, C. Riemer, D. Gumucio, [23] C. J. Reid, K. Blau, S. Jechalke, K. Smalla, S. P. DjordJ. Slightom, M. Goodman, W. Miller, R. Hardison, jevic, Whole genome sequencing of Escherichia Comparison of five methods for finding conserved coli from store-bought produce, Frontiers in Microsequences in multiple alignments of gene regula- biology 10 (2020) 3050. tory regions, Nucleic Acids Research 27 (1999) 3899– [24] ENA, Project: PRJNA563564, https://www.ebi.ac. 3910. uk/ena/browser/view/PRJNA563564?show=reads, [10] N. J. Croucher, A. J. Page, T. R. Connor, A. J. Delaney, 2019. Accessed: 2023-04-10.
J. A. Keane, S. D. Bentley, J. Parkhill, S. R. Harris, [25] H. Li, Aligning sequence reads, clone sequences and Rapid phylogenetic analysis of large samples of re- assembly contigs with BWA-MEM, arXiv preprint combinant bacterial whole genome sequences using arXiv:1303.3997 (2013).
Gubbins, Nucleic Acids Research 43 (2015) e15–e15. [26] H. Li, B. Handsaker, A. Wysoker, T. Fennell, J. Ruan, [11] L. Brankovic, C. S. Iliopoulos, R. Kundu, M. Mo- N. Homer, G. Marth, G. Abecasis, R. Durbin, The sehamed, S. P. Pissis, F. Vayani, Linear-time superbub- quence alignment/map format and SAMtools, Bioinble identification algorithm for genome assembly, formatics 25 (2009) 2078–2079.
Theoretical Computer Science 609 (2016) 374–383. [27] E. Garrison, G. Marth, Haplotype-based variant de[12] C. S. Iliopoulos, R. Kundu, S. P. Pissis, Eficient tection from short-read sequencing, arXiv preprint pattern matching in elastic-degenerate strings, In- arXiv:1207.3907 (2012).
formation and Computation 279 (2021) 104616. [28] S. P. Pissis, A. Retha, Dictionary matching in [13] F. Bengtsson, J. Chen, Computing maximum- elastic-degenerate texts with applications in searchscoring segments optimally, Luleå tekniska univer- ing VCF files on-line, in: 17th International Symsitet, 2007. posium on Experimental Algorithms (SEA 2018), [14] P. Gawrychowski, P. K. Nicholson, Encodings of volume 103 of Leibniz International Proceedings in range maximum-sum segment queries and appli- Informatics (LIPIcs), Dagstuhl, Germany, 2018, pp. cations, in: Combinatorial Pattern Matching: 26th 16:1–16:14. Source code is available at https://github. Annual Symposium (CPM 2015), Springer, 2015, pp. com/webmasterar/edso.
196–206. [29] M. Kulldorf, Spatial scan statistics: models, cal[15] H.-F. Liu, K.-M. Chao, Algorithms for finding the culations, and applications, in: Scan statistics and weight-constrained k longest paths in a tree and applications, Springer, 1999, pp. 303–322. the length-constrained k maximum-sum segments [30] Z. He, B. Xu, J. Buxbaum, I. Ionita-Laza, A genomeof a sequence, Theoretical Computer Science 407 wide scan statistic framework for whole-genome (2008) 349–358. sequence data analysis, Nature Communications [16] S. K. Kim, J.-S. Cho, S.-C. Kim, Path Maximum 10 (2019) 3018.
Query and Path Maximum Sum Query in a Tree, [31] F. Ferrari, A. Solari, C. Battaglia, S. Bicciato, Preda: IEICE TRANSACTIONS on Information and Sys- an R-package to identify regional variations in getems 92 (2009) 166–171. nomic data, Bioinformatics 27 (2011) 2446–2447. [17] K.-M. Chung, H.-I. Lu, An optimal algorithm for the [32] A. Coppe, G. A. Danieli, S. Bortoluzzi, REEF: searchmaximum-density segment problem, SIAM Journal ing REgionally Enriched Features in genomes, BMC on Computing 34 (2005) 373–387. Bioinformatics 7 (2006) 1–7. [18] N. Robertson, P. D. Seymour, Graph minors. i. ex- [33] E. D. Stavrovskaya, T. Niranjan, E. J. Fertig, S. J. cluding a forest, Journal of Combinatorial Theory, Wheelan, A. V. Favorov, A. A. Mironov, StereoSeries B 35 (1983) 39–61. Gene: rapid estimation of genome-wide correlation [19] J. Barát, Directed path-width and monotonicity in of continuous or interval feature data, Bioinformatdigraph searching, Graphs and Combinatorics 22 ics 33 (2017) 3158–3165.
(2006) 161–172. [20] J. Erde, Directed path-decompositions, SIAM Jour
nal on Discrete Mathematics 34 (2020) 415–430. [21] S. Gelfman, G. Ast, When epigenetics meets alternative splicing: the roles of DNA methylation and GC architecture, Epigenomics 5 (2013) 351–353.