Damien Masson
email: damien.masson@univ-paris-est.fr

Serge Midonnet
email: serge.midonnet@univ-paris-est.fr

RTSJ Extensions: Event Manager and Feasibility Analyzer

We present in this paper our experience on the implementation with RTSJ of advanced algorithms to handle aperiodic traffic. We have adapted existing algorithms in order to take into account some constraints brought about by the use of Java language, and our aim which is to propose a portable mechanism. To circumscribe some difficulties, we had to use some programming ruses which could be better integrated into the specification. From these experiences resulted a set of modifications to the specification which we propose to submit to the community in this paper, in addition to a unified event manager framework.

INTRODUCTION

The aim of the Real-time Specification for Java is to design APIs and virtual machine specifications for the writing of real-time applications in Java language. An important aspect of real-time system programming is the feasibility analysis to ensure the respect of temporal constraints.

The case of hard real-time systems composed of periodic tasks was extensively elaborated for each of the many scheduling policies. The RTSJ is well designed to write such systems, with feasibility analysis methods integrated both in Scheduler abstract class and Schedulable interface.

In more realistic systems composed of hard real-time periodic tasks and soft real-time aperiodic events, three approaches are possible to ensure that the interference of aperiodic tasks on periodic ones is bounded: 1) scheduling the aperiodic tasks with a lower priority ; 2) bounding the minimal inter-arrival time of aperiodic events, and studying the worst case scenario where they arrive at this worst rate ; 3) delegating the service of non periodic events to a mechanism which can be integrated into the analysis.

There are classes in the RTSJ to model handlers associated to asynchronous events. These handlers are schedulable objects which can be set either with AperiodicParameters or with SporadicParameters. The latter enables the event to be integrated into the feasibility analysis process as a stand alone task, as if it were arriving at its maximal rate.

For the third approach, the ProssessingGroupParameters class is proposed. It enables several schedulable objects to share release parameters, such as a mutual CPU time periodic budget. Unfortunately, it will not support any aperiodic task server policy nor any other advanced mechanism to handle aperiodic events. Moreover, as pointed out in [START_REF] Burns | Processing group parameters in the real-time specification for java[END_REF], this is far too permissive and does not provide appropriate schedulability analysis techniques.

Therefore, if the sporadic approach is not possible or too pessimistic, the only remaining solution with RTSJ is to schedule the task in the background.

In [START_REF] Masson | The design and implementation of real-time event-based applications with RTSJ[END_REF] we began to address the problem of event managing with an API proposition to write task servers. We continued this work and developed an approximate slack stealer compatible with the task servers model in [START_REF] Masson | Slack time evaluation with RTSJ[END_REF].

In this paper, we propose to generalize our task server model into an event manager model. We want to set up a homogeneous event manager framework and propose modifications to the specification in order to better include this framework. What we propose exactly is this: to modify the RTSJ feasibility analysis approach and to add methods to the Scheduler class for monitoring tasks execution and inserting treatments before and after each schedulable object execution.

The remainder of the paper will be structured as follow: we shall discuss in Section 2 which programming level is suitable to write event handling mechanisms. We present a task server framework and a slack stealer for RTSJ respectively in Sections 3 and 4. We also discuss modifications on the specification in order to better integrate them. Some results are commented on in Section 5. We expose the limitations of the feasibility analysis model of the RTSJ and propose to extend it in Section 6. Finally we conclude in Section 7 where we recapitulate the extensions which we propose for the RTSJ.

PROGRAMMING EVENT HANDLING

The aim of a scheduler is to schedule tasks. It is responsible for handling the execution of pending tasks by following The specification contains an abstract class, Scheduler, the aim of which is to model the system scheduler. The scheduler class can be overridden and a multiplicity of implementations can be proposed. However, if we take a look at the implementations of this class in available RTJVMs, we find that scheduler implementations are provided by native methods, which use the underlying operating system scheduler. This means that the use of a scheduling policy which is not provided by the system your virtual machine is running on, is impossible. Besides, the RTSJ only imposes a preemptive fixed priority scheduler to each RTSJ-compliant JVM.

Thus if one wants to design a portable mechanism for event handling or another advanced algorithm to deal with specific tasks in a given system, one has to provide it in user land, above the underlying fixed priority scheduler.

Several questions need to be answered here: how and when can we control the system without being the scheduler ? How can we ensure the respect of timing constraints without using underlying system specific data ? In the following subsections, we will look at solutions to these problems.

Carrying Out Computations

In order to control the system, the exact implementation details of the scheduler must be known and the highest priority task must be used to avoid interference from other tasks. Unfortunately this interferes with the business tasks. The mechanism has to be integrated into the feasibility analysis process, and must be periodic, or have known activation behavior, so that its interference with other tasks can be easily confined.

The solution we propose consists of performing necessary computations just before the beginning of the periodic tasks, and just after their completion. When doing this, if the cost value of these computations is known, then this value can be added to the periodic tasks worst case execution cost, and then the usual feasibility analysis can be performed. This solution is easily integrable with the RTSJ. Indeed, the periodic behavior is obtained with the specification by writing the code in a loop and by calling the special method waitForNextPeriod() at the end of this loop. This method call is blocking and the thread is activated automatically by the virtual machine at its next activation. Thus we just have to extend RealtimeThread or other Schedulable object and override the waitForNextPeriod() method in the way shown in Figure 1. Then it only remains to write the two methods computeBeforePeriodic() and computeAfterPeriodic().

Although this design may seem to be just a patch, it is extremely useful. For example, in [START_REF] Masson | Fault tolerance with real-time java[END_REF] we used it to set up temporal fault detectors, and as we will see in Section 4 it enables computations to be carried out to estimate the available slack time in the system.

In a system composed only of periodic tasks, it can be used to find out the amount of time a task has really consumed. A task stops its execution only when it has completed its periodic activation or when a higher priority task begins its own execution. Thus if the elapsed time is measured between the last time an entry is made into one of the two proposed methods, the consumed CPU time for each task can be kept up-to-date. It supposes that the execution stack is kept in order to know which is the executing task between the two calls.

This behaviour is missing from the RTSJ and has been proposed by the JSR-282: "7. Add a method to Schedulable and processing group parameters, that will return the elapsed CPU time for that schedulable object (if the implementation supports CPU time)".

With our patch we can obtain the elapsed CPU time even if the implementation cannot support the method which provides that elapsed CPU time. A drawback is that the cost must be paid both in memory and CPU usage.

The proposed MyRealtimeThread class (Figure 1) requires that all the tasks in the system either extend or use it. If one uses both MyRealtimeThread and regular Schedulable objects, one can no longer deduce anything from the elapsed time since the last beginning or end of a MyRealtimeThread implemented task. Moreover, the patch becomes inefficient if AsyncEventHandlers are used to write periodic tasks, or if the tasks share resources, inducing priority inversions. So it is, in our opinion, a good idea to integrate this mechanism with the RTSJ. In order to do so, we propose to modify the Scheduler abstract class by adding abstract methods automatically called before tasks instances start and after their completion, for all schedulable objects. Appropriate methods can also be called for other context switches due to monitor control algorithms or tasks which suspend themselves.

Then we also propose to add a CPU time monitor to the Scheduler which uses this mechanism. This monitor can be turned off if it is not needed or if the cost enforcement is available on the targeted platform. If it is turned on, a method RelativeTime getConsumnedCPUTime(Schedulable s) should return the total amount of time the Schedulable s has consumed before its last activation. Another method getTotalCPUTime(Schedulable s) can return the total CPU time consumed by the schedulable. If priority inversion due to resource sharing has occurred, the blocking time values can be incorporated or return separately.

As this mechanism has a non negligible cost, it has to be integrated into the feasibility analysis. In order to do so in a transparent way, a method getContextSwitchCost() should be added in the Scheduler class.

All the extension propositions we make are summed up in Section 7.

Ensuring Timing Constraints

Let us suppose here that an event management algorithm allows us to start an AsyncEventHandler h at the priority p, assuming that the worst case execution time of h is C h .

We need to ensure that h does not exceed this worst case execution time, since the algorithm relies on this parameter to allow us to start h at the priority p.

Cost enforcement is an optional behavior in the specification, so we do not want to use it. The only remaining solution is to set up a timer which suspends the task if it has not completed its execution at the expiration. But the consequence is that we need to cancel the timer each time the task is preempted, and resume it each time the task is resumed.

We can do that with the patch proposed in Section 2.1, but the overhead of these timers' management would be linear with the number of pending tasks. Such a cost can neither be bounded nor integrated in the feasibility analysis since the number of aperiodic tasks cannot be controlled. This induces a strong limitation in the user land approach to managing non periodic events: we have to schedule them at the highest available priority. When doing that, we ensure that we need only one control timer at the same time and this timer is set up once and for all.

The other limitation is that if a thread can be suspended through the AsynchronouslyInterruptedException mechanism, it is not possible to resume it. This means that we need to adapt existing algorithms available in real-time scheduling literature. Indeed, available resources (server remaining capacity or slack) can exist but may be lower than the worst case execution cost of any pending aperiodic events. This leads to situations where some resources available in the general context of real-time systems are not expendable because of the use of the RTSJ. To limit this side effect, we can take action with the queue policy in the event manager.

Moreover, for the same reason, a task with a very high cost can never be carried out. To avoid this drawback, we imagined a BS-duplication policy which consists of simultaneously scheduling each aperiodic task in background and enqueuing it in the event manager. The first replication which completes its execution interrupts the other.

TASK SERVERS IMPLEMENTATION

