BACKGROUND
next-generation sequencing  technologies have drastically reduced the cost of genome sequencing  <cit> .
as more genomic sequences have become available, it has become clear that genomes contain many structural variations , which include large insertions, deletions, tandem duplications, and translocations.
svs have already been associated with diverse diseases  <cit> .
for example, the fusion genes bcrabl and eml4-alk play key roles in the development of cancer, and it is believed that other recurrent rearrangements remain to be discovered  <cit> .
in cancer genomes, many svs are occasionally concentrated in a small region of the genome  <cit> .
it has been suggested that a single catastrophic mutational event, known as chromothripsis  <cit> , causes these concentrations.
a study of prostate cancer also uncovered a distinct type of complex rearrangement termed chromoplexy  <cit> , wherein rearrangements are unclustered but involve multiple chromosomes.
complex genomic rearrangements have even been observed in germline mutations, resulting in serious congenital diseases  <cit> .
because of their importance in functions of the genome, various methods have been developed for finding svs  <cit> .
when genomic rearrangements are complex, enumerating only individual svs is insufficient for elucidating the global structure of chromosomes, i.e., how the segments in a reference genome are extracted and ordered in an unknown target genome.
here, the reference genome is known and is a pre-existing sequenced genome of the same organism, such as the grch <dig> build of the human genome  <cit> .
in this study, we address the problem of inferring the global structure of chromosomes based on sv data, which refer to aberrant adjacencies of genomic regions and copy number variations  in this study.
by solving this problem, we can determine the order of the genomic regions in the target genome.
this order affects the structure of proteins if the genomic regions contain coding regions, and regulation of genes if the genomic regions include promoters or enhancers.
in addition, raw sv data could be corrected by inferring the global structure of chromosomes because an optimal global structure would ignore false positive detection of aberrant adjacencies or correct wrongly estimated copy numbers.
the task of inferring chromosomes is formulated as an optimization problem on a graph, which we term as a chromosome graph.
our contributions are summarized as follows:
• to infer the global structure of chromosomes, we formulate a computational problem that takes into account the number and length of chromosomes, as well as aberrant adjacencies and cnvs caused by genomic rearrangements.
by taking sv data as the input, relatively low-depth ngs sequencing can be used.
• we prove that the problem is np-complete.
• we propose a biologically meaningful restriction that makes the problem solvable in polynomial time.
we also show an algorithm that solves the restricted problem.
oesper et al.
<cit>  presented a pioneering work that aimed to infer the global structure of chromosomes from sv data.
they formulated the copy number and adjacency genome reconstruction problem.
their formulation is based on graphs that they termed interval-adjacency graphs.
these graphs are essentially the same as our chromosome graphs, except that we used bidirected graphs  <cit>  while they used alternating paths to exclude paths on the graph that do not correspond to chromosomes.
they also implemented an efficient algorithm called paired-end reconstruction of genome organization  that solved their problem and obtained promising results.
our work includes the following results that were not addressed by oesper et al.
first, we present a formulation that takes into account the number and length of chromosomes determined experimentally.
second, we prove that the problem is np-complete.
finally, we propose a variation of the problem that can be solved in polynomial time.
some methods can also be applied to analyze the global structure of genomes by using non-sv data.
first, de novo sequence assembly aims at reconstructing target genomes from raw ngs sequences  <cit> .
it includes a step to order fragments of genomes obtained by assembling ngs sequences.
the step is usually implemented as an optimization problem, involving searching for paths that cover all vertices or all edges corresponding to substrings of genome sequences  <cit> .
by contrast, we allow some vertices and edges to be ignored because some portions of the reference genome might not appear in the target genome.
second, reference-assisted assembly  <cit> , also known as comparative assembly  <cit> , aims at ordering segments of an unknown target genome by using known genomes of other organisms.
by contrast, we order segments so that the chromosomes in the solution are most consistent with the sv data and the experimentally determined number and length of chromosomes.
finally, methods based on permutations of integers  <cit>  compare two genomes represented by two sequences of integers corresponding to genes or markers in the genome.
instead of using such sequences, we exploit sv data.
the rest of this paper is organized as follows.
first, we present types of experimental data from which we infer the global structure of chromosomes.
next, we give our formulation of the problem of inferring the global structure of chromosomes, and show that the problem is np-complete.
then, we show a variation of the problem that is solvable in polynomial time.
finally, we discuss our results and state our conclusions.
RESULTS
experimental data
we assume the following experimental data as input.
aberrant adjacencies
in the target genome, distant segments in the reference genome may be adjacent because of rearrangements .
such aberrant adjacencies are detected by using ngs technologies as follows.
first, ngs technologies can generate read pairs that are a few hundred bases apart from each other in the target genome.
if two reads of a pair are not mapped to the reference genome with the expected orientations and mapped distance, the pair is called a discordant pair and is likely to be caused by svs  <cit> .
second, if the alignment of a read and reference genome is split into more than one portion, such a split read also indicates a rearrangement  <cit> .
a breakpoint is a position at a boundary of a rearrangement.
here, we ignore small differences between the real breakpoints and their estimations.
copy numbers
the number of occurrences of a subsequence in the reference genome may change because of rearrangements.
this phenomenon results in copy number variations .
traditionally, cnvs have been analyzed by using dna microarrays  <cit> .
several recent methods detect cnvs by finding changes in the depth of coverage of ngs sequences  <cit> .
although tumor samples are usually a mixture of normal cells and various tumor cells, the copy numbers of a cancer cell can still be estimated by single-cell analysis  <cit> .
in this paper, for the sake of conciseness, the boundaries of cnvs are also called breakpoints.
number of chromosomes and truncations
identifying chromosomes and finding aberrant chromosomes by microscopy is an important part of clinical diagnostics  <cit> .
the number of chromosomes, denoted by nn in this paper, is available after inspection.
throughout this paper, we assume that nn ≥  <dig>  in addition, we also take into account the number of chromosomal truncations, which we denote as nt.
chromosomal truncations are detected as a decrease in copy numbers without aberrant adjacencies.
we consider nn and nt to improve the inference of the global structure of chromosomes from sv data.
chromosome length
the length of chromosomes can be estimated experimentally from flow karyotyping, and, approximately, from microscopic images  <cit> .
here, the estimated length is denoted by λi for  <dig> ≤ i ≤ nl, where nl is the maximum possible number of chromosomes.
problem definition
any instance of our problem is modeled as a graph that we term a chromosome graph.
the graph contains elements derived from the reference genome and experimental data.
each vertex corresponds to a location in the reference genome.
in addition, each edge corresponds to either a segment in the reference genome, an adjacency of flanking segments in the reference genome, or an aberrant adjacency in the target genome caused by rearrangements.
we assume that the target genome is a set of chromosomes, each of which is a concatenation of segments in the reference genome.
each chromosome in the target genome is represented as a path on the graph, and these paths explain how segments in the reference genome are incorporated into the target genome.
the goodness of the estimated target genome is measured by a cost function, and we search for an optimal set of chromosomes that minimizes this cost function.
we first define a graph that contains some of elements described above.
then, we extend the graph to a chromosome graph.
finally, we present the formal definition of the problem.
prototype chromosome graph
we first construct an undirected graph called a prototype chromosome graph, g =  .
let nc be the number of chromosomes of the reference genome and ni be the number of breakpoints in the i-th chromosome of the reference genome.
then, v contains the following vertices.
• vertices corresponding to breakpoints:
vm={vi,j|1≤i≤nc,1≤j≤ni}.
• vertices corresponding to the beginning of chromosomes in the reference genome:
v5={vi,0|1≤i≤nc}.
• vertices corresponding to the end of chromosomes in the reference genome:
v3={vi,ni+1|1≤i≤nc}.
then, we define v = v <dig> ∪ v <dig> ∪ vm.
next, we define a set of edges, e. we make the following two types of edges.
• edges corresponding to segments between two breakpoints that are next to each other in the reference genome.
for each  <dig> ≤ i ≤ nc and  <dig> ≤ j ≤ ni, we make an edge ei,j = .
• edges corresponding to aberrant adjacency of two segments in the reference genome.
let na be the number of detected aberrant adjacencies.
for the k-th aberrant adjacency  that links positions corresponding to vi <dig> j <dig> and vi <dig> j <dig>  we make an edge elk=.
then, we define
es={ei, j|1≤i≤nc,0≤j≤ni},el={elk|1≤k≤na},   e=es∪el.
chromosome graph
in a prototype chromosome graph, a path might visit two edges in el contiguously.
such a path does not correspond to a real chromosome.
to exclude such a path we use a technique similar to that of oesper et al.
<cit> .
although oesper et al.
<cit>  used alternating paths, their formulation can be represented by using a bidirected graph whose edges have directions at both ends  <cit> .
we directly define our graph by using a bidirected graph .
let d ∈ {+,−} be the direction of an edge e at a vertex v, and −d be the opposite direction of d.
• each vertex vi,j ∈ vm is split into two vertices vi,j+ and vi,j-.
the set vm is redefined as
vm={vi,j-,vi,j+|1≤i≤nc,1≤j≤ni}.
vertices in v <dig> and v <dig> are renamed so that
v5={vi,0-|1≤i≤nc},v3={vi,ni+1+|1≤i≤nc}.
• an edge ei,j =  ∈ es is reconnected to vi,j- and vi,j+1+.
in addition, d=- and d=+.
• let e ∈ el be an edge connected to vi,j in the prototype chromosome graph.
if e corresponds to an aberrant adjacency involving the segment that stretches toward vi,j+ <dig>  e is reconnected to vi,j- and d is set to '+'.
otherwise, e is reconnected to vi,j+ and d is set to '−'.
• we add the following set of new edges:
er={e^i,j=|1≤i≤nc,1≤i≤ni}.
directions are set so that d=- and d=+.
the modified graph represents a chromosome graph.
paths and chromosomes
a path c = v1e1v2e2v <dig> ... elvl+ <dig> on a chromosome graph g is an alternating sequence of vertices and edges, which has the following properties:
• the first and the last of c are vertices.
• any subsequence of the form ekvkek+ <dig>  means that d = −d.
a path c is said to visit an edge e if c contains e. similarly, c is said to visit a vertex v if c contains v. when a path is written as a sequence of vertices and edges, for simplicity, we omit the notation of the vertices if they are clear.
let c = {c <dig>  c <dig> ..., c|c|} be a multiset of paths on g. we define c as a multi-set so that more than one identical path can exist.
in addition, let m be the number of times c visits an edge e, and m=∑ci∈cm.
a cycle is a path whose first and last vertices are identical and the directions of the first and the last edges at the vertex are opposite.
a chromosome on g is a path whose first and last edges are both in es.
copy numbers and lengths
two integers are assigned to each e ∈ e. first, n for e ∈ es represents an experimentally estimated copy number of the corresponding segment in the reference genome.
second, |e| for e ∈ es represents the length of the corresponding segment in the reference genome.
for e ∈ el ∪ er, we set n and |e| to  <dig>  the length of a path c is defined as |c|=∑e∈e|e|m.
to simply describe all properties of e together, we use the following notation:
e=⟨dv <dig> dv <dig> n,|e|⟩.
upper bound on parameters
campbell et al.
<cit>  presented examples of amplified regions in cancer cells.
the copy numbers were less than  <dig> in these regions.
therefore, we assume that the copy numbers are in at most hundreds.
we also assume that short repeat elements are masked in advance in order to exclude segments that appear spuriously.
based on the details given above, we assume that nn, nt, and n for e ∈ es are all less than a fixed constant u. the value of u does not have to be determined because u is only used in the analysis of computational complexity.
formulation of the problem
to find an optimal set of chromosomes, we define an optimization problem over a chromosome graph.
we define a cost function to be used as a target function of the optimization problem.
this function imposes costs on the number of chromosomes, the number of chromosomal truncations, and the number of visits to edges, penalizing for deviations from those that are experimentally expected.
let c = {c <dig>  c <dig> ..., c|c|} be a multi-set of chromosomes on g, and wn be the cost of the difference between nn and |c|.
also let tr be the number of ends of chromosomes in vm, and wt  be the cost of the difference between nt and tr.
in addition, w for e ∈ es is defined as the cost when e is visited x-times.
for e ∈ el ∪ er, w is set to  <dig>
we assume that wn, wt, and w for e ∈ es monotonically increase as ||c| − nn|, |tr − nn|, and |x − n| increase, respectively.
then, we define the cost function w as follows:
w=wn+wt+∑e∈ew).
we assume that each term is  <dig> if and only if
|c|=nn,tr=nt,m=n for e∈es.
with these notations, we formulate the problem of inferring the global structure of chromosomes as follows:
definition  <dig> ) suppose that we are given a chromosome graph g = , a cost function w, and parameters λi , where nl is the maximum possible number of chromosomes.
then, find a multi-set of chromosomes c on g that minimizes w under the constraint that |ci| ≤ λi for ci ∈ c.
although a similar problem was proposed previously  <cit> , its computational complexity was not analyzed.
theorem  <dig> chrp is np-complete.
in the methods section, we prove theorem  <dig>
polynomial-time solvable variation
we propose a variation of chrp that is solvable in polynomial time.
for e ∈ el ∪ er, it is highly likely that m ≥  <dig> if e is supported by a large number of paired-reads.
therefore, it is worth considering a variation in which some edges in el∪ er must appear in the target genome.
we refer to the edges as required edges.
in addition, because chromosomal truncations can be detected, it is also worth considering a variation in which we know where the ends of the chromosomes of the target genome exist in the reference genome.
because the definition of w is abstract, we focus on a cost function such that
wn=qn||c|-nn|,wt=qt|tr-nt|,w=|e||x-n|,
where qn and qt are constants given as parameters.
the values of qn and qt are tuned in advance so that known global structures of genomes are well reconstructed.
weakly connected constraint
let g =  be a general bidirected graph.
a subgraph g of g is a weakly connected component if g is a connected component when all directions are removed  <cit> .
in addition, g is maximal if g is not a subgraph of a larger weakly connected component.
for a subset e' of e, we define cc as a set of maximal weakly connected components of a graph induced from g by removing the edges not in e'.
definition  <dig> ) let g =  be a chromosome graph.
also let vw and ew be subsets of v and e, respectively.
each g ∈ cc is good if g contains at least one vertex in vw.
then, g satisfies the weakly connected constraint  if all g ∈ cc are good.
we use wcc by setting vw to a set of vertices that correspond to ends of chromosomes in the target genome, and ew = {e ∈ es|n ≥ 1} ∪ {e ∈ el ∪ er|e is required}.
see figure  <dig> for an example.
an instance that satisfies wcc can be obtained as follows.
first, vw is obtained by finding the positions of chromosomal truncations, as well as the ends of the chromosomes of the reference genome that remain in the target genome.
because a chromosome that does not include detected ends can be in a solution, vw does not need to contain all ends of chromosomes in the target genome.
we assume that nt ≥ |vw|.
next, if g ∈ cc is not good, edges e ∈ e on some path connecting g and good g' ∈ cc are added to ew.
to do this, if possible, we experimentally confirm that n ≥  <dig> if e ∈ es or that e is required if e ∈ el ∪ er.
finally, if some g ∈ cc that are not good still remain, edges in g are forcibly removed from ew by setting n to  <dig> if e ∈ es or by changing e not required if e ∈ el ∪ er.
definition  <dig> ) let g =  be a chromosome graph that satisfies wcc with respect to some vw ⊂ v and ew ⊂ e. then, find a set c of chromosomes on g that minimizes w when  is satisfied.
theorem  <dig> the problem chrw can be solved in o time.
see the methods section for the algorithm that solves chrw.
restriction on the length of chromosomes
in chrw, we removed restrictions on the length of chromosomes.
this relaxation is necessary to make the problem solvable in polynomial time.
definition  <dig> ) chrw with restriction on length  is the same problem as chrw, except that the length of each chromosome ci is bounded by a parameter λi , where nl is the maximum possible number of chromosomes.
theorem  <dig> the problem chrl is np-complete.
see the methods section for proof that problem chrl is np-complete.
discussion
handling practical situations
solutions to the chromosome problems are affected by errors in given sv data.
however, some errors can be mitigated as follows.
first, a false positive aberrant adjacency may be correctly ignored in the optimal solution because a set of chromosomes that uses such an adjacency is expected to have a larger cost than those ignoring the adjacency.
second, the effects of a missing aberrant adjacency may be limited to segments including its ends because a chromosome that contains the missing adjacency may be recognized as two split chromosomes.
finally, there is a chance that incorrect copy numbers will be corrected if they are inconsistent with other svs.
in addition to segments in the reference genome, our method can handle newly inserted fragments not in the reference genome.
such a fragment is incorporated yasuda and miyano page  <dig> of  <dig> into a chromosome graph as a new chromosome.
in particular, an edge e, where |e| is equal to the length of the fragment, is added to es, and edges that connect vertices in a chromosome graph to e are added to el.
if any breakpoints are contained within the new fragment, vertices and edges are added to vm and er, respectively.
if a breakpoint corresponds to any aberrant adjacency, edges are also added to el.
if a gene duplication has occurred in the target genome, it causes an increased copy number and aberrant adjacencies flanking the gene.
if it is a tandem duplication, an aberrant adjacency connecting the upstream and downstream regions of the gene should exist.
if these svs exist in given sv data, any solution to our problem has to take into account gene duplication.
limitations
a mixture of many cells cannot be handled because it is difficult to correctly estimate copy numbers.
however, our method may generate meaningful results for data obtained from multiple cells if the sum of copy numbers is correctly estimated.
in this case, the solution is a mixture of chromosomes of all cells in the sample, although some of the chromosomes might be fused.
note that many optimal solutions may exist depending on how an optimal circulation is converted into chromosomes.
.
choosing the right solution requires additional information such as the mate-pairs of long genomic fragments, or the result of experiments involving such techniques as fluorescence in situ hybridization  that indicate whether or not distant genomic regions are in the same chromosome.
toward implementation
for implementation, we require an algorithm that can calculate an optimal circulation on the bidirected graph.
it would be difficult to implement gabow's algorithm because no efficient implementation is currently known.
another option would be to use medvedev's algorithm  <cit> .
any solver for general integer programming could also be used, as demonstrated by oesper et al.
<cit> , although the computational time bound is not guaranteed.
CONCLUSIONS
continuing technological innovations in dna sequencing will, in future, allow the prediction of an enormous number of svs.
however, detecting only individual svs cannot reveal the global structure of chromosomes.
here, we formulated the problem of inferring chromosomes from the aberrant adjacencies of genomic regions, copy number variations , and the number and length of chromosomes.
the problem, which we term as the chromosome problem , was proved to be np-complete.
however, if an instance of chrp satisfies a constraint, which we call a weakly connected constraint , and if the length of chromosomes is ignored, the problem can be solved in o time.
this work provides a theoretical basis for the development of practical computational tools that are emerging for use in analysis of the global structure of chromosomes based on svs.

 next-generation sequencing technologies have drastically reduced the cost of genome sequencing. as more genomic sequences have become available, it has become clear that genomes contain many structural variations, which include large insertions, deletions, tandem duplications, and translocations. svs have already been associated with diverse diseases. for example, the fusion genes bcrabl and eml4-alk play key roles in the development of cancer, and it is believed that other recurrent rearrangements remain to be discovered. in cancer genomes, many svs are occasionally concentrated in a small region of the genome. it has been suggested that a single catastrophic mutational event, known as chromothripsis, causes these concentrations. a study of prostate cancer also uncovered a distinct type of complex rearrangement termed chromoplexy, wherein rearrangements are unclustered but involve multiple chromosomes. complex genomic rearrangements have even been observed in germline mutations, resulting in serious congenital diseases. because of their importance in functions of the genome, various methods have been developed for finding svs. when genomic rearrangements are complex, enumerating only individual svs is insufficient for elucidating the global structure of chromosomes, i.e., how the segments in a reference genome are extracted and ordered in an unknown target genome. here, the reference genome is known and is a pre-existing sequenced genome of the same organism, such as the grch build of the human genome. in this study, we address the problem of inferring the global structure of chromosomes based on sv data, which refer to aberrant adjacencies of genomic regions and copy number variations in this study. by solving this problem, we can determine the order of the genomic regions in the target genome. this order affects the structure of proteins if the genomic regions contain coding regions, and regulation of genes if the genomic regions include promoters or enhancers. in addition, raw sv data could be corrected by inferring the global structure of chromosomes because an optimal global structure would ignore false positive detection of aberrant adjacencies or correct wrongly estimated copy numbers. the task of inferring chromosomes is formulated as an optimization problem on a graph, which we term as a chromosome graph. our contributions are summarized as follows: • to infer the global structure of chromosomes, we formulate a computational problem that takes into account the number and length of chromosomes, as well as aberrant adjacencies and cnvs caused by genomic rearrangements. by taking sv data as the input, relatively low-depth ngs sequencing can be used. • we prove that the problem is np-complete. • we propose a biologically meaningful restriction that makes the problem solvable in polynomial time. we also show an algorithm that solves the restricted problem. oesper et al. presented a pioneering work that aimed to infer the global structure of chromosomes from sv data. they formulated the copy number and adjacency genome reconstruction problem. their formulation is based on graphs that they termed interval-adjacency graphs. these graphs are essentially the same as our chromosome graphs, except that we used bidirected graphs while they used alternating paths to exclude paths on the graph that do not correspond to chromosomes. they also implemented an efficient algorithm called paired-end reconstruction of genome organization that solved their problem and obtained promising results. our work includes the following results that were not addressed by oesper et al. first, we present a formulation that takes into account the number and length of chromosomes determined experimentally. second, we prove that the problem is np-complete. finally, we propose a variation of the problem that can be solved in polynomial time. some methods can also be applied to analyze the global structure of genomes by using non-sv data. first, de novo sequence assembly aims at reconstructing target genomes from raw ngs sequences. it includes a step to order fragments of genomes obtained by assembling ngs sequences. the step is usually implemented as an optimization problem, involving searching for paths that cover all vertices or all edges corresponding to substrings of genome sequences. by contrast, we allow some vertices and edges to be ignored because some portions of the reference genome might not appear in the target genome. second, reference-assisted assembly, also known as comparative assembly, aims at ordering segments of an unknown target genome by using known genomes of other organisms. by contrast, we order segments so that the chromosomes in the solution are most consistent with the sv data and the experimentally determined number and length of chromosomes. finally, methods based on permutations of integers compare two genomes represented by two sequences of integers corresponding to genes or markers in the genome. instead of using such sequences, we exploit sv data. the rest of this paper is organized as follows. first, we present types of experimental data from which we infer the global structure of chromosomes. next, we give our formulation of the problem of inferring the global structure of chromosomes, and show that the problem is np-complete. then, we show a variation of the problem that is solvable in polynomial time. finally, we discuss our results and state our conclusions.  experimental data we assume the following experimental data as input. aberrant adjacencies in the target genome, distant segments in the reference genome may be adjacent because of rearrangements. such aberrant adjacencies are detected by using ngs technologies as follows. first, ngs technologies can generate read pairs that are a few hundred bases apart from each other in the target genome. if two reads of a pair are not mapped to the reference genome with the expected orientations and mapped distance, the pair is called a discordant pair and is likely to be caused by svs. second, if the alignment of a read and reference genome is split into more than one portion, such a split read also indicates a rearrangement. a breakpoint is a position at a boundary of a rearrangement. here, we ignore small differences between the real breakpoints and their estimations. copy numbers the number of occurrences of a subsequence in the reference genome may change because of rearrangements. this phenomenon results in copy number variations. traditionally, cnvs have been analyzed by using dna microarrays. several recent methods detect cnvs by finding changes in the depth of coverage of ngs sequences. although tumor samples are usually a mixture of normal cells and various tumor cells, the copy numbers of a cancer cell can still be estimated by single-cell analysis. in this paper, for the sake of conciseness, the boundaries of cnvs are also called breakpoints. number of chromosomes and truncations identifying chromosomes and finding aberrant chromosomes by microscopy is an important part of clinical diagnostics. the number of chromosomes, denoted by nn in this paper, is available after inspection. throughout this paper, we assume that nn ≥ in addition, we also take into account the number of chromosomal truncations, which we denote as nt. chromosomal truncations are detected as a decrease in copy numbers without aberrant adjacencies. we consider nn and nt to improve the inference of the global structure of chromosomes from sv data. chromosome length the length of chromosomes can be estimated experimentally from flow karyotyping, and, approximately, from microscopic images. here, the estimated length is denoted by λi for ≤ i ≤ nl, where nl is the maximum possible number of chromosomes. problem definition any instance of our problem is modeled as a graph that we term a chromosome graph. the graph contains elements derived from the reference genome and experimental data. each vertex corresponds to a location in the reference genome. in addition, each edge corresponds to either a segment in the reference genome, an adjacency of flanking segments in the reference genome, or an aberrant adjacency in the target genome caused by rearrangements. we assume that the target genome is a set of chromosomes, each of which is a concatenation of segments in the reference genome. each chromosome in the target genome is represented as a path on the graph, and these paths explain how segments in the reference genome are incorporated into the target genome. the goodness of the estimated target genome is measured by a cost function, and we search for an optimal set of chromosomes that minimizes this cost function. we first define a graph that contains some of elements described above. then, we extend the graph to a chromosome graph. finally, we present the formal definition of the problem. prototype chromosome graph we first construct an undirected graph called a prototype chromosome graph, g =. let nc be the number of chromosomes of the reference genome and ni be the number of breakpoints in the i-th chromosome of the reference genome. then, v contains the following vertices. • vertices corresponding to breakpoints: vm={vi,j|1≤i≤nc,1≤j≤ni}. • vertices corresponding to the beginning of chromosomes in the reference genome: v5={vi,0|1≤i≤nc}. • vertices corresponding to the end of chromosomes in the reference genome: v3={vi,ni+1|1≤i≤nc}. then, we define v = v ∪ v ∪ vm. next, we define a set of edges, e. we make the following two types of edges. • edges corresponding to segments between two breakpoints that are next to each other in the reference genome. for each ≤ i ≤ nc and ≤ j ≤ ni, we make an edge ei,j =. • edges corresponding to aberrant adjacency of two segments in the reference genome. let na be the number of detected aberrant adjacencies. for the k-th aberrant adjacency that links positions corresponding to vi j and vi j we make an edge elk=. then, we define es={ei, j|1≤i≤nc,0≤j≤ni},el={elk|1≤k≤na},   e=es∪el. chromosome graph in a prototype chromosome graph, a path might visit two edges in el contiguously. such a path does not correspond to a real chromosome. to exclude such a path we use a technique similar to that of oesper et al.. although oesper et al. used alternating paths, their formulation can be represented by using a bidirected graph whose edges have directions at both ends. we directly define our graph by using a bidirected graph. let d ∈ {+,−} be the direction of an edge e at a vertex v, and −d be the opposite direction of d. • each vertex vi,j ∈ vm is split into two vertices vi,j+ and vi,j-. the set vm is redefined as vm={vi,j-,vi,j+|1≤i≤nc,1≤j≤ni}. vertices in v and v are renamed so that v5={vi,0-|1≤i≤nc},v3={vi,ni+1+|1≤i≤nc}. • an edge ei,j = ∈ es is reconnected to vi,j- and vi,j+1+. in addition, d=- and d=+. • let e ∈ el be an edge connected to vi,j in the prototype chromosome graph. if e corresponds to an aberrant adjacency involving the segment that stretches toward vi,j+ e is reconnected to vi,j- and d is set to'+'. otherwise, e is reconnected to vi,j+ and d is set to'−'. • we add the following set of new edges: er={e^i,j=|1≤i≤nc,1≤i≤ni}. directions are set so that d=- and d=+. the modified graph represents a chromosome graph. paths and chromosomes a path c = v1e1v2e2v... elvl+ on a chromosome graph g is an alternating sequence of vertices and edges, which has the following properties: • the first and the last of c are vertices. • any subsequence of the form ekvkek+ means that d = −d. a path c is said to visit an edge e if c contains e. similarly, c is said to visit a vertex v if c contains v. when a path is written as a sequence of vertices and edges, for simplicity, we omit the notation of the vertices if they are clear. let c = {c c..., c|c|} be a multiset of paths on g. we define c as a multi-set so that more than one identical path can exist. in addition, let m be the number of times c visits an edge e, and m=∑ci∈cm. a cycle is a path whose first and last vertices are identical and the directions of the first and the last edges at the vertex are opposite. a chromosome on g is a path whose first and last edges are both in es. copy numbers and lengths two integers are assigned to each e ∈ e. first, n for e ∈ es represents an experimentally estimated copy number of the corresponding segment in the reference genome. second, |e| for e ∈ es represents the length of the corresponding segment in the reference genome. for e ∈ el ∪ er, we set n and |e| to the length of a path c is defined as |c|=∑e∈e|e|m. to simply describe all properties of e together, we use the following notation: e=⟨dv dv n,|e|⟩. upper bound on parameters campbell et al. presented examples of amplified regions in cancer cells. the copy numbers were less than in these regions. therefore, we assume that the copy numbers are in at most hundreds. we also assume that short repeat elements are masked in advance in order to exclude segments that appear spuriously. based on the details given above, we assume that nn, nt, and n for e ∈ es are all less than a fixed constant u. the value of u does not have to be determined because u is only used in the analysis of computational complexity. formulation of the problem to find an optimal set of chromosomes, we define an optimization problem over a chromosome graph. we define a cost function to be used as a target function of the optimization problem. this function imposes costs on the number of chromosomes, the number of chromosomal truncations, and the number of visits to edges, penalizing for deviations from those that are experimentally expected. let c = {c c..., c|c|} be a multi-set of chromosomes on g, and wn be the cost of the difference between nn and |c|. also let tr be the number of ends of chromosomes in vm, and wt be the cost of the difference between nt and tr. in addition, w for e ∈ es is defined as the cost when e is visited x-times. for e ∈ el ∪ er, w is set to we assume that wn, wt, and w for e ∈ es monotonically increase as ||c| − nn|, |tr − nn|, and |x − n| increase, respectively. then, we define the cost function w as follows: w=wn+wt+∑e∈ew). we assume that each term is if and only if |c|=nn,tr=nt,m=n for e∈es. with these notations, we formulate the problem of inferring the global structure of chromosomes as follows: definition ) suppose that we are given a chromosome graph g =, a cost function w, and parameters λi, where nl is the maximum possible number of chromosomes. then, find a multi-set of chromosomes c on g that minimizes w under the constraint that |ci| ≤ λi for ci ∈ c. although a similar problem was proposed previously, its computational complexity was not analyzed. theorem chrp is np-complete. in the methods section, we prove theorem polynomial-time solvable variation we propose a variation of chrp that is solvable in polynomial time. for e ∈ el ∪ er, it is highly likely that m ≥ if e is supported by a large number of paired-reads. therefore, it is worth considering a variation in which some edges in el∪ er must appear in the target genome. we refer to the edges as required edges. in addition, because chromosomal truncations can be detected, it is also worth considering a variation in which we know where the ends of the chromosomes of the target genome exist in the reference genome. because the definition of w is abstract, we focus on a cost function such that wn=qn||c|-nn|,wt=qt|tr-nt|,w=|e||x-n|, where qn and qt are constants given as parameters. the values of qn and qt are tuned in advance so that known global structures of genomes are well reconstructed. weakly connected constraint let g = be a general bidirected graph. a subgraph g of g is a weakly connected component if g is a connected component when all directions are removed. in addition, g is maximal if g is not a subgraph of a larger weakly connected component. for a subset e' of e, we define cc as a set of maximal weakly connected components of a graph induced from g by removing the edges not in e'. definition ) let g = be a chromosome graph. also let vw and ew be subsets of v and e, respectively. each g ∈ cc is good if g contains at least one vertex in vw. then, g satisfies the weakly connected constraint if all g ∈ cc are good. we use wcc by setting vw to a set of vertices that correspond to ends of chromosomes in the target genome, and ew = {e ∈ es|n ≥ 1} ∪ {e ∈ el ∪ er|e is required}. see figure for an example. an instance that satisfies wcc can be obtained as follows. first, vw is obtained by finding the positions of chromosomal truncations, as well as the ends of the chromosomes of the reference genome that remain in the target genome. because a chromosome that does not include detected ends can be in a solution, vw does not need to contain all ends of chromosomes in the target genome. we assume that nt ≥ |vw|. next, if g ∈ cc is not good, edges e ∈ e on some path connecting g and good g' ∈ cc are added to ew. to do this, if possible, we experimentally confirm that n ≥ if e ∈ es or that e is required if e ∈ el ∪ er. finally, if some g ∈ cc that are not good still remain, edges in g are forcibly removed from ew by setting n to if e ∈ es or by changing e not required if e ∈ el ∪ er. definition ) let g = be a chromosome graph that satisfies wcc with respect to some vw ⊂ v and ew ⊂ e. then, find a set c of chromosomes on g that minimizes w when is satisfied. theorem the problem chrw can be solved in o time. see the methods section for the algorithm that solves chrw. restriction on the length of chromosomes in chrw, we removed restrictions on the length of chromosomes. this relaxation is necessary to make the problem solvable in polynomial time. definition ) chrw with restriction on length is the same problem as chrw, except that the length of each chromosome ci is bounded by a parameter λi, where nl is the maximum possible number of chromosomes. theorem the problem chrl is np-complete. see the methods section for proof that problem chrl is np-complete. discussion handling practical situations solutions to the chromosome problems are affected by errors in given sv data. however, some errors can be mitigated as follows. first, a false positive aberrant adjacency may be correctly ignored in the optimal solution because a set of chromosomes that uses such an adjacency is expected to have a larger cost than those ignoring the adjacency. second, the effects of a missing aberrant adjacency may be limited to segments including its ends because a chromosome that contains the missing adjacency may be recognized as two split chromosomes. finally, there is a chance that incorrect copy numbers will be corrected if they are inconsistent with other svs. in addition to segments in the reference genome, our method can handle newly inserted fragments not in the reference genome. such a fragment is incorporated yasuda and miyano page of into a chromosome graph as a new chromosome. in particular, an edge e, where |e| is equal to the length of the fragment, is added to es, and edges that connect vertices in a chromosome graph to e are added to el. if any breakpoints are contained within the new fragment, vertices and edges are added to vm and er, respectively. if a breakpoint corresponds to any aberrant adjacency, edges are also added to el. if a gene duplication has occurred in the target genome, it causes an increased copy number and aberrant adjacencies flanking the gene. if it is a tandem duplication, an aberrant adjacency connecting the upstream and downstream regions of the gene should exist. if these svs exist in given sv data, any solution to our problem has to take into account gene duplication. limitations a mixture of many cells cannot be handled because it is difficult to correctly estimate copy numbers. however, our method may generate meaningful results for data obtained from multiple cells if the sum of copy numbers is correctly estimated. in this case, the solution is a mixture of chromosomes of all cells in the sample, although some of the chromosomes might be fused. note that many optimal solutions may exist depending on how an optimal circulation is converted into chromosomes.. choosing the right solution requires additional information such as the mate-pairs of long genomic fragments, or the result of experiments involving such techniques as fluorescence in situ hybridization that indicate whether or not distant genomic regions are in the same chromosome. toward implementation for implementation, we require an algorithm that can calculate an optimal circulation on the bidirected graph. it would be difficult to implement gabow's algorithm because no efficient implementation is currently known. another option would be to use medvedev's algorithm. any solver for general integer programming could also be used, as demonstrated by oesper et al., although the computational time bound is not guaranteed.  continuing technological innovations in dna sequencing will, in future, allow the prediction of an enormous number of svs. however, detecting only individual svs cannot reveal the global structure of chromosomes. here, we formulated the problem of inferring chromosomes from the aberrant adjacencies of genomic regions, copy number variations, and the number and length of chromosomes. the problem, which we term as the chromosome problem, was proved to be np-complete. however, if an instance of chrp satisfies a constraint, which we call a weakly connected constraint, and if the length of chromosomes is ignored, the problem can be solved in o time. this work provides a theoretical basis for the development of practical computational tools that are emerging for use in analysis of the global structure of chromosomes based on svs. 
