The goal of gene nding is to locate genes, which are important segments of DNA encoding proteins. Programs solving this task are based on hidden Markov models (HMMs) capturing statistical features extracted from known genes, but often also incorporate hints about the correct gene structure extracted from experimental data. Existing gene nding programs can use such external information only in a limited way. Typically, they can process only simple hints describing a single part of the gene structure, because these are relatively easy to incorporate to standard HMM algorithms, but cannot cope with complex hints spanning multiple parts. We have developed an e cient algorithm able to process such complex hints. Our experiments show that this approach slightly increases the accuracy of gene prediction. We also prove that a more general class of hints leads to an NP-hard problem.
De nition 1 (Optimal labeling with hints prob? This research is funded by European Community FP7 lem). Given is positive integer n, nite alphabet , grant IRG-231025, VEGA grant 1/0210/10, and APVV and a set of hints. Each hint is a pair ( ; b) where grant SK-CN-0007-09. n is a set of labelings and b 2 R is a bonus. We
problem arising in computational biology. Although we were originally motivated by a very speci c application, we formulate the problem quite generally and explore its variants that admit e cient polynomialtime algorithms as well as those that are NP hard.
Our motivation comes from the problem of gene nding. Here the goal is to locate segments of a DNA sequence that encode proteins produced by the organism. On a more abstract level, we are given a string X = x1 : : : xn and the goal is to produce a string A = a1 : : : an over some output alphabet of possible labels, such that ai is a label of xi, corresponding to its functional role. In gene nding, X is the input DNA sequence (over alphabet fA; C; G; T g) and the output alphabet could be = f0; 1g where 1 stands for genes and 0 for non-genic regions. We will call A a labeling or annotation of the input string X.
The desired mapping from X to A is in gene nding
often characterized by a probabilistic model de ning
probability distribution P (AjX). We then output the
labeling with the highest probability. Frequently used
models are hidden Markov models (HMMs) or their
variants such as hidden semi-Markov models and
conditional random elds [
To combine an HMM with hints, we can
manipulate probabilities of individual labelings A so that the
labeling gets a bonus for each hint agreeing with it.
Di erent gene nders de ne the set of possible hints
and their in uence on the probability space di erently,
but the possibilities are restricted by the need for
efcient algorithm nding the annotation with highest
probability in the modi ed space. The simplest form
of a hint is a point-wise hint which increases or
decreases probabilities of all annotations that have a
certain label at a certain position in the sequence [
However, a single piece of evidence often suggests
labels for a longer interval of the sequence. Splitting
such information into multiple point-wise hints leads
to information loss, because some labelings can get the
bonus even if they do not agree with the evidence over
the whole interval. Therefore, some gene nders [
For most of the time we will abstract away both the HMM and the input string X and consider only a set of hints. Indeed, probabilities from the HMM can be expressed as special hints of length 2, as we explain in Section 2. Therefore in the most general setting, we can formulate our problem as follows:
allowing compact representation of a potentially large set . In particular, a complex hint is a four-tuple (s; e; Y; b) such that 1 s e n and Y 2 e s+1 is the labeling suggested for xs : : : xe (see Figure 1).
Set for this hint is = s 1Y n e. Interval hints are a special case of complex hints with Y = ak for some a 2 and point-wise hints are a special case of interval hints with s = e. say that a labeling A 2 n agrees with hint ( ; b) if form with running time O(n2j j2). With appropriate A 2 . The score of a labeling A 2 n is the sum of data structures, it is possible to implement the algobonuses of all hints that agree with A. The goal is to rithm so that processing of hints adds only an additive nd a labeling with the maximum score. term O(m) where m is the number of hints. However, a more e cient algorithm would be desirable if we wanted to use hints with regular HMMs, where the Viterbi algorithm is linear in n. Running time of our algorithm for complex hints with positive bonuses will not depend on the sequence length, only on the number and total length of hints.
Complex hints with positive bonuses. In order to introduce our algorithm for a set of complex hints with positive bonuses, we start with several necessary definitions. Let h = (s; e; y1 : : : ys e+1; b) be a complex h1 = (1; 4; 0001; 2) 0001... hint. Then for i 2 [s; e] expression `(h; i) denotes lah2 = (2; 3; 00; 1) .00.... bel suggested by h for xi, that is, `(h; i) = yi s+1. h3 = (2; 6; 00100; 1) .00100. Now let us consider two hints h1 = (s1; e1; Y1; b1) and h4 = (3; 6; 0001; 1) ..0001. h2 = (s2; e2; Y2; b2). We say that h1 and h2 are comh5 = (6; 7; 02; 1) .....02 patible if they agree in the intersection of their interA 0001002 vals, that is, if for every i 2 [s1; e1] \ [s2; e2] we have Fig. 1. A set of complex hints for n = 7 and = f0; 1; 2g `(h1; i) = `(h2; i) (non-intersecting hints are always and an optimal labeling with score 5, agreeing with hints compatible). Hint h1 is a subset of hint h2 if they are h1, h2, h3 and h5. Note that h2 is an interval hint. compatible and [s1; e1] [s2; e2]. Hint h2 is an extension of h1 if they are compatible and e2 > e1 and
In this work we describe an e cient algorithm for s2 > s1. Note that if s1 = s2, e1 = e2, and Y1 = Y2,
nding the optimal labeling for a set of complex hints, these two hints can be replaced by a single hint with
which is a non-trivial extension of algorithms for in- bonus b1 + b2. We will assume that such a
transformaterval hints (Section 2). We also show that additional tion is done on all applicable pairs.
natural generalization of the problem where some po- In our algorithm, we transform the input to create
sitions between s and e are allowed to vary, leads to a weighted directed acyclic graph (DAG) such that the
an NP-hard problem (Section 3). Finally in Section 4, optimal labeling corresponds to the path with
maxiwe describe the use of our algorithm in the context mum weight between given two vertices s and t. Such
of gene nding and show experimental results on real longest paths can be found in DAGs e ciently, in
and simulated data. O(jV j + jEj) time [
In this section we give a polynomial-time algorithm Our graph has one vertex for each hint and two spewhich nds the optimal labeling for a set of complex cial vertices s and t. There is an edge from h1 to h2 if hints. We will rst discuss several simpler cases, later and only if h2 is an extension of h1. The weight of this generalizing the algorithm to the full problem. edge is the sum of the bonus of h2 and bonuses of all hints that are subset of h2 but are not a subset of h1 (see Figure 2). Vertices s and t are connected with other vertices as if they corresponded to sentinel intervals beyond the end of the sequence, namely (0; 0; a; 0) and (n + 1; n + 1; a; 0). Clearly the graph created in this way is acyclic, because vertices on each path have increasing coordinates of their endpoints. Correctness of the algorithm is given by the following theorem.
Interval hints. Gene nders employing interval hints typically proceed by dynamic programming. For each pre x x1 : : : xi of the input string X, they consider all possibilities for the last region of this pre x labeled by one label (that is, all possible j i and a 2 such that aj = aj+1 = = ai = a and aj 1 6= a). For each such interval (j; i), it is easy to compute the sum of bonuses of all interval hints agreeing with label a.
This type of algorithm is dictated by the fact that
gene nders combine hints with hidden semi-Markov
models or their variants [
with score S there is a path with weight S and therefore W S . Let H be the set of hints that agree with A. Let HS be the set of all hints from H that are a subset of another hint from H, and let HR = H nHS . Let h1 and h2 be two di erent hints from HR such that s1 < s2. Then also e1 < e2 because no hint in HR is a subset of another, and these two hints are compatible because they both agree with A. Therefore, h2 is an extension of h1.
Our path will start in s, pass through all vertices in set HR ordered from left to right by their left endpoints and end in t. As we have shown, all necessary edges on the path exist. Bonus of hint h 2 HR is included in the weight of the edge entering h and bonus of hint h 2 HS is included in the weight of the edge entering the leftmost hint h0 2 HR such that h is a subset of h0. Bonuses of no other hints are included in the weight of the path, and therefore its weight is exactly S.
Now we will prove that for any path from s to t with weight W , there is a labeling with score at least W , implying that W S . Let H0 be the set of all hints corresponding to vertices of except s and t. We will construct a labeling A = a1 : : : an as follows. If a position i is not covered by any hint in H0, its label ai can be chosen arbitrarily. If i is covered by some hints h1; : : : ; hk from H0, they suggest the same label for position i and this label is chosen as ai.
Now let H00 be the set containing all hints from H0 and all hints that are subsets of hints from H0. The score S of path is the sum of bonuses of hints from H00. Also, each hint from this set agrees with A. The score of A is the sum of all bonuses that agree with it, therefore S W . tu
We have proved that the weight of the optimal path is equal to the score of the optimal labeling and the proof also implies an algorithm to convert the optimal path to a labeling with the same score. Note however that weights of some suboptimal paths do not correspond to the score of any labeling, as a labeling that agrees with all vertices on a path may also agree with other hints that the path avoids.
Our graph has O(m) vertices and O(m2) edges where m is the number of hints. As we will show below, it can be constructed in O(m2 + `) time, where ` is the sum of lengths of all hints. The running time of the whole algorithm is therefore O(m2 + ` + n) where the dependence on n comes only from the necessity to produce a labeling of length n (using arbitrary labels for parts of the sequence not covered by any hint). Running time improvement for practical instances. In practical gene nding instances, we expect hints to be much shorter than n and to be spread along the length of the sequence. We can modify the graph so that it has fewer edges if every position is covered by at most d hints for some d < m. The construction shown above will create edges even between hints that are far apart, and those can be eliminated. The weight of an edge from hint h0 to hint h depends on mutual position of these hints, because we include only those subset hints of h that end after the end of h0. However, the weight will be the same for all hints h0 that do not intersect h. Our goal is to remove such edges from the graph and replace them with a smaller number of edges linear in m.
We will say that a hint h2 is a strict extension of a hint h1 if h1 is an extension of h2 and the two hints overlap. Our new graph will have a vertex for each hint, two special vertices s and t for sentinel hints and a skipping vertex vi for every position i which is a right endpoint of at least one hint (including position 0 where the sentinel hint for s ends). Skipping vertices are connected to a chain going from left to right with edges of weight 0. Vertex for a hint h is connected to all hints that are its strict extensions, with the same edge weights as before. It is also connected to the skipping vertex for its right endpoint with an edge of weight 0. Finally, each skipping vertex vi is connected to all hints that start in the interval (i; j] where vj is its neighbor in the chain of skipping vertices. The edge from vi to h will contain the bonus of h and all its subset bonuses. Paths in this new graph have 1-1 correspondence with the paths in the original graph, where an edge between two non-overlapping hints is now replaced by a path through skipping vertices. The number of vertices is O(m) and the number of edges O(md), since from a vertex for hint h there are at most d outgoing edges: one to a skipping vertex and at most d 1 to other hints, because all these hints cover the right endpoint of h. Similarly the number of incoming edges is at most d. Finally, the number of edges between skipping vertices is O(m). The overall time of the algorithm with this graph will be O(md + ` + n); we still need to demonstrate that the graph can be constructed within this running time. The critical ingredient is the ability to check in constant time whether two hints are compatible. This can be achieved by building a su x tree of the strings associated with individual hints and preprocessing the sufx tree for longest extension queries. These queries allow us to take two su xes of any of the strings and determine the length of their common pre x. In our scenario we take two hints (s1; e1; Y1; b1), (s2; e2; Y2; b2) and if they overlap by some length d > 0, we determine the positions of the start of the overlap in strings Y1 and Y2. If the su xes starting at these two positions have a common pre x of length at least d, the two hints are compatible. They are also compatible if d = 0. The preprocessing of necessary structures can be done in O(`) time, and compatibility of each pair of hints can be then assessed in O(1) time [8].
To nd the edges between hint vertices, we rst sort all hints by left endpoints. This can be done in O(n + m) time by counting sort. Next, we traverse the sorted list and maintain a set of active hints. A hint is active if it overlaps the left endpoint of the current hint in the list. In every step, the list contains at most d hints, and therefore we can in each iteration traverse the list and remove hints that are no longer active. The current hint h is a strict extension of any active hint h0 such that h0 and h are compatible and h is not a subset of h0. This can be checked in O(1) time per pair of hints. If the current hint h is a subset of some active hint h0, we will append h to a list of subsets of h0. with positive bonuses. Each hint (s; e; Y; b) with a negative bonus b is transformed to a set of hints of the form (s; e0; Y 0; jbj) such that s e0 e and Y 0 is the same as Y on the rst e0 s positions and di ers from Y on its last position. We create all (j j 1) (e s + 1) combinations of e0 and Y 0 of this form. Clearly, these hints are mutually incompatible, and therefore at most one of them will agree with any annotation. An annotation A agrees with one of these hints if and only if it does not agree with the original hint h. This transformation increases the score of every annotation by jbj: the annotations agreeing with h will increase by jbj because hint h is omitted from the set and all other annotations agree with one of the new hints, thus getting an additional bonus of jbj. When we transform all hints with negative values in this way, we increase the total score of every labeling by the sum of absolute values of all negative bonuses. This is a constant and therefore the optimal labeling will remain the same and can be found by the algorithm described above. Unfortunately, the number of hints m as well as their total length ` increase by a factor of Lj j where L is the length of the longest negative hint, but the running time is still polynomial.
nding, we typically (although not exclusively [
At the end of traversal, we have for each hint h the ticular labeling A in hidden Markov models or condilist of its subset hints and the list of incoming edges tional random elds can be written as from other hint vertices. We sort both these lists by right endpoints by counting sort in time proportional n to the length of h (the right endpoints of all these P (A) = Y p(i; ai; ai+1; X); hints are within h). Now we use a merge-like algorithm i=1 with two pointers to the two lists to nd for every where factors p(i; ai; ai+1; X) depend only on two adincoming edge from hint h0 the bonus sum of subset jacent labels ai and ai+1 (and some portion of the hints that end after the end of h0. Edges incident to input string X). They are computed from the emisskipping vertices can be easily constructed within the sion and transition probabilities of the model. We will desired running time. The overall running time of the consider the case when the total score of A has the graph construction is thus O(md + ` + n) where the form n term comes from sorting and can be replaced by O(m log m).
described above is e cient, but can only handle hints with positive bonus values. If a hint h has a negative bonus value, the path could skip its vertex in the graph, even if other visited vertices imply that the labeling agrees with h and its bonus should be counted.
The graph may thus contain paths with weight higher that the score of the optimal labeling.
As we will show, we can transform a set of hints with arbitrary bonuses to an equivalent set of hints where B is the sum of bonuses of all agreeing hints. The log values in the sum can be written as hints of length 2 of the form (i; i + 1; aiai+1; log p(i; ai; ai+1; X)). Overall, we will need nj j2 such hints and they typically all have negative score. After applying the transformation described in the previous paragraphs and combining together hints with the same values of s, e and Y; we get O(nj j2) additional hints of length 1 and 2 with positive bonuses.
B + log P (A) = B + n X log p(i; ai; ai+1; X); i=1
This generic procedure works only if the states of corresponds to jth literal from ith clause, where pi;j = the HMM correspond exactly to the symbols of the N +3(i 1)+j. For each such literal we will add an asoutput alphabet . Gene nding HMMs typically have signment hint of the form (k; pi;j ; zf0; 1gpi;j k 11; 1) a much larger state space, with several states cor- where k is the index of the variable forming this literal responding to the same output label. This situation and z = 1 if the literal is yk and z = 0 if the literal could be expressed using more general subset hints de- is :yk. Notation f0; 1gc represents c copies of the set scribed in Section 3. Although subset hints lead in gen- f0; 1g 2 +. In other words, the hint connects the literal to NP-hard problems, special cases necessary for eral with its satisfying variable assignment, and if the handling large state spaces can be solved e ciently, as literal is selected by api;j = 1 and the variable yk has discussed at the end of the next section. Moreover, it is the satisfying assignment, the labeling gets a bonus 1. also possible to create specialized algorithms for com- We will also add three selector hints for every clause, bining complex hints with a hidden Markov model [12]. that enforce that exactly one literal from the clause By taking the special structure of the problem into ac- is selected by api;j = 1. These hints have the form count, we may obtain more e cient solutions than by (pi;1; pi;3; Y; K) where Y is a binary string of length converting the HMM to a collection of hints. three containing exactly two zeroes. Note that for each clause at most one of the selector hints can agree with a given labeling. 3 NP-hardness for subset hints In order to achieve total score M + M K, the annotation has to agree with one selector hint for evA subset hint is a four-tuple h = (s; e; Y; b) such that ery clause. The loss of even one such selector could numbers s, e, and b are de ned as for a complex hint not be compensated because the sum of bonuses of all and Y is a string of length e s + 1 over an extended assignment hints is only 3M , which is less than K. alphabet + containing all non-empty subsets of . Selector bonuses that contribute bonus M K enforce Expression `(h; i) now denotes the set of labels sug- that exactly one literal in each clause is selected. The gested by h for xi and a labeling A agrees with h if for selected literal has a potential to contribute bonus 1 every position i 2 [s; e] the label ai is in the set `(h; i). if it is indeed satis ed in the assignment speci ed by Unfortunately, our algorithm for complex hints can- the labeling of the rst N symbols. If the formula has not be straightforwardly extended to this scenario, be- score at least M + M K, every clause has exactly one cause the relation of extension is not transitive, which literal which is simultaneously selected and satis ed. is crucial for the existence of a labeling satisfying all Note that multiple literals per clause may be satis ed, hints on a path in our graph. but if they are not selected, they will not in uence
As we will prove, it is unlikely that the problem the score. Annotation with score M + M K thus correcan be solved e ciently in the full generality by other sponds to a satisfying assignment of the formula and methods, since it is NP-hard. vice versa. tu Theorem 2. The problem of testing whether there is This proof is a slight modi cation of our earlier a labeling A with score at least t for a set of subset proof for the use of RT-PCR queries in gene ndhints is NP-complete, even for a binary alphabet . ing [10]. In this earlier work we have considered hints of a special form that suggest a speci c label at both Proof. Clearly the problem is in NP (if the size of in- ends and allow arbitrary labels in the middle. Howput is much smaller than n, we can specify only por- ever the output labeling was constrained to obey an tions of A covered by hints and this is su cient for additional DAG of possible gene structures. Here we e cient computation of the score). have adapted the proof for the simpler case where the
To prove NP-hardness, we will use a reduction from annotation can be arbitrary. the 3-SAT problem. Consider a 3-SAT instance with N variables y1; : : : ; yN and M clauses, each clause con- Partition subset hints. Subset hints often occur in sisting of three literals. We will encode it as a set of practice because our methods for obtaining additional hints over the alphabet = f0; 1g such that the for- information about the labeling cannot distinguish bemula has a satisfying assignment if and only if there tween some labels from . In some situations we can is a labeling with score at least M + M K where K = represent subset hints as complex hints over an alpha3M + 1. bet 0 + that forms a partition of into equiva
The length of the annotated sequence will be n = lence classes (in other words, every two elements in 0 N + 3M . The rst N labels correspond to a truth as- are disjoint subsets of ). We will now consider a situsignment to all variables, that is, ai = 1 corresponds ation where every hint contains only characters from to yi being true. Each of the remaining labels cor- or only characters from 0 (but cannot use characresponds to one literal from the formula, namely api;j ters from both). We will show that optimal labeling (over ) for such hint sets can be found in polynomial is relatively well sequenced and annotated. Genomic time. sequences and reference annotations were downloaded
Brie y, we rst create a directed acyclic graph G from the UCSC genome browser [7]. We have used for hints over similarly as in Section 2. We add new 44 MB of DNA sequence containing 5 164 genes. They hints of the form (i; i; a; 0) for all positions i and labels were split to 2 MB parts and divided to traina 2 . Both the original hints and these new hints ing ( 28 MB, 3368 genes) and testing ( 16 MB, will be vertices. We will have an edge from hint h1 1796 genes) data sets. to hint h2 if h2 is an extension of h1 and they ei- The HMM has been taken from the work of [15] ther overlap or h2 starts immediately after h1 ends. and retrained on our training data set by standard In this graph, every path consists of hints that com- procedures [6]. It has 265 states, but it is quite simple pletely cover the sequence. In the same way we also compared to state-of-the-art gene nders. For exambuild a graph G0 for hints over 0. Finally, we create ple, it does not allow arbitrary length distributions of graph G00 in which each vertex is a pair (h; h0) such exons, introns and intergenic regions and uses simpler that h is a vertex in G, h0 is a vertex in G0, hints h models of sequence motifs at exon boundaries. In our and h0 overlap and are compatible. If hint h0 ends be- experiments we compare the accuracy achieved on the fore h, this vertex will be connected to vertices of the testing set by the HMM alone and with di erent sets form (h; h00) where (h0; h00) is an edge in G0, the weight of hints. of the edge is also copied from G0. Similarly, if h ends before h0, (h; h0) will be connected to vertices of the form (h00; h0) where (h; h00) is an edge in G. Finally, Protein hints if the two hints end together, they will be connected Gene 1 Gene 2 to vertices of the form (h00; h000) where (h; h00) is an Reference edge in G and (h0; h000) is an edge in G0. The weight of the new edge will be the sum of the two source edges. Interval hints The best path in G00 then corresponds to the optimal Complex hints annotation (proof omitted due to space).
The algorithm can be extended to several groups No hints of hints, each over a di erent partition of , but the 1226000 1227000 1228000 1229000 running time would increase exponentially in the number k of such groups, because the vertices in the nal graph will be k-tuples of vertices of graphs for individual groups of hints.
Use of complex hints in gene
nding
Section 2 and applied it to the problem of gene nding.
Recall that the goal of gene nding is to nd genes, regions encoding proteins in DNA sequences. A gene in eukaryotic organisms can be divided into several Experiment with protein hints. In the rst experiment, segments called exons and introns, and only exons en- we have used a real set of hints originating from code the protein (see Figure 3). Thus the goal of gene a database of known proteins. We have downloaded all nding is to nd the position of each gene and its ex- known proteins from several insect species (D. melanoact partitioning to exons and introns. We use output gaster, D. simulans, D. pseudoobscura, Anopheles alphabet = fC; I; Xg, where C stands for coding gambiae, and Bombyx mori ) from the NCBI RefSeq exons, I for introns, and X for intergenic regions. database [13] (67; 893 protein sequences in total). We
The algorithm was implemented in C++ as a stan- have used the BLAT program [9] and scripts from
Exdalone console application called grapHMM. In order onHunter distribution [
We have tested the program on genomic data from ered by hints, whereas genes cover almost 45% of the Drosophila melanogaster (fruit y). This species is an sequence. Hints contain exon and intron labels (eximportant model organism in genetics and its genome ons are regions where the protein seems to be encoded and introns are separating parts encoding the same protein). If the whole source protein could be aligned to the genome, a single intergenic position is added to the beginning and to the end of the complete gene hint.
Our goal was to compare prediction accuracy obtained using complex hints with accuracy obtained using simpler interval and point-wise hints. Therefore we have converted our hint set to these simpler forms by splitting each complex hints to several shorter hints as necessary. Overall we have thus used three di erent hint sets: Hint set Bonus Gene sn.
Gene sp.
Exon sn.
Exon sp.
Base sn.
Base sp.
No hints Point-wise Interval Complex
{ 8 8 6 48.83% 61.08% 61.30% 61.86% 40.40% 46.00% 46.42% 46.61% 71.18% 75.89% 76.20% 76.14% 69.01% 71.73% 72.31% 72.29% 92.81% 94.35% 94.15% 94.14% 91.86% 92.00% 92.10% 92.08%
Bonuses of hints have great in uence on the gene a random place in the sequence and suggest label for prediction accuracy: if they are too low, the hints will intergenic regions along their whole length. Some of be ignored; if they are too high, wrong hints will de- these hints are correct, since by chance they are concrease the gene prediction accuracy. For simplicity, all tained in real intergenic regions, whereas others overhints in one hint set have the same bonus b, and we lap real genes. Note that we have chosen intergenic choose optimal value of b to maximize the accuracy on hints, because it is non-trivial to randomly generate the training set for each set of hints separately. The other reasonable wrong hints that have a non-zero exception are complex hints, where the bonus of a hint probability in the HMM. Overall, 74% of hints in our is bk where k is the number of contiguous regions in the set were correct. In this experiment, we have compared hint labeled by one label (or in other words the number complex and interval hints, again training their bonus of interval hints comprising this complex hint). Again on the training set and testing their performance on the value of b was optimized using the training set. the testing set. Results shown in Table 2 are analogous
Evaluation of these three hints sets on the test se- to the protein hint experiment { slight improvement in quences is shown in Table 1. Complex hints slightly the prediction accuracy at the gene level for complex increase the number of completely correctly predicted hints compared with interval hints. genes compared to the interval hints, but the di erence is less than 1%. On the other hand, di erence in Hint set Interval Complex accuracy between prediction without hints and with Bonus 6 12 one of the hint sets is quite signi cant. Gene sensitivity 60.75% 61.53%
Figure 3 shows an example of a gene where com- Gene speci city 49.43% 50.41% plex hints lead to a better prediction than interval Exon sensitivity 77.31% 77.92% hints. The algorithm with interval hints chooses an Exon speci city 76.51% 76.92% annotation agreeing with only two out of three parts Base sensitivity 94.98% 94.69% comprising a single complex hint. With complex hints Base speci city 93.52% 93.39% only annotations agreeing with the whole hint get the Tab. 2. Comparison of gene prediction accuracy with arbonus, and one such annotation is indeed the opti- ti cial hints sets, using the same accuracy measures as in mum. Table 1.
various parameters of the hint set, we have also generated arti cial hints. All hints in this set have the 5 Conclusion and open problems length 1000, and the number of hints was chosen so that the sum of their lengths is approximately n=2. In this paper, we have explored several variants of the Half of the hints were created so that they start at problem of nding optimal sequence annotation that a random place within some exon and agree with the agrees with hints with the highest total score. If the reference annotation along their whole length. The sec- hints completely specify annotation within some inond half of hints was generated so that they start at terval and all hints have positive scores, the problem can be solved quite e ciently, in time O(md + ` + n) 6. R. Durbin, R. Eddy, A. Krogh, and G. Mitchison: Biowhere n is the length of the annotated sequence, ` is logical sequence analysis. Cambridge University Press, the total length of all hints, m is the number of hints 1998. and d is the maximum number of hints overlapping 7. P.A. Fujita, B. Rhead, A.S. Zweig, et al. (2011). The a single position. If some hints have negative scores, UCSC Genome browser database: update 2011. Nucleic the problem can still be solved in polynomial time. Fi- Acids Research, 39(Database issue), 2011, D876{882. nally, we can also solve the case where hints are over 8. Dqu.enGcuess: eclodm: puAtelrgosrciitehnmces aonnd sctorminpgust,attiroenesal abniodlogsey-. two di erent alphabets, one being a partition of the Cambridge University Press, 1997. other. These algorithms can be also extended to com- 9. W.J. Kent: BLAT { the BLAST-like alignment tool. bine hints with hidden Markov models or conditional Genome Research, 12(4), 2002, 656{664. random elds. We have also shown that if we allow 10. J. Kovac, T. Vinar, and B. Brejova: Predicting gene wildcards in hints, the problem becomes NP-hard even structures from multiple RT-PCR tests. In Algorithms for binary output alphabet. in Bioinformatics, 9th International Workshop, WABI
Our results might be applicable in various elds 2009, volume 5724 of LNCS, pp. 181{193. Springer, where HMMs and their variants need to be combined 2009. with external information. However, our original mo- 11. P. Kovac: Implementacia externych zdrojov dat v tivation stems from gene nding, where complex and hplu'atedranScgieennocev,. BCaocmheelnoirusThUesniisv,eDrseiptyartimnenBtraotfisClaovma-, subset hints are the most natural form of express- 2010. ing hints from various sources. Our experiments with 12. M. Kuchar k: A new algorithm for using external ina simple gene nder show that compared to simpler formation in gene nding. Master's Thesis, Departinterval hints used before, complex hints may lead to ment of Computer Science, Comenius University in slight increases in prediction accuracy. More experi- Bratislava. Submitted 2011. ments with di erent information sources or in di erent 13. K.D. Pruitt, T. Tatusova, and D.R. Maglott: NCBI species may lead to more signi cant improvements. reference sequences (RefSeq): a curated non-redundant
Several open problems remain in this area. Our al- sequence database of genomes, transcripts and progorithms are in the worst case quadratic in the number teins. Nucleic Acids Research, 35(Database issue), of hints. The question is whether more e cient algo- 14. M20.0S7t,aDn6k1e,{6M5.. Diekhans, R. Baertsch, and D. Haussler: rithms exist at least for the case of interval hints. It Using native and syntenically mapped cDNA alignmight be also useful to consider special classes of sub- ments to improve de novo gene nding. Bioinformatset hints that can be processed in polynomial time. For ics, 24(5), 2008, 637{644. example in our earlier work the RT-PCR hints were 15. R. Sramek, B. Brejova, and T. Vinar: On-line Viterbi NP-hard in general but solvable e ciently if their rel- algorithm for analysis of long biological sequences. In ative position was constrained [10]. Finally, one could Algorithms in Bioinformatics: 7th International Workalso generalize complex hints in other ways, for ex- shop (WABI), volume 4645 of Lecture Notes in Comample, allowing some uncertainty in the exact place puter Science, pp. 240{251. Springer. where labeling changes from one label to another. 16. R.F. Yeh, L.P. Lim, and C.B. Burge: Computational inference of homologous gene structures in the human genome. Genome Research, 11(5), 2001, 803{806.