Task servers which were first introduced in 1987 [START_REF] Lehoczky | Enhanced aperiodic responsiveness in hard real-time environments[END_REF], are special tasks in the system which are in charge of servicing They are characterized by a capacity and a policy to recover it. The execution of the aperiodic traffic cannot interfere with the system more than a server using its full capacity. The main advantage is that these special tasks can be integrated into the feasibility analysis (with or without modifications to it).

Many task server algorithms have been proposed in the two previous decades [START_REF] Strosnider | The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments[END_REF][START_REF] Sprunt | Aperiodic task scheduling for hard real-time systems[END_REF]. However, the RTSJ does not support any particular task server policy. It proposes two classes AsyncEvent and AsyncEventHandler to model respectively an asynchronous event and its handler. The only way to include the handler in the feasibility process is to consider it as an independent task, and that implies knowing its worst-case occurring frequency. Even if the maximum value of the frequency is known, it often represents a very pessimistic approximation.

The RTSJ also provides the class ProcessingGroupParameters (PGP), which allows programmers to assign resources to a group of tasks. A PGP object is like a ReleaseParameters which is shared between several tasks. More specifically, PGP has a cost field which defines a time budget for its associated tasks set. This budget is replenished periodically, since PGP has also a field period. This mechanism provides a way to set up a task server at a logical level. Unfortunately it does not take into account any server policy. Moreover, as pointed out in [START_REF] Burns | Processing group parameters in the real-time specification for java[END_REF], it is far too permissive and it does not provide appropriate schedulability analysis techniques. Finally, as cost enforcement is an optional feature for a RTSJ-compliant virtual Java machine, PGP may not be available. This is the case with the Timesys Reference Implementation of the specification (RI).

We proposed a set of classes to write task servers in [START_REF] Masson | The design and implementation of real-time event-based applications with RTSJ[END_REF].

This contribution is summed up by Figure 2. It is composed of six new classes: ServableAsyncEvent (SAE), Servable-AsyncEventHandler (SAEH), TaskServer, PollingServer and DeferrableServer. The notion of "Servable" object is similar to the "Schedulable" one, except that if a Schedulable is executed by a scheduler, whereas a Servable is handled by a server. Thus, the Schedulable object is the server. A ServableAsyncEvent extends the regular AsyncEvent.

It models an asynchronous event where its handlers can be either asynchronous event handlers, i.e. regular Schedulable objects, or ServableAsyncEventHandlers: shells containing logic that task servers can execute.

Each ServableAsyncEventHandler has to be registered in one TaskServer. Then, when a ServableAsyncEvent is fired, each of its regular AsyncEventHandlers is set ready for execution. For each of its servable handlers the servable-EventReleased(SAEH h) method of its associated server is invoked.

After this the server is notified and can, for example, enqueue the handler. This allows developers to write different behaviours for different task server policies: the handlers can be scheduled in a FIFO order, or any other desired order, depending on the implemented policy. Finally TaskServer inherits from Scheduler in order to enable the use of the feasibility methods for aperiodic tasks inside the server.

Polling and Deferrable Server Modifications

As a demonstration of the efficiency of this design, we implement two well known service policies: the Polling Server and the Deferrable Server, taking into account the limitations described in Section 2 to modify these policies.

The servers have to run at the highest priority, which prohibits the use of several servers. As we cannot resume the threads, we start a handler only if the remaining capacity in the server is equal to or greater than its worst case execution time.

This leads to situations where the server still has capacity, and has tasks to execute, but remains inactive. In the case of the deferrable server, the loss in performance is limited, as the server has bandwidth conservation, but the polling server loses its remaining capacity when it becomes inactive.

To limit the loss of performances, we investigated a lot of queue policies. We tried a simple FIFO, a LIFO, scheduling first the task with the highest cost (HCF) and finally the one with the lower (LCF). The policy which perform better in all the cases is the LCF policy. Moreover, to ensure that all task can be scheduled, we set up a policy we called "BS duplication" as explained in Section 2.2. Figure 3 show results of simulations we conducted to estimate the loss of performances. Surprisingly, with the impact of the BS duplication, the policies performances are quiet similar. We even have the modified DS policy which performs better than the preemptive one in some cases.

From an implementation point of view, there is no specific problem with the Polling Server. We use a delegation to a RealtimeThread set up with PeriodicParameters. Writing the code for the deferrable server was a little bit more tricky, since it can be activated at any moment. So we use a delegation to an AsyncEventHandler associated to a special AsyncEvent "wakeUp". This event is fired each time a ServableAsyncEventHandler is added to the waiting queue of aperiodic requests (i.e. each time a ServableAsyncEvent is fired). This handler is also associated to a PeriodicTimer in order to manage the capacity.

Despite the limitations and adaptations to the policies, the performances are much better than just executing aperiodic service as a background task. However, the extensive evaluation of performances is not the purpose of this paper.

Integrating Servers and Feasibility Analysis

Integrating the Polling Server in the feasibility analysis process is straightforward. Indeed, it is just a regular periodic task in the worst case (when it uses its full capacity). The general overhead of the mechanism can be deducted from the server capacity. We use a PeriodicParameters object in which the field cost is used for the capacity.

The Deferrable Server induces more difficulties. In fact, the feasibility analysis has to be modified because in the worst case, this server does not interfere like a regular pe- riodic task on the lower priority tasks. This is due to its ability to conserve its capacity when there is no traffic to the server. The counter example of a feasible system with a Polling Server but not feasible with a Deferrable Server is well known as the double hit effect. It is represented in Figure 4.

A sufficient and necessary condition for the feasibility is available and described in [START_REF] Ghazalie | Aperiodic servers in a deadline scheduling environment[END_REF]. However, with the current specification, the only way to change the feasibility analysis algorithm is to overrun the Scheduler class. From our point of view, this is not a coherent action if the scheduling policy is not modified, which is the case. We propose the creation of a new interface FeasibilityAnalyzer, which can be integrated into the scheduler as a field, and can be changed by a setter method call. This question will be further discussed in Section 6.

A SLACK STEALER FOR RTSJ

For the general problem of jointly scheduling hard realtime periodic tasks and soft real-time non periodic events, the best known solution for minimizing the soft tasks' response times whilst guaranteeing hard tasks deadlines is the use of a slack stealer, proposed in [START_REF] Lehoczky | An optimal algorithm for scheduling soft-aperiodic tasks fixed priority preemptive systems[END_REF] and [START_REF] Ian | On Exploiting Spare Capacity in Hard Real-Time Systems[END_REF]. An approximate algorithm, DASS, is also presented in [START_REF] Ian | On Exploiting Spare Capacity in Hard Real-Time Systems[END_REF]. We proposed in [START_REF] Masson | Slack time evaluation with RTSJ[END_REF] MASS, an algorithm to estimate the slack using data only updated when periodic tasks end or begin. This algorithm is more pessimistic than DASS but needs less computations, and only when tasks ends. The slack at the instant t is the total amount of time you can suspend all the tasks without inducing temporal faults (i.e. deadline misses).

We perform O(n) complexity operations each time a task ends, and this allows us to compute a lower limit on the available slack in constant time.

Implementing this algorithm with RTSJ is simple as it is designed to take into account RTSJ userland restrictions evoked in Section 2. Indeed, the evaluation relies on two pieces of data for each task kept up to date whenever a task begins and ends.

Estimating the Slack

We consider a process model of a mono processor system, Φ, made up of n periodic tasks, Π = {τ1, ..., τn} scheduled with fixed priorities. Each τi ∈ Π is a sequence of requests for execution characterized by the tuple τi = (Ci, Di, Ti, P i).

Where Ci is the worst case execution time of the request ; Di is its relative deadline; Ti its period and Pi its priority, 3 being the highest.

The system also has to serve an unbounded number p of aperiodic requests, Γ = {σ1, ..., σp}. A request σi ∈ Γ is characterized by a worst case execution time Ci.

Let S max i,t
denotes the slack at priority level i available at the instant t, i.e. the amount of time the processor will be idle for priority levels higher or equal to i between t and the next τi deadline. Then S max t , the available time at the highest priority at time t is the minimum over all the S max i,t . This quantity can increase only when a periodic task ends its periodic execution. So we propose to keep up-to-date for all task Si,t, a lower bound on S max i,t . St is computed each time a periodic task ends, and is assumed to have decreased by the elapsed time otherwise. So the Si,t values only have to be correct (i.e. lesser than or equal to S max i,t ) in such situations.

Si,t is described using two elements: firstly a lower bound on the maximum possible work at priority i regardless of lower priority processes, wi,t, secondly the effective hard real-time work we have to process at the instant t, ci(t).

Equation 1 recapitulates the operations needed to obtain a lower bound on the available slack at time t. These operations have an O(n) time complexity. ∀i, Si,t = wi,t -ci(t) St = min

i\τ i ∈Π Si,t (1)
Two pieces of data must be kept up-to-date for each periodic task: wi,t and ci(t). cj(t) = cj(t ′ ) -min(dtc, dtw)

(2)

∀j < i, wj,t = w j,t ′ -dtw wi,t = w i,t ′ + Ti -Ii ∀j > i, wj,t = w j,t ′ + dtw + Ci ci(t) = Ci (3)
If we note t the current time, t ′ the time of the last update of a value, dtc the elapsed time since the last update of a c k (x) value, dtw the elapsed time since the last operation on a w k (x) value, τi the task which begins or ends and τj the task which is executing just before t (if any), then Equation (2) indicates the operation which has to be performed at the beginning of the task τi and Equation (3) indicates the operations which have to be performed at the end of the task τi. Equation 3 still holds even if we allow resources sharing and priority inversions (we just have to replace Ci by Ci + Bi), but the operation described by equation 2 has also to be performed when a critical section is entered.