although various methods for detecting svs have been developed, the global structure of chromosomes, i.e., how segments in a reference genome are extracted and ordered in an unknown target genome, cannot be inferred by detecting only individual svs. the computational complexity of the inference can be reduced by detecting the segments of the reference genome at the ends of the chromosomes of the target genome and also the segments that are known to exist in the target genome. this problem takes into account the aberrant adjacencies of genomic regions, the copy numbers, and the number and length of chromosomes. our results establish a theoretical foundation for the development of practical computational tools that could be used to infer the global structure of chromosomes based on svs. here, we formulate the problem of inferring the global structure of chromosomes from svs as an optimization problem on a bidirected graph. we also explain how to obtain experimental data that satisfies the weakly connected constraint. although the problem is np-complete, we propose its polynomial-time solvable variation by restricting instances of the problem using a biologically meaningful condition, which we call the weakly connected constraint.
 next generation sequencing technologies have made it possible to exhaustively detect structural variations in genomes. although various methods for detecting svs have been developed, the global structure of chromosomes, i.e., how segments in a reference genome are extracted and ordered in an unknown target genome, cannot be inferred by detecting only individual svs.  here, we formulate the problem of inferring the global structure of chromosomes from svs as an optimization problem on a bidirected graph. this problem takes into account the aberrant adjacencies of genomic regions, the copy numbers, and the number and length of chromosomes. although the problem is np-complete, we propose its polynomial-time solvable variation by restricting instances of the problem using a biologically meaningful condition, which we call the weakly connected constraint. we also explain how to obtain experimental data that satisfies the weakly connected constraint.  our results establish a theoretical foundation for the development of practical computational tools that could be used to infer the global structure of chromosomes based on svs. the computational complexity of the inference can be reduced by detecting the segments of the reference genome at the ends of the chromosomes of the target genome and also the segments that are known to exist in the target genome. 21- january the thirteenth asia pacific bioinformatics conference hsinchu, taiwan 