At the end of a τi periodic execution, the work available :

• is increased by Ti minus the interference from higher priority tasks activated during its next instance for τi;

• is decreased by dtw but increased by Ci for tasks with a lower priority;

• is decreased by dtw for tasks with a higher priority.

The interference, which we shall call Ii in Equation ( 3), can take two different values depending on the instance. The most accurate value can be found in a constant time complexity operation.

The operations needed when a task completes all have a time complexity linear in the number of tasks. Their cost can be bounded to the worst case execution cost Cep. Respectively, the operation needed when a periodic task begins has a constant time complexity and can be bounded to the worst case execution cost C bp . These values can be integrated into the feasibility analysis process. This integration is not harmonious with the current RTSJ. If we use the MyRealtimeThread class proposed in Figure 1, we have to increase the cost of each task by Cep + C bp . A more elegant way to proceed is to use additional methods in the Scheduler class to add the computation before and after all the Schedulable executions, and to add a new parameter to the Scheduler class which represents the context switch cost.

Using the Slack

A slack stealer can be viewed as a task server with a capacity which is always equal to the available slack. Thus when an aperiodic task arrives, the slack can be estimated in a constant time operation. After that, as with the task servers, multiple policies are possible.

We can add a new class SlackStealer to Figure 2. This class extends TaskServer. The slack stealer has to be activated aperiodically: when an aperiodic task is released while the queue is empty, and when the slack time is increased while the queue is not empty. So we can use the same mechanism we used for writing the code of the De-ferrableServer: The logic of the SlackStealerTaskServer class can be delegated to an AsyncEventHandler associated to a special AsyncEvent.

However, the slack stealer approach is not really similar to that of the server. The server is similar to a reservation approach whilst the slack stealer uses the unused available resources. So we prefer to rename our class TaskServer in EventManager.

SOME RESULTS

Figure 5 exposes some simulation results with modified server and RTSJ compliant slack stealer algorithms. MASS designates the algorithm implementable with RTSJ using the slack approximation while ESS and DASS designate the same algorithm with respectively an exact knowledge of the available slack and a slack approximation obtained by DASS algorithm.

We compared a lot of queuing policies, and the best one consisted of first scheduling the task with the lowest cost. We named this policy LCF (Lower Cost First).

The use of the BS-duplication is noted "&BS". We measured the mean response time of aperiodic tasks with different aperiodic and periodic loads.

First, we generated groups of ten periodic task sets with utilization levels of 30, 50, 70 and 90%. The results presented are averages over a group of ten task sets.

We conduct the experiments with a variable number of periodic tasks from 2 to 100. The periods are randomly generated with an exponential distribution in the range [40-2560] time units. Then the costs are randomly generated with an exponential distribution in the range [1-period] and deadlines with an exponential distribution in the range [costperiod]. Priorities are assigned assuming a Deadline Monotonic Policy.

Non feasible systems are rejected, the utilization is computed and systems with an utilization level differing by less than 1% from that required are kept.

Then, we generate groups of ten aperiodic tasks sets with a range of utilization levels (plotted on the X-axis in the following graphs). Costs are randomly generated with an exponential distribution in the range [START_REF] Burns | Processing group parameters in the real-time specification for java[END_REF][START_REF] Ian | On Exploiting Spare Capacity in Hard Real-Time Systems[END_REF][START_REF] Ghazalie | Aperiodic servers in a deadline scheduling environment[END_REF][START_REF] Lehoczky | An optimal algorithm for scheduling soft-aperiodic tasks fixed priority preemptive systems[END_REF][START_REF] Lehoczky | Enhanced aperiodic responsiveness in hard real-time environments[END_REF][START_REF] Masson | Fault tolerance with real-time java[END_REF][START_REF] Masson | The design and implementation of real-time event-based applications with RTSJ[END_REF][START_REF] Masson | Slack time evaluation with RTSJ[END_REF][START_REF] Sprunt | Aperiodic task scheduling for hard real-time systems[END_REF][START_REF] Strosnider | The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments[END_REF][11][12][13][14][15][16] and arrival times are generated with a uniform distribution in the range . Our simulations end when all soft tasks have been served.

The figure presents the best policy for each algorithm (BS, MPS, MDS, MASS, DASS and ESS) on systems with Di < Ti for all periodic tasks. Equivalent results are obtained on systems with Di = Ti. For all load conditions, servers bring real improvement compared to BS. The DS offers better performances than the PS. MASS performs better than the DS, DASS better than MASS and ESS better than DASS. For systems with periodic loads of 30% and 50%, results obtained with MASS, DASS and ESS are quite similar. Considering the differences between these algorithms' time complexities (linear with very low constant, linear with a high constant and pseudo polynomial), this is a very satisfying result. However MASS performances degrade quickly than DASS ones when periodic load increases. Nevertheless MASS remains a really good implementable algorithm even for systems with a periodic load of 90%.

FEASIBILITY ANALYSIS DESIGN

The feasibility process in the RTSJ is not suitable for mixed task systems. Indeed, the problem is that the methods are part of the scheduler class and this has several disadvantages.

The choice of feasibility analysis (FA) algorithms depends on the type of application. A simple statistical condition can be suitable for a multimedia application. Here, a deadline miss can be acceptable, if the analysis ensures that after m periods, k instances of the task can be executed.

In other cases, a necessary but non sufficient condition on the feasibility can be acceptable. For example if a detection mechanism and a temporal fault gesture is set up at runtime, or if the worst case execution times are known to have been over-evaluated.

For other applications, a sufficient test is needed, a test which can be necessary or not.

However, the FA is highly dependent on the scheduling algorithm. So in our opinion, the feasibility analyzer has to be a separate object by itself, but must be integrated into the scheduler object as a parameter, which the developers can change according to the target application they are writing.

Of course, this is already possible with the current specification by overriding the Scheduler and changing the FA methods, but this is not really a coherent approach. Indeed, the FA does not have to affect the scheduling behavior, and changing the analysis algorithm should not mean changing the scheduler object since the task scheduled will remain the same.

So we propose the addition of an interface Feasibility-Analyzer in the RTSJ. A field of Scheduler can be typed with this interface, and all the methods relative to the FA delegated to it.

Then it is possible to change the default FA on demand. This interface should have the methods addToFeasibility(Schedulable s) and boolean isFeasible(). We propose two other interfaces extending FeasibilityAnalyzer: SufficientTest and NecessaryTest. Then we can set up a fourth interface SufficientAndNecessaryTest which extends the others two.

In this way, if a class can use any FA policy, it can just type its field FeasibilityAnalyzer, but all the other degrees of precision can be enforced just by the correct choice of the type.

We can easily write the class LoadCondition as an implementation of NecessaryTest. This class must compute the system load (for fixed priority scheduled systems : U = P Ci/Ti).

For the fixed priority preemptive case, which is the only scheduling policy imposed for an RTSJ compliant JVM, we can add the abstract class ResponseTimeAnalysis as an implementation of the interface SufficientAndNecessary-Test, and finally the class FixedPriorityRTAnalysis as its subclass.

Possible methods for this abstract class are RelativeTime computeLevelIBusyPeriod(int i) which computes the ilevel busy period and computeResponseTime(int i, int q) which computes the response time of the instance q of the task τi.

CONCLUSIONS

In this paper, we have shown how an aperiodic event traffic can be handled using the RTSJ implementation in a portable way. We have presented the necessary adaption of existing algorithms in order to take into account the constraints brought about by the use of the Java language. We have presented a set of modifications to the RTSJ Specification and a unified event management framework. This framework enables RTSJ programmers to write a simple and We now recapitulate the modifications and additions which we consider to be relevant in order to improve the specification. Then, the RTSJ extension proposed is the following:

• add void computeBefore(Runnable logic, Relative-Time cost) and void computeAfter(Runnable logic, RelativeTime cost) methods in Scheduler abstract class. With these methods the scheduler automatically adds logic parameter before or after each instance of periodic or non periodic tasks handled. The parameter cost is the logic worst case execution time;

• add the boolean field monitorCPUTime and the two methods RelativeTime getConsumedCPUTime(Schedulable s) and getTotalCPUTime(Schedulable s) to the class Scheduler, in order to allow the CPU time consumption monitoring when the underlying operating system does not directly provide this feature;

• add a contextSwitchCost field typed RelativeTime and its getter method to the Scheduler abstract class, in order to integrate the context switch cost, the logic added by the previously proposed methods and the optional CPU monitoring mechanism to the feasibility analysis;

• add new classes ServableAsyncEvent and Servable-AsyncEventHandler. The first extends the class Async-Event and models an event which can be associated both to regular schedulable handlers and special handlers associated to an event manager;

• add the new abstract class EventManager, and its implementations PollingServer, DeferrableServer, Sl-ackStealer. We can provide the Java code for these three classes;

• add the interfaces FeasibilityAnalyzer, Sufficient-Test, NecessaryTest and SufficientAndNecessary-Test;

• add the abstract class ResponseTimeAnalysis and its subclass FixedPriorityRTAnalysis;

• integrate these feasibility relative classes and interfaces into the Scheduler abstract class as a field and with setter/getter methods. Delegate the behaviors of existing feasibility analysis methods to this field.

Figure 6 recapitulates these propositions in a UML diagram.

In future work, we have to investigate on the interactions between the memory parameters and the feasibility analyzer object. We also have to clarify the behavior of the proposed CPU time user land module when resource sharing is allowed.

Figure 1 :

 1 Figure 1: WaitForNextPeriod() modifications

Figure 2 :

 2 Figure 2: Classes to implement the server policies

Figure 3 :

 3 Figure 3: Regular server policies VS modified ones

1 Figure 4 :

 14 Figure 4: Double hit effect

Figure 5 :

 5 Figure 5: RTSJ compliant Slack Stealer and Task servers algorithms

Figure 6 :

 6 Figure 6: Extensions to the RTSJ we propose

Acknowledgments

We want to thank Sian Cronin and Aurore Sibois for their valuable advices and English corrections.


Damien Masson
email: damien.masson@univ-mlv.fr

Serge Midonnet
email: serge.midonnet@univ-mlv.fr

Fault Tolerance with Real-Time Java

After having drawn up a state of the art on the theoretical feasibility of a system of periodic tasks scheduled by a preemptive algorithm at fixed priorities, we show in this article that temporal faults can occur all the same within a theoretically feasible system, that these faults can lead to a failure of the system and that we can use the data calculated during control of admission to install detectors of faults and to define a factor of tolerance. We show then the results obtained on a system of periodic tasks coded with Java Real-Time and carried out with the virtual machine jRate. These results show that the installation of the detectors and the tolerance to the faults makes an improvement of the behavior of the system in the presence of faults.

Introduction

Real-Time systems occupy an increasingly significant place in industry and are present in an increasing number of fields. Today, because of temporal constraints, real-time programmers have to use low-level programming languages like the assembler or the language C. They cannot benefit from the advantages of the Java language: a high level of abstraction (oriented object approach) and the independence from the execution platforms (portability). This led in 2001 to the Real-Time Specification for Java (RTSJ) [START_REF] Bollella | The Real-Time Specification for Java[END_REF]. This specification describes a set of classes and interfaces and defines the constraints imposed for real-time virtual machines (memory management, scheduling algorithms and synchronisation mechanisms). The work on this specification is still in progress, as attested by the publication in June 2005 of its version 1.0.1. There are also many RTSJ virtual machines. Some are commercialized as Jamaïca VM from AICAS society. Some others exist for research as RI which stand for reference implementation. The latter was made to prove the feasibility of real-time Java adventure. Eventually jRate [START_REF] Corsaro | Evaluating real-time java features and performance for real-time embedded systems[END_REF][START_REF] Corsaro | The design and performance of the jrate real-time java implementation[END_REF], an open source project based upon an extension of the GNU GCJ compiler or flex [START_REF] Francu | Real-time scheduling for java[END_REF] developed in MIT. Recently, Sun Microsystems themselves announced their own implementation of the specification called project Mackinac [START_REF]The Real-Time Java Platform[END_REF][START_REF] Bollella | Mackinac: Making hotspot(tm) realtime[END_REF].

If this specification offers to programmers methods to compute an admission control for real-time periodic tasks, the tested machines do not offer a valid implementation. We can easily show a non feasible set of tasks for which RI returns feasible, and we can see in the file PriorityScheduler.java that feasibility methods are not yet implemented in jRate.

So, to begin this work, we have drawn up a state of the art on the feasibility analysis issues for a fixed priority scheduled periodic task system. This study leads us to write the deficient methods of RI and missing ones in jRate. However, though these methods give us a theoretical feasibility of the task system, in practice faults can occur for many reasons. To take into account these faults, an approach usually met in the literature is to install overload detection and treatment mechanisms [START_REF] Locke | Best-effort decision-making for real-time scheduling[END_REF][START_REF] Koren | Rt-0138 -d-over : an optimal on-line scheduling algorithm for overloaded real-time systems[END_REF][START_REF] Buttazzo | Red: A robust earliest deadline scheduling algorithm[END_REF]. Our approach, in the other hand, consisted on using an admission control with fault detection and treatments mechanisms, in order to avoid any overload.

We start by presenting the admission control algorithm in Section 2. In Section 3 we define the temporal faults and we explain how we can detect them by overloading methods of the Real-time Specification for Java (RTSJ). Section 4 presents the various treatments of the faults we have established. We explain which mechanisms of measurement we 1-4244-0054-6/06/$20.00 ©2006 IEEE set up in Section 5 and have their results in Section 6. Finally we present in conclusion the prospects for work offered by these results.

Control of admission

The theory of scheduling applied to real-time systems have been largely studied over the past twenty years and many results were published [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard real time environment[END_REF][START_REF] Lehoczky | Fixed priority scheduling of periodic task sets with arbitrary deadline[END_REF][START_REF] Audsley | Hard Real-Time Scheduling: The Deadline Monotonic Approach[END_REF][START_REF] Bini | Rate monotonic analysis: The hyperbolic bound[END_REF]. We limited our study to a fixed priority pre-emptive scheduling algorithm because all the RTSJ implementations have to offer it at least. A task, denoted by τ i has a cost C i , a relative deadline D i , a period T i and a priority P i .

In this section, we present the results described by Liu and Layland in [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard real time environment[END_REF] and generalised by Lehoczky in [START_REF] Lehoczky | Fixed priority scheduling of periodic task sets with arbitrary deadline[END_REF] to the tasks with the deadline higher than the period.

Load test

The system load, denoted by U , can be calculated by:

U = N i=1 C i T i (1)
There are two possibilities:

• if U > 1, the system is not feasible,

• else the load condition is not enough to conclude.

Worst case response times computation

P i D i T i C i τ 1 20 6 6 3 τ 2 15 2 4 2

Table 1. System task data

The response time for a task job is the time interval between its activation and its termination. The worst case response time for a task is the response time of its longest job in the worst situation. In the particular situation where D i < T i , the worst situation is reached when all the tasks are activated simultaneously. As shown in table 1 and figure 1, this is not true in the general case. Consequently, the calculation of these worst case response times in the general case requires a thorough study.

Figure 2. Worst case response time computation of a task in a fixed priority preemptive system

Many works were carried out on the calculation of these response times. They led to the algorithm shown on Figure 2.

The algorithm is based on the following observations: a job activation can only be delayed by a job of a higher priority task or by the previous jobs of the same task. Furthermore a job can only be preempted by a higher priority task job. A recurrence formula enables us to compute the response time of each task job from the response time of the previous job. We just have to iterate this computation over all the jobs until we find a job with a response time smaller than its period. In that case, there is no influence of the job on the following jobs: the worst case response time is then the maximum response time computed during the iterations.

Implementation

We offer to developers a new package called javax.realtime.extended. This package contains the class RealtimeThreadExtended which extends RealtimeThread.

The methods concerned by the job control are addToFeasibility() and removeFromFeasibility() and are overloaded to delegate the work to one of our classes called FeasibilityAnalysis. This class implements the algorithm of Figure 2.

Fault detection

A system failure occurs when one (or many) task has a job which missed its deadline (D i ). If we always perform an admission control before starting a task system, it should never have any system failure. However, algorithms shown up on the previous section lead on the hypothesis of the exactitude and the respect of tasks parameters. In particular, the task jobs have always to respect their costs (C i ). Since this cost is often obtained by a statistical work, it is not reliable. So it is possible a task job takes a little bit more than its cost, either because it was underestimated, or because of an external event with the system. This is called a fault. A fault can lead to the failure of the faulty task or the failure of a task with a smaller priority.

The detection of a cost overrun is a difficult problem, because it implies being able to know at any time how much CPU resource a job has already consumed. However, the worst case response time computation carried out during the admission control gives us for each task job a date, depending on its activation, before which it has to be finished.

A worst case response time overrun implies a cost overrun.

All the critical instants to watch depend on the jobs activations. This is why a detector can be a periodic task, with a period equal to the task period and with an offset equal to the task worst case response time. This periodic approach enables us to avoid the creation of an instance of a detector for each job. This decreases the cost overrun induced in the system by our detectors since there is only need for one real-time task for each thread.

Implementation

In RealtimeThreadExtended, we overload the method start(). Our method starts a periodic detector with an offset equal to the worst case response time just after having called the method start() of the super-class. The detector is an instance of PeriodicTimer which checks the states of a boolean value and a job counter. This job counter was added to our real-time thread class. If the job is not finished when the timer is called, a fault treatment can be started. The states of the boolean value and the counter are up-to-date in overloading the method waitForNextPeriod() which is called at the end of each periodic job and which is blocking until the next job activation. Our method becomes: public boolean waitForNextPeriod(){ computeAfterPeriodic(); boolean returnValue = super.waitForNextPeriod(); computeBeforePeriodic(); return returnValue; } With this approach, we are able to add actions just before and just after each job.

It implies that the method waitForNextPeriod() has to be called before the first job, which is often the case in order to minimise the influence of the method start() call.

Treatments

We are now able to detect some kinds of faults in a real-time system. How can we treat these faults ? First, we have to look at the consequences of a worst case response time overrun:

• the system is still feasible, there are no more consequences than a little offset on the worst case response times of the tasks with a lower priority,

• the faulty task misses its deadline and probably provokes the failure of tasks with lower priority,

• the faulty task ends before its deadline but the offset leads to failure for some tasks with lower priority.

Our goal is to prevent that the faulty tasks with a strong priority cause the failure of non-faulty tasks with a lower priority. To do so, we considered three treatments presented in the following subsections. We compare these treatments and we measure the improvement of the system behavior in a practical way on an example of three tasks in Section 6.

Instantaneous stop of the faulty tasks

The first idea of treatment consists in simply stopping the faulty tasks. This approach is very pessimistic, because making a fault can have no consequence on the system feasibility.

Let us note in addition that, in Java, it is not possible to stop a thread brutally. The theoretical solution would consist in lowering the priority of the task so that this one can be preempted, but this possibility is not yet implemented with jRate. For the needs of our analysis, we thus added a boolean field in the class RealtimeThreadExtended which is checked after each instruction of the loop constituting the periodic treatment. If this boolean gets true, then the loop is broken and the thread is stopped. That causes an annoying side effect: in the method run(), the thread must check the state of the boolean, and thus calls the method RealtimeThread.currentRealtimeThread(), the cost of which is not bounded. Consequently, the task will regularly make small cost overruns, about a few milliseconds. These cost overruns remaining lower than the precision of our detectors, that does not obstruct our analysis.

Stop after an allowance factor granted to the task

In order to have a less pessimistic approach, and to make it possible for the faulty tasks to continue as long as they can without obstructing the lower priority tasks, we have to calculate what we will call the allowance of the system, i.e. the additional cost we can grant to each task while keeping a theoretically feasible system.

To compute this tolerance, we carry out a binary search of the maximum value which can be added to the costs of all the tasks so that the system remains feasible (within the meaning of the analysis described in the previous section).

During this computation, we also compute new worst case response times which take into account the allowance. The tasks will now be stopped after these new worst case response times.

Stop after an allowance factor granted to the system

The treatment previously described considers that all the tasks have the same probabilities to make faults. The free time in the system is equitably distributed between all the tasks.

In the last treatment we implemented we consider that the higher the task priority is, the more it has the right to make a fault: this time, a task is stopped after a worst case response time overrun equal to the maximum free time available in the system. This allowance is obtained by seeking the maximum value which can be added to each task cost.

If the first faulty task finishes before having consumed all its allowance, the remainder is allocated to the other faulty tasks. A task allowance is obtained looking for the maximum cost overrun this task can do and substracting the more priority tasks overrun.

Measurements

In order to have measurements, we developed various tools. The first one enables us to parse a file which describes the tasks in the system. It builds and runs the tasks automatically. During the system execution, many data are collected. A second tool provides a chart of these data in the form of a time series chart.

The data collected, which are the key dates in the system life, are:

• the beginning of a job (the moment when the method computeBeforePeriodic() is called),

• the end of a job (the moment when the method computeAfterPeriodic() is called),

• the release of a detector.

In order to have a maximum precision, we use for these measurements an Intel processors characteristic: these processors have an instruction RDTSC (ReaD Time-Stamp Counter) providing the number of cycles carried out since the start-up of the system.

We thus wrote a library in Java native interface (JNI) allowing us to exploit this instruction, in order to obtain durations with a nanosecond precision.

We write these times in StringBuffer fields in order not to slow down the system with in-out operations. At the end of the execution of the system, these fields are written in a log file which can then be interpreted by our tool of time series chart.

Figures presented in Section 6 were obtained thanks to these tools, and thus are experimental results obtained on true Real-time Java systems of tasks, and not the awaited theoretical behaviors.

Results

We present in this section the results obtained on the system of tasks described in table 2. A cost overrun was voluntarily added for the priority task, which represents the most unfavourable case. We will compare the time series charts obtained in the following cases:

• no detection mechanism,

• active detectors, no fault treatment,

• active detectors, immediate stop of faulty tasks,

• active detectors, allowance granted equitably to all tasks,

• active detectors, allowance granted totally for the first faulty task.

P i T i D i C i W CRT i A i τ 1

Table 2. Tested tasks system

Figures from 3 to 7 are obtained with the tool that we developed, and present the behavior of the system during the fifth job of task τ 1 , which coincides with the activation of a job of τ 2 and τ 3 .

On these figures ↑ represents the periods and ↓ the deadlines. The materializes the detectors, and > indicates the worst case response times.

For our tests, we used the RTSJ jRate compiler because it is the only one among the tested virtual machines (RI, JamaïcaVM, ...) to have a good implementation of some essential aspects for our work, such as the signature of the method RealtimeThread.waitForNextPeriod(). We used a 2 GHz processor INTEL Pentium 4 machine with 500 MB of memory and a real-time kernel Timesys 2.4.18timesys-4.0.243.

Execution without detection

Figure 3. Execution without detection

Figure 3 shows us that task τ 1 makes a temporal fault at moment 1020m. It ends before its deadline, just as task τ 2 but task τ 3 misses its deadline. It is the case we wish to avoid. The execution presented in Figure 4 is similar to the one presented on Figure 3. One can notice that the detectors have a small delay. This delay cannot exceed ten milliseconds. This is due to the implementation of the PeriodicTimer in jRate: if the value given for the first release is not a multiple of ten, the precision is not good. We thus voluntarily round the release values of the detectors. This is why the detector of task τ 1 has a 30 -29 = 1 millisecond delay, that of τ 2 60 -58 = 2 milliseconds and that of τ 3 90 -87 = 3 milliseconds, which can be checked on the diagram.

Execution with detection, without treatments

The overrun generated in the system by the presence of the detection mechnism is that of a pre-emption, in addition to an unbounded value which corresponds to the boolean testing/test, as explained in Section 4.1. One can estimate this overrun to be inferior to the underlying accuracy of the real-time machine, hence to be negligible. Yet, one has to bear in mind that the more tasks in the system, the more sensors, hence, the higher the influence of this overrun on its execution. In the execution presented on Figure 5, the tasks are stopped as soon as they make faults. One can notice that the only task to miss its deadline is task τ 1 . However after the end of the execution of task τ 3 , the processor is free, and there remains time before its expiry. We can then think that task τ 1 could have time to finish, or at least to be carried out at greater length without causing the failure of τ 2 and/or τ 3 . Task worst case response time with cost overruns

Instantaneous stop of the faulty tasks

Allowance granted equitably to all tasks

τ 1 W CRT 1 + A 1 = W CRT 1 + 11 τ 2 W CRT 2 + A 1 + A 2 = W CRT 2 + 22 τ 2 W CRT 3 + A 1 + A 2 + A 3 = W CRT 3 + 33

Table 3. Worst case response time with cost overruns

Table 3 gives these new worst case response times. We note that only task τ 1 is stopped, and that it had more time to be carried out than in the previous case. However, we also notice that there remains unused CPU time, because tasks τ 2 and τ 3 did not consume their allowance, since they did not make cost overruns. Figure 7 corresponds to the last treatment considered: all the system time available in the worst execution case, that is to say thirty three milliseconds, is granted to the first faulty task. If this task does not consume all this allowance, and if another task makes a fault, it will benefit of what remains. Task τ 1 is thus stopped thirty-three milliseconds after its worst case response time and as neither τ 2 nor τ 3 make fault, they both finish just before their deadlines.

Allowance granted totally to the first faulty task

Conclusions and future works

The study of the theoretical results of the analysis of feasibility of a system enabled us to provide a correct establishment of the methods specified by the standard RTSJ for control of admission, which we could concretely check on the machine jRate.

We saw that theoretical feasibility is based on data such as the cost of the tasks which can possibly be exceeded during a real execution because of external factors, causing faults within the tasks system.

Thanks to the study of the worst case response times, we could define a type of fault whose detection does not require a complete monitoring of the CPU usage. We deduced a mechanism of detection which we coded and tested.

Finally we showed that the theoretical study made it possible to obtain a factor of allowance which maximizes the execution time of a task before its fault causes a failure of the system. However, our study considers a rather static system, in which all the tasks are known before launching, making possible to set up expensive algorithms in time to compute the response times and the allowance of the system.

Our objective in the continuation of this work will be to reach the same results in a more dynamic system where tasks can be added or removed "in real-time" by adapting the behavior of our detectors.

Moreover, if the cost of a task can be underestimated, it is also possible to overestimate it. Consequently, we can consider to dynamically study the system in order to detect these costs under-run and to reassign resources for faulty tasks.

Besides, we have considered neither the issues related to precedence constraints nor the ones deriving from the share of resources among the various tasks of the system. In the latter case, it would be advisable to study the influence of tolerance on the determination of the blocking time (b i ).

Another main line of our research will consist in studying the faults detection and tolerance in the case of aperiodic tasks.

Figure 1 .

 1 Figure 1. Response times

Figure 4 .

 4 Figure 4. Execution with detection, without treatments

Figure 5 .

 5 Figure 5. Execution without allowance

Figure 6 .Figure 6

 66 Figure 6. Allowance granted equitably to all tasks

Figure 7 .

 7 Figure 7. Allowance granted totally to the first faulty task

[Return the worst case response time in nanosecondes] Function WCResponseTime( S : Schedulable) : long integer Rq : long integer Rmax : long integer ← 0 q : integer ← 0 Rtmp : long integer While ( true) do Rq

← 0 Rtmp ← S.cost * (q + 1) While (Rq = Rtmp) do HP(S) :

Set of Schedulables with higher or equal priority than S pri- ority

	l	Rq S j .period	m	* Sj .cost
	done
	done
	Rq ← Rtmp
	If (Rmax < Rq -q * S.period) then
	Rmax ← Rq -q * S.period
	end If
	If (Rq ≤ (q + 1) * S.period) then
	break;
	end If
	q ← q + 1

Rq ← Rtmp Rtmp ← S.cost * (q + 1) For all Sj in HP(S) do Rtmp ← Rtmp +

done return Rmax End


Guillaume Blin
email: gblin@univ-mlv.fr

Eric Blais
email: eblais@mcb.mcgill.ca

Pierre Guillon
email: pguillon@univ-mlv.fr

Mathieu Blanchette
email: blanchem@mcb.mcgill.ca

Nadia El-Mabrouk

Inferring gene orders from gene maps using the breakpoint distance

Preliminary to most comparative genomics studies is the annotation of chromosomes as ordered sequences of genes. Unfortunately, different genetic mapping techniques usually give rise to different maps with unequal gene content, and often containing sets of unordered neighboring genes. Only partial orders can thus be obtained from combining such maps. However, once a total order O is known for a given genome, it can be used as a reference to order genes of a closely related species characterized by a partial order P . In this paper, the problem is to find a linearization of P that is as close as possible to O in term of the breakpoint distance. We first prove an NP-complete complexity result for this problem. We then give a dynamic programming algorithm whose running time is exponential for general partial orders, but polynomial when the partial order is derived from a bounded number of genetic maps. A time-efficient greedy heuristic is then given for the general case, with a performance higher than 90% on simulated data. Applications to the analysis of grass genomes are presented.

Introduction

Despite the increase in the number of sequencing projects, the choice of candidates for complete genome sequencing is usually limited to a few model organisms and species with major economical impact. For example, the rice genome is the only crop genome that has been completely sequenced. Other grasses of major agricultural importance such as maize and wheat are unlikely to be sequenced in the short term, due to their large size and highly repetitive composition. In this case, all we have are partial maps produced by recombination analysis, physical imaging and other mapping techniques that are inevitably missing some genes (or other markers) and fail to resolve the ordering of some sets of neighboring genes. Only partial orders can thus be obtained from combining such maps. The question is then to find an appropriate order for the unresolved sets of genes. This is important not only for genome annotation, but also for the study of evolutionary relationships between species. Once total orders have been identified, the classical genome rearrangement approaches can be used to infer divergence histories in terms of global mutations such as reversals [START_REF] Bergeron | Reversal distance without hurdles and fortresses[END_REF][START_REF] Hannenhalli | Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals)[END_REF][START_REF] Pevzner | Human and mouse genomic sequences reveal extensive breakpoint reuse in mammalian evolution[END_REF].

In a recent study [START_REF] Sankoff | Reversals of fortune[END_REF][START_REF] Zheng | Reversal distance for partially ordered genomes[END_REF], Sankoff et. al. generalized the rearrangement by reversal problem to handle two partial orders. The idea was to resolve the partial orders into two total orders having the minimal reversal distance with respect to each other. The problem has been conjectured NP-hard, and a branch-and-bound algorithm has been developed for this purpose. The difficulty of this approach is partly due to the fact that both compared genomes have partially resolved gene orders. However, once a total order is known for a given genome, it can be used as a reference to order markers of closely related species. For example, as the grass genomes maintain a high level of conserved synteny [START_REF] Keller | Colinearity and gene density in grass genomes[END_REF][START_REF] Gale | Comparative genetics in the grasses[END_REF], maps of the completely sequenced rice genome can be used to deduce an order of markers in other grass genomes such as maize.

In this paper, given a reference genome characterized by a total order O and a related genome characterized by a partial order P , the problem is to find a total order coherent with P minimizing the breakpoint distance with respect to O. The underlying criterion is a parsimony one assuming a minimum number of genomic rearrangements. After introducing the basic concepts in Section 2, we show in Section 3 that the considered problem is NP-complete. We then give, in Section 4, two dynamic programming algorithms. First is an algorithm that solves exactly the problem on arbitrary partial orders, and whose worst-case running time is exponential in the number of genes. However, when the partial order considered is the intersection of a bounded number of genetic maps of bounded width, the algorithm runs in polynomial time. We then present a fast and accurate heuristic for the general problem in Section 5. We finally report results on simulated data, and applications to grass genetic maps in Section 6.

A graph representation of gene maps

Hereafter, we refer to elementary units of a map as genes, although they could in reality be any kind of markers. Moreover, as the transcriptional orientation of genes is usually missing from genetic maps, we consider unsigned genes.

A genetic map is represented as an ordered sequence of gene subsets or blocks B 1 , B 2 , . . . , B q , where for each 1 ≤ i ≤ q, genes belonging to block B i are incomparable among themselves, but precede those in blocks B i+1 , . . . , B q and succeed those in blocks B 1 , . . . , B i-1 . For example, in Figure 1.a, {4, 5} is a block, meaning that genes 4 and 5 are assigned to the same position, possibly due to lack of recombination between them. A genetic map is thus a partial order of genes.

Maps M 1 , . . . , M m obtained from various protocols can be combined to form a more complex partial order P on the union set of genes of all maps as follows: a gene a precedes a gene b in P if there exists a map M i where a precedes b. However, combining maps can be a problem in itself, due to possible inconsistencies, which would create precedence cycles (e.g. a precedes b in M 1 but b precedes a in M 2 ). Breaking cycles can be done in different ways, the parsimo-nious method consisting in eliminating a minimum number of precedence rules. Another potential problem is the presence of multiple loci (markers that are assigned to different positions in the same map). These issues have been considered in previous studies [START_REF] Yap | A graph-theoretic approach to comparing and integrating genetic, physical and sequence-based maps[END_REF][START_REF] Zheng | Reversal distance for partially ordered genomes[END_REF][START_REF] Sankoff | Reversals of fortune[END_REF], and a software is available for combining genetic maps [START_REF] Jackson | Consensus genetic maps: a graph theory approach[END_REF]. In this paper, we assume that the partial order P is already known. As proposed in previous studies [START_REF] Yap | A graph-theoretic approach to comparing and integrating genetic, physical and sequence-based maps[END_REF][START_REF] Zheng | Reversal distance for partially ordered genomes[END_REF], we represent such a partial order P as a directed acyclic graph (or DAG) (V P , E P ), where the vertex set V P represents the set of genes along the chromosome and the edge set E P represents the available order information (Figure 1). We consider a minimum set of edges, in the sense that any edge of E P can not be deduced by transitivity from other edges. In particular, a total order of genes is represented by a DAG such that each edge connects a pair of consecutive genes.

Let P be a partial order represented by a DAG (V P , E P ). We say that a vertex a is P -adjacent to a vertex b and write a < P b iff there is an edge in E P from a to b. We say that a precedes b in P and write a P b iff there is a path from a to b. We say that vertices a and b are incomparable if neither a P b nor b P a, and denote this by a ∼ P b. A linearization of P is a total order O on the same set of genes, such that a P b ⇒ a O b.

Given a partial order P and a total order O, our goal is to find a linearization O of P , in such a way that O is as "similar" as possible to O. The distance measure used here is the number bkpts(O, O ) of breakpoints between O and O , where a breakpoint is a pair of consecutive vertices (a, b) of O that are not consecutive in O (a < O b but a ≮ O b). Equivalently, we may try to maximize the number of O-adjacencies of O , which is defined as the number of pairs of consecutive genes in O that are also consecutive in O (Figure 1.d). Formally:

Minimum-Breakpoint Linearization (MBL) problem

Given: A partial order P and a total order O on the set of genes {1, 2, . . . , n}, Find: A linearization of P into a total order O so that bkpts(O, O ) is minimized.

Without loss of generality, we assume from now on that O is the identity permutation (1, 2, . . . , n), that is i < O j ⇔ j = i + 1.

Hardness results

In this section, we prove that the decision version of the MBL problem is NPcomplete: given a complete order O and a partial order P defined on the same set of genes and an integer k , can one find a linearization O of P such that bkpts(O, O ) ≤ k ?

We propose a reduction from the NP-complete problem Maximum Independent Set [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]: given a graph G = (V, E) and an integer k, can one find an independent set of vertices of G -i.e. a set V ⊆ V such that no two vertices of V are connected by an edge in E -of cardinality greater than or equal to k ?

We initially note that the MBL problem is in NP since given a complete order O and a linearization O of P , one can compute the number of breakpoints in linear time. In order to prove that the MBL problem is NP-complete, we show that from any instance of Maximum Independent Set with a parameter k, we are able to construct -in polynomial time -an instance of the MBL problem such that k depends on k. We detail this construction hereafter.

For convenience, we define a reduction from a slightly different set of instances for the Maximum Independent Set problem: connected graphs. This can be done w.l.o.g. since the problem is still NP-complete in that case. Let G = (V, E) be a connected graph of n vertices. We define the complete and the partial orders O and P of the MBL problem as follows. The complete order O is defined as a string O = δ α 1 β 1 γ 1 α 2 β 2 γ 2 . . . α n β n γ n , and the partial order P as a DAG P = (V P , E P ) with

V P = {δ, α 1 , α 2 . . . α n , β 1 , β 2 . . . β n , γ 1 , γ 2 , . . . γ n , } and E P = {(δ, γ 1 )} ∪ {(γ i , γ i+1 )|1 ≤ i < n} ∪ {(γ n , α i ), (γ n , β i )| 1 ≤ i ≤ n} ∪ {(β i , α j ), (β j , α i )|∀(v i , v j ) ∈ E} ∪ {(α i , ), (β i , )|1 ≤ i ≤ n}.
In order to complete the instance of the MBL problem, we define k = (3n + 1) -k. In the following, we will refer to any such construction as a MBLconstruction.

First, let us present some interesting properties of any instance of Minimum-Breakpoint Linearization problem obtained by a MBL-construction. Then, we will use those properties to prove that the Minimum-Breakpoint Linearization problem is NP-complete. An illustration of a MBL-construction of a graph G of 6 vertices is illustrated in Figure 2. Lemma 1. Let G = (V, E) be a graph and P = (V P , E P ) be a partial order obtained from G by a MBL-construction. There exists no linearization O of P where both α i < O β i and α j < O β j , for any α i , α j , β i , β j of V P such that

(v i , v j ) ∈ E.
Proof. By contradiction, let us assume that there exists such a linearization O where α i < O β i and α j < O β j . Since (v i , v j ) ∈ E, we have (β i , α j ) ∈ E P and (β j , α i ) ∈ E P . Therefore, in any linearization of P -and consequently O -β i O α j and β j O α i -which leads, by transitivity, to β i O α i ; a contradiction. Lemma 2. Let G = (V, E) be a graph of n vertices, O and P = (V P , E P ) be respectively a complete and a partial order obtained from G by a MBL-construction. Given any linearization O of P , bkpts(O, O ) = (3n+1)-k where k is the number of couples

(α i , β i ) such that α i < O β i . Proof. By construction, in O, (i) δ < O α 1 < O β 1 < O γ 1 , (ii) ∀1 < i ≤ n, γ i-1 < O α i < O β i < O γ i and (iii) γ n < O . In any linearization O of P , (i) δ < O γ 1 , (ii) ∀1 < i ≤ n, γ i-1 < O γ i and (iii) either α i < O or β i < O for a given 1 ≤ i ≤ n.
Therefore, in any linearization O of P , the only adjacencies that can be preserved are the ones of the form

α i < O β i for some 1 ≤ i ≤ n. Let k be the number of couples (α i , β i ) such that α i < O β i . If k = 0 then no adjacencies at all are preserved, therefore bkpts(O, O ) = (3n+1). And consequently, if k > 0 then bkpts(O, O ) = (3n + 1) -k.
We now turn to prove the following theorem. Theorem 1. A connected graph G = (V, E) admits an independent set of vertices V ⊆ V of cardinality greater than or equal to k if and only if there exists a linearization O of P such that bkpts(O, O ) ≤ (3n + 1) -k, where O and P result from a MBL-construction of G.

Proof. (⇒) Let V ⊆ V such that |V | ≥ k and V is an independent set. Let O be a linearization of P defined by O = δ P 1 P 2 P 3 P 4 where: (⇐) Suppose we have a linearization O of P such that bkpts(O, O ) ≤ (3n + 1) -k. Let V ⊆ V be the set of vertices such that:

-P 1 is the linearization of the subset of vertices V 1 = {γ i |1 ≤ i ≤ n} such that ∀1 < i ≤ n, γ i-1 < P1 γ i ; -P 2 is any linearization of the subset of vertices V 2 = {β i |v i ∈ V -V }; -P 3 is any linearization of the subset of vertices V 3 = {α i , β i |v i ∈ V } such that ∀v i ∈ V , α i < P3 β i ; -P 4 is any linearization of the subset of vertices V 4 = {α i |v i ∈ V -V }.
∀(α i , β i ) such that α i < O β i , add v i to V By Lemma 1, we can affirm that V is an independent set. Let us verify that |V | ≥ k. By Lemma 2, Bkpts(O, O ) = (3n + 1) -k where k is the number of couples (α i , β i ) such that α i < O β i . Therefore, we obtain |V | = k.

Exact dynamic programming algorithms

Hereafter, we describe two exact dynamic programming algorithms for solving the MBL problem. The first algorithm works on an arbitrary partial order P , but has a running time that can be exponential in |V P |. However, we show that the algorithm's running time is polynomial in the more realistic case where P is built from a bounded set of genetic maps. The second algorithm applies to the case where P is built from a single genetic map, and runs in linear time.

We begin with some preliminary definitions. Let A be a subset of vertices of V P . A is a border of P iff any pair of vertices of A are incomparable, and a maximum border iff any other vertex of V P is comparable to at least one vertex of A. We also define, for any subset B ⊆ V P , f ront(B) = {x ∈ B :

x has no successor in B}. Note that the front of any set B is a border. Finally, we denote pred(A) = A ∪ {x ∈ V P : ∃y ∈ A s.t. x P y}.

A dynamic algorithm for arbitrary partial orders

Let A be a maximum border. We denote by X A,i the maximum number of adjacencies that can be obtained from a linearization of pred(A) that is consistent with the partial order P , and that ends with vertex i (i.e. i is the rightmost vertex in the total order of pred(A)). It is easy to see that the number of adjacencies in the global optimal solution is max i∈F X F,i adjacencies, where F = f ront(V P ).

The following theorem provides a recursive formula for the computation of X A,i .

Theorem 2. For any border A and any vertex

i ∈ A, X A,i = max j∈A X A ,j + 1 if |j -i| = 1 0 otherwise where A = f ront(pred(A) \ {i})) = (A \ {i}) ∪ {k | (k, i) ∈ E P and k / ∈ pred(A \ {i})}
begins with A = F = border(V P ) and stops as soon as A is the empty set. Computing all the entries of the dynamic programming table only requires operations which can be done in linear time. If the partial order P admits b(P ) possible borders, the running time is O(b(P )

• |V P | 2 ).
In the general case, the number of borders of P can be as much as 2 |VP | , if P consists of a single block of incomparable vertices. However, we are more interested in the case where P is obtained by combining m genetic maps, where each map contains a maximum of q blocks and the size of each block is at most k. In this case, there are at most q m maximal borders in P . Furthermore, two elements that are in the same border cannot be in different blocks on a genetic map, so each maximal border is of size at most km, which allows 2 km possible subsets. Therefore, the total number of borders of P is bounded above by b(P ) ∈ O(q m 2 km ). Since, in practice, only two or three different genetic maps are combined to form a partial order, the dynamic algorithm yields a practical and exact solution to the MBL problem.

A linear-time algorithm for single genetic map

When P is a genetic map consisting of a list of blocks B 1 , B 2 , . . . , B q , a much faster linearization algorithm exists. Let X i be the maximum linearization score obtained in the partial subset B 1 ∪ • • • ∪ B i ⊆ V P . The maximum linearization score of P is thus equal to X q . Let L i represent the set of elements in B i that can be placed at the last position in a total ordering of B 1 ∪• • •∪B i that achieves the score X i . Define the functions g 1 (X, Y ) = {x | x ∈ X and x + 1 ∈ Y } and g 2 (X, Y ) = {y | y ∈ Y and y -1 ∈ X}. Then, the values X i and L i can be determined recursively as follows.

Theorem 3. Define X 0 = 0 and L 0 = {}. Then, for any

1 ≤ i ≤ q, X i = X i-1 + |g 1 (B i , B i )| + 1 , if |g 2 (L i-1 , B i )| ≥ 1 0 , otherwise and
L i = B i \ g 1 (B i , B i ) , if |g 2 (L i-1 , B i )| = 1 or |B i | = 1 B i \ (g 1 (B i , B i ) ∪ g 2 (L i-1 , B i )) , otherwise
The intuition behind the recursive definition of X i is as follows: to get the maximum linearization score, we always want to join as many elements x, x + 1 within a same block. Furthermore, as much as possible, we want to join consecutive elements in neighboring blocks as well. The set L i is used to keep track of which elements can be put last in the ordering of B i and therefore possibly be matched with an element in the block B i+1 . If the elements of B i are stored in an ordered list, then the recursive definition of Theorem 3 can be implemented in a recursive algorithm for which each iteration requires O(|B i | + |L i-1 |) time to run, for a total time complexity of O(n) in the case of a genetic map of n genes.

An efficient heuristic

Since our exact dynamic programming has a worst-case running time that is exponential in the number of genes, a faster heuristic is required to solve large problem instances. In this section, a greedy heuristic is developed for general partial orders obtained from the concatenation of an arbitrary number of maps. It aims to find a maximum number of O-adjacencies coherent with a partial order P . At each step, the partial order is updated by incorporating adjacencies of the longest O-adjacency path that can be part of a linearization of P . The algorithm does not necessarily end up with a total order. Rather, it stops as soon as no more adjacencies can be found. All linearizations of the obtained partial order are then equivalent in the sense that they all give rise to the same number of adjacencies. A direct (resp. indirect) adjacency path of P is a sequence of vertices of form

(i, i + 1, i + 2, • • • i + k) (resp. (i + k, • • • i + 2, i + 1, i))
such that for any 0 ≤ j < k, either i + j < P i + j + 1 (resp. i + j + 1 < P i + j), or i + j and i + j + 1 are incomparable. For example, in Figure 3, (1, 2, 3, 4) (resp. [START_REF] Keller | Colinearity and gene density in grass genomes[END_REF][START_REF] Jackson | Consensus genetic maps: a graph theory approach[END_REF][START_REF] Hannenhalli | Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals)[END_REF][START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF][START_REF] Gale | Comparative genetics in the grasses[END_REF]) is a direct (resp. indirect) adjacency path. Notice that adjacencies of this indirect path can not belong to any linearization of P , as gene 5 should be located after 11 but before 7.

We say that an adjacency path p of P is valid iff there is a linearization O of P such that p is a subsequence of O . Lemma 3 gives the conditions for an adjacency path to be valid. We need a preliminary definition. Definition 1. Given two vertices i and j, we say that i is compatible with j iff the two following conditions hold:

1. i and j are either incomparable or i P j; 2. Any vertex v verifying i P v P j belongs to the interval [i, j] (or [j, i] if j < i).

Lemma 3. A direct (resp. indirect) adjacency path of P from i to i + k (resp. from i + k to i) is valid if and only if, for any j 1 , j 2 such that 0 ≤ j 1 < j 2 ≤ k, i + j 1 is compatible with i + j 2 . (resp. i + j 2 is compatible with i + j 1 ). A preliminary preprocessing of P = (V P , E P ) is required to efficiently compute successive adjacency paths.

1. Create the matrix M of size |V P |×|V P | verifying, for any i, j ∈ V P , M (i, j) = 1 iff i < P j and M (i, j) = 0 otherwise.

2. Compute the transitive closure of M , that is the matrice M T of size |V P | × |V P | verifying, for any i, j ∈ V P ,

M T (i, j) =    1 iff i < P j 2 iff i P j but i ≮ P j 0 otherwise
After the preprocessing step, the following Steps 1 and 2 are iterated as long as P contains an adjacency path.

-Step 1: Find a longest valid direct or indirect adjacency path. An algorithm for this step is described in Figure 4. -Step 2: Incorporate the new adjacencies in M T , and compute the transitive closure of M T .

Algorithm Find-Valid-Path (Figure 4) only considers the case of direct paths, though generalization to indirect paths is straightforward. Valid paths are computed beginning with paths of size 2. For a fixed k, any path p = (i, i+1, • • • i+k) of size k is obtained from a concatenation of two valid consecutive paths

p 1 = (i, i + 1, • • • i + k -1) and p 2 = (i + 1, i + 2, • • • i + k) of size k -1.
As p 1 and p 2 are valid paths, the path p is valid iff i is compatible with i + k.

Complexity: Computing the transitive closure of the adjacency matrix in the preprocessing phase, as well as in Step 2, is done using the Floyd-Warshall algorithm [START_REF] Floyd | Algorithm 97: Shortest path[END_REF]

Experimental results

We first test the efficiency of the heuristic compared to the dynamic programming algorithm for general partial orders on simulated data, and then illustrate the method on grass maps obtained from Gramene (http://www.gramene.org/).

Simulated data:

We simulate DAGs of fixed size n that can be represented as a linear expression involving the operators '→' and ',' where P-adjacent genes are separated by a '→' and incomparable genes by a ','. Such a representation is similar to the one used in [START_REF] Lander | MAP-MAKER: an interactive computer package for constructing primary genetic linkage maps of experimental and natural populations[END_REF][START_REF] Yap | A graph-theoretic approach to comparing and integrating genetic, physical and sequence-based maps[END_REF]. For example, the DAG in Figure 1.c has the following string representation:

{2 → 6, 1 → 3 → {4, 5} → 7} → 8 • • • 14 → {9, 15, 16, 17, 21} → {18, 19} → 20
DAGs are generated according to two parameters: the order rate p that determines the number of ',' in the expression, and the gene distribution rule q corresponding to the probability of possible O-adjacencies. We simulated twenty different instances for each triplet of parameters (n, p, q) with k ∈ {30, 50, 80, 100}, p ∈ {0.7, 0.9} and q ∈ {0.4, 0.6, 0.8}. We did not consider p values lower than 0.7, as the dynamic programming algorithm exponential-time prevented us from testing such instances.

Figure 5 shows that the running time of the dynamic programming algorithm grows exponentially with the DAG's largest border size, while the heuristic is not affected by it (this was expected, as the time-complexity only depends on the DAG's size). We note that the greedy heuristic can easily handle partial orders consisting of thousands of genes.

We now evaluate the heuristic's optimality, namely the number of O-adjacencies resulting from the obtained linearization compared to the optimal solution (obtained with the dynamic programming algorithm). As illustrated by Table 1, the performance of the greedy algorithm is almost always higher than 90%, and usually close to 100%. Illustration on grass genomes: The Gramene database contains a large variety of maps of different grass genomes such as rice, maize and oats, and provides tools for comparing individual maps. A visualization tool allows to identify regions of 'homeology' between species, that is a linear series of markers in one genome that maps to a similar series of loci on another genome. Integrating marker orders between different studies remains a challenge to geneticists. However, as total orders are already obtained for widely studied species such as rice which has been completely sequenced, one can use this information to order markers on another species by using the adjacency maximization criterion.

Extracting the linear orders of markers using the Gramene visualization tool remains unpractical for hundreds of markers, as no automatic tool is provided for this purpose. We therefore illustrate the method on maps that are small enough to be extracted manually. Maize has been chosen instead of rice as it has shorter maps, though non-trivial, that can be represented graphically.

We used the "IBM2 Neighbors 2004" [START_REF] Polacco | IBM neighbors: a consensus GeneticMap[END_REF] map for chromosomes 5 (Figure 1) and 1 (Figure 6) of maize as a reference, and compared it with the "Paterson 2003" [START_REF] Bowers | A high-density genetic recombination map of sequence-tagged sites for Sorghum, as a framework for comparative structural and evolutionary genomics of tropical grains and grasses[END_REF] and "Klein 2004" [START_REF] Menz | A High-Density Genetic Map of Sorghum Bicolor (L.) Moench Based on 2926 Aflp, Rflp and Ssr Markers[END_REF] maps of the chromosomes labeled C and LG-01, respectively, of sorghum. We extracted all markers of maize indicated as having a homolog in one of the databases of sorghum. All are found completely ordered in maize. This linear order is considered as the identity permutation. For markers of sorghum that are located on maize chromosome 5 (resp. 1), a total order maximizing the adjacency criterion is indicated in Figure 1.d (resp.

Conclusion

We have presented a detailed complexity result and algorithmic study for the problem of linearizing a partial order that is as close as possible to a given total order, in term of the breakpoint distance. Applications on the grass genomes show that this may be helpful to order unresolved sets of markers of some species using the totally ordered maps of well studies species such as rice. However, preliminary to the application of our algorithms is generating the appropriate partial orders. For this purpose, an automated preprocessing of the Gramene comparative database would be required to output the considered genetic maps, and then combine them on a single partial order. The absence of such tools prevented us from presenting more consequent applications. The next step of this work will be to generalize our approach to two (or more) partial orders, as previously considered in [START_REF] Sankoff | Reversals of fortune[END_REF][START_REF] Zheng | Reversal distance for partially ordered genomes[END_REF] for the reversal distance. As conjectured by Sankoff, an NP-complete result for this problem should be proved. A dynaming programming approach may also be envisaged for this case.

Considering the breakpoint (or similarly the adjacency) distance is a first step towards more general distances such as the number of conserved or common intervals [START_REF] Bérard | Conservation of combinatorial structures in evolution scenarios[END_REF][START_REF] Blin | Conserved interval distance computation between non-trivial genomes[END_REF][START_REF] Figeac | Sorting by reversals with common intervals[END_REF]. Indeed, an adjacency of two genes is just a common interval of size 2. A simple extension of the greedy heuristic would be to order genes that remain unordered after maximizing adjacencies, by using the constraint of maximizing intervals of size 3, 4 and so on.

Fig. 1 .

 1 Fig. 1. Data extracted from the comparison of maize and sorghum in the Gramene database. The identity permutation (1 2 3 4 • • • ) represents the order of markers in the "IBM2 neighbors 2004"[15] map for maize chromosome 5. The corresponding marker's partial orders in sorghum are deduced from (a) "Paterson 2003" [4] map of the chromosome labelled C and (b) "Klein 2004" [13] map of the chromosome labelled LG-01; (c) is the partial order obtained by combining (a) and (b); (d) is a linearization of (c) minimizing the number of breakpoints.

Fig. 2 .

 2 Fig. 2. Example of a MBL-constrction. The graph (a) is a connected graph of 6 vertices. The sequence (b) represents the complete order O and the graph (c) represents the partial order P obtained from the graph (a) by a MBL-construction.

By Lemma 2 ,

 2 we can affirm that bkpts(O, O ) = (3n + 1) -|V |. Since, by hypothesis, |V | ≥ k, we obtain bkpts(O, O ) ≤ (3n + 1) -k.

Fig. 3 .

 3 Fig.3. Dotted edges are all O-adjacencies that can, individually, be part of a linearization of P . A bi-directional edge represents the concatenation of two edges, one in each direction. An adjacency path of P is a directed sequence of consecutive dotted edges.

Fig. 4 .

 4 Fig. 4. Finding a longest valid adjacency path of P . L is the list of adjacency paths of size k, Lj denotes the j th path of L, and Lj[i] the i th vertex of Lj .

  in time complexity O(n 3 ) where n is the number of vertices of the corresponding graph. As each condition of Algorithm Find-Valid-Path can be checked in constant time and L contains at most |V | -1 elements, the time complexity of Step 1 is in O(n). Moreover, Steps 1 and 2 are iterated at most |V | times. Therefore, the worst time complexity of the greedy algorithm is in O(n 4 ).

Fig. 5 .

 5 Fig. 5. CPU time expended by (a) the dynamic programming algorithm and (b) the heuristic, for DAGs of a given size and width. Each result is obtained from 10 runs (10 different simulated DAGs). The Y axis is logarithmic.

  Figure 6.b).

Fig. 6 .

 6 Fig. 6. (a) The partial order of markers in sorghum that are located and totally ordered on the maize chromosome 1; (b) A total order maximizing the adjacency criterion.

  {As long as L contains at least two elements, concatenate paths of size k to paths of size k + 1} While |L| ≥ 2 do For j = 1 to |L| do If Lj+1 and Lj are consecutive paths then If Lj [1] is compatible with Lj+1[k] then

	Algorithm Find-Valid-Path (P)
	{Compute the list L of all adjacency paths of size 2}
	For 1 ≤ i ≤ |V | do
	If (i <P i + 1) or (i and i + 1 are incomparable) then
	Add (i, i + 1) to L;
	End For
	k = 2;
	L = Concatenate(Lj , Lj+1);
	Add L to LNew;
	End For
	If |LN ew| > 0 then L = LN ew; Clear(LNew);
	k = k + 1;
	End While
	Return (L1);

Table 1 .

 1 Percentage of O-adjacencies resulting from the heuristic's linearization compared to the optimal solution (obtained with the dynamic programming algorithm). Results are obtained by running the heuristic and dynamic programming algorithm on 10 different simulated DAGs for a given size and width.

						DAG Width
		2	3	4	5	6	7	8	9	10	11
	Genome size	30 100 100 98,15 97,41 94,33 96,18 93,18 95,54 100 100 50 100 98,04 96,43 97,62 95,25 98,61 100 86,96 95,26 94,94 80 100 98,21 97,90 87,54 96,79 93,89 100 95,83 98,33 100 100 100 98,81 95,65 96,83 89,70 93,95 90,38 95,30 94,63 94,95