Julien Clavard
email: julien.clavard@fr.thalesgroup.com

Denis Pillon
email: denis.pillon@fr.thalesgroup.com

Annie-Claude Pignol
email: pignol@univ-tln.fr

Claude Jauffret
email: jauffret@univ-tln.fr

Target motion analysis of a source in a constant turn from a non-maneuvering observer

Keywords: Constant turn motion, bearings-only target motion analysis, bearings and frequencies target motion analysis, passive tracking, maximum likelihood estimate, Cramér-Rao lower bound

The passive target motion analysis (TMA) of a source in constant turn motion by a platform moving with a constant velocity vector is addressed in this paper. The observer acquires either bearing measurements or bearing and frequency measurements. Firstly the bearings-only TMA is investigated. The observability conditions are established and the performance is analyzed with the Cramér-Rao lower bound. The behavior of the maximum likelihood estimator is evaluated using Monte-Carlo simulations, for various typical scenarios. The bearings and frequencies TMA is subsequently analyzed in the same way. Its performance is compared with that of the bearings-only TMA to evaluate the improvement brought about by frequency measurements, in some typical scenarios.

Tactical aspects are also investigated.

I Introduction

In TMA, when a sole passive sensor is employed, just few kinematic models have been adopted, compared to numerous models encountered in the active tracking domain (see [START_REF] Li | Survey of Maneuvering Target Tracking. Part I: Dynamic Models[END_REF] and its references). This is one of the consequences of the poor quality of the information contained in the data (implying a lack of observability) acquired by a passive system which does not directly measure the position of a source, unlike an active sensor.

The polynomial kinematic models are most often used; the oldest (and simplest)

is the constant velocity motion or CV motion (see [START_REF] Kolb | Bearings-Only Target Motion Estimation[END_REF] to [START_REF] Nardone | Observability Criteria for Bearings-Only Target Motion Analysis[END_REF]). The higher order is also exploited (see [START_REF] Fogel | N th-order dynamics target observability from angle measurements[END_REF] to [START_REF] Jauffret | Observability in Passive Target Motion Analysis[END_REF]).

Indeed, in the classic bearings-only TMA (or BO-TMA), it has been proved that the observer must have a model of higher order to the source's motion model to get observability but it is not sufficient ([7] [START_REF] Jauffret | Observability in Passive Target Motion Analysis[END_REF]).

Several authors have proposed more sophisticated kinematics derived from this basic deterministic model, for instance, a segmented trajectory with unknown duration of each leg ( [10] [11]). In [START_REF] Jauffret | Bearings-Only Maneuvering Target Motion Analysis from a Nonmaneuvering Platform[END_REF], we proved the interest of this model when the target's speed is constant: in this case, the observability is obtained without maneuver of the observer (except in some pathological geometry).

But these models are too restrictive. One of the challenges of the passive TMA is to construct a realistic model for which observability is acquired when the observer does not maneuver. We propose here to consider a target kinematic model for which the maneuver is not instantaneous: the legs of unknown duration are linked by arcs of a circle at constant speed (as in [START_REF] Sanjeev Arulampalam | Bearings-Only Tracking of Manoeuvring Targets Using Particle Filters[END_REF] [START_REF] Ristic | Tracking a Manoeuvring Target Using Angle-Only Measurements: Algorithms and Performance[END_REF]).

The key model being the constant turn motion (CT motion), we will start by analyzing it. From our knowledge, this deterministic model and its use in BO-TMA

has never yet been employed. Surprisingly, the first mathematicians to have treated a very similar problem are the French Pierre-Simon de Laplace [START_REF] Laplace | Mémoire sur la détermination des orbites des comètes[END_REF] in 1780 and the German Karl Friedrich Gauss [START_REF] Gauss | Theoria Motus: Theory of the motion of the heavenly bodies moving about the sun in conic sections[END_REF] in 1795. They identified the parameters of the elliptical orbit of an asteroid from angular measurements of lines of sight given by a telescope. They proved that with three angles collected at different times, they were able to recover the whole trajectory of the asteroid.

Thus they introduced for the first time the notion of discrete observability in a TMA problem. At this time, Gauss invented the method of least squares [START_REF] Sorenson | Least-Squares Estimation: from Gauss to Kalman[END_REF]. This method is already used for satellite orbit determination by ground based telescope [START_REF] Sabol | A Fresh Look at Angles-Only Orbit Determination[END_REF]. Recently, a Chinese team proposed a 3D TMA method that is very similar [20][21]. Indeed, they collect angular measurements from a High Earth Orbit (HEO) satellite in order to localize a Low Earth Orbit (LEO) satellite.

The trajectory of the observer is elliptical whereas that of the source is a circle whose center is known (the center of the Earth).

Nevertheless, the nature of these aerospace problems is different from the one considered in this paper: Here, the rotation center is unknown; as a consequence, the observability is not a priori established. This kind of kinematic is still quite common:

 Sources like lightweight torpedoes in underwater environments and drones in aerial environments, for example, travel along an arc of a circle,  Observers manoeuver in an arc of a circle to get observability in BO-TMA [START_REF] Bucy | Digital synthesis of non-linear filters[END_REF] [11] [START_REF] Ristic | Tracking a Manoeuvring Target Using Angle-Only Measurements: Algorithms and Performance[END_REF].

More generally, a surface ship or a submarine follows an approximately circular motion when it changes its heading.

The problem treated here is hence the BO-TMA of a source whose trajectory is composed of a succession of legs and arcs of a circle, its speed being constant whereas the duration of each segment is unknown.

Let us recall that in the classic case (target and observer with constant velocity vector), an additional frequency track alleviates the problem of observability ( [START_REF] Jauffret | Observability in Passive Target Motion Analysis[END_REF] [9]). Moreover, the greater the number of frequencies, the more accurate the result will be [START_REF] Jauffret | Multi Frequencies And Bearing Target Motion Analysis : Properties and Sonar Applications[END_REF].

It is legitimate to ask the same question when the source is in CT motion.

The computation of the Cramér Rao lower bound (CRLB) together with Monte Carlo simulations will allow us to evaluate the performance of proposed estimates in a set of realistic scenarios.

The underlying system is twice nonlinear: the state equation is nonlinear (due to the CT motion) as well as the measurement equation. Consequently, we can no longer use the technique that consists of transforming the natural system into an equivalent linear system (as in [START_REF] Jauffret | Observability in Passive Target Motion Analysis[END_REF]). We have been constrained to use an original mechanism based upon strong tools of analysis mathematics.

The basic questions posed here are:

 Does the observer have to maneuver to get a unique solution if only bearings are available?

 Would it be helpful to take into account a frequency measurement?

 What are the consequences tactically speaking?

We propose to answer these questions more completely than in [START_REF] Clavard | Bearings-Only Target Motion Analysis of a Source in a Circular Constant Speed Motion from a Non-Maneuvering Platform[END_REF].

This paper is organized in five main sections, followed by the conclusion and an appendix.

In section II, after having defined the assumptions and the notations, we analyze the observability when the observer measures angles only.

Section III is devoted to the presentation of the maximum likelihood estimator (MLE) and its performance. The numerical aspect is discussed.

In section IV, we deal with the same problem when additional frequency measurements or track(s) are available: observability, the MLE and its performance are analyzed.

Section V establishes the tactical advantages between a maneuvering and a non-maneuvering platform in terms of accuracy of their respective TMA, when only bearings are available and when bearings and frequencies are.

A conclusion ends the paper.

The appendix is devoted to the development of the observability analysis.

II

The Bearings-only constant turn TMA (BO-CTTMA)

II.1 Assumptions and notations

We consider an observer O and a source (or target) S moving in the same plane.

We assume that at any time, the location of the source is different from the location of the observer (collision is impossible).

The source is traveling along an arc of a circle at constant speed (say constant turn or CT motion); meanwhile the observer follows a constant velocity (CV motion). All the angles are referenced clockwise, from North as in any usual TMA problem.

At time   T t , 0 
, the source's position is given by - is the "initial angle" (relative to North), when the source starts its motion.

                                      t t y
Note that the speed of the source denoted S v is linked to the turn rate and the radius of the circle by

C S v    .
The position of the observer at any time  

T t , 0  is                           O O O O O O O y t y x t x t y t x t P   0 0 where   T O O y x   is its constant velocity vector.
The noise-free bearing at time t is given by

                  t y t y t x t x t O S O S 1 tan ) (  .
The noise-free range between the source and the observer at time

t is denoted   t R .
All these notations are illustrated in Fig. 1. The trajectory of the source is entirely defined by the state vector

  T c C C y x Z     .
To indicate that the bearings

) (t



are a function of the state vector, we will also

employ the notation ) , ( t Z  .
At time k t , the observer collects the measured bearings

) ( k m t  N k t t Z t k k k m ..., , 2 , 1 for ), ( ) , ( ) (        (1)
where

) ( k t  
is the additive noise assumed to be zero-mean and Gaussian. Its covariance matrix is equal to

    k t diag 2   (assumed to be known).
Note that the duration of any scenario is equal to

N t .
The aim of the BO-CTTMA is to estimate the state vector

Z from   ) ( , , ) ( , ) ( 2 1 N m m m m t t t       .

II.2 Observability analysis

In this section, three strong results about observability in continuous time are

given. The proofs of the results are detailed in the Appendix.

II.2.a Source in CT motion

RESULT 1 (observability case):

The trajectory of any source in CT motion is observable from bearings-only measurements  

      T c O O C O O C y y y x x x Z            ' , ) 0 (



being the homothetic ratio.

If the observer is located in the circle in which the source is travelling, this set of trajectories is augmented with the trajectories defined as the intersection of the angular sector

      T   , 0
and similar 1 Fig. 2 illustrates the case where the observer is outside the circle, whereas Fig. 3 gives an example when the observer is inside the circle. In both examples, the homothetic ratio  is equal to 3.

1 A similarity is obtained by composing of a rotation of angle  and an homothety of ratio  . In the second part of this result, the rotation angle  is submitted to the following constraints (in order to insure that the intersection between the angular sector and the similar circle is not empty):

 If 0   , then     2 0 2              C C T ,  If 0   , then     2 2 0              C C
T .

Remarks:

From the above analysis, when the observer is motionless,  knowledge of one parameter (the speed, the center of the circle, its radius) confers observability,  the turn rate  is observable,  if the observer is not in the circle in which the source is moving, the initial angle  is observable too,



II.2.b Distinguishability between a source in CV motion from an another in CT motion

In this subsection, we use a notion derived from observability called distinguishability, corresponding to the following problem:

Suppose that the source of interest S is in CT motion. We need to determine if another source, denoted ' S , in CV motion, could be detected with the same bearings as S . The answer is given by the following property.

RESULT 3 (distinguishablity of motion models in continuous time)

Consider an observer in CV motion and the source of interest S in CT motion.

Then there is no source in CV motion detected with the same bearings

  t  for   T t , 0 
. The CT motion is said to be distinguishable from the CV motion by bearings only.

Remark:

 If the observer is not motionless, observability is ensured only for the source in CT motion.

 Otherwise, the two sources are unobservable.

II.2.c Observability of segmented trajectories (succession of legs and arcs of a circle at constant speed)

The previous results allow us to get a very general and important result about observability when the observer is in CV motion, with a non-zero speed. P and the ratio is  ) would be detected in the same bearings.

We illustrate this result using the example drawn from [START_REF] Jauffret | Bearings-Only Maneuvering Target Motion Analysis from a Nonmaneuvering Platform[END_REF]: a source whose trajectory is composed of two legs with a constant speed is proven to be observable if and only if  

0 1 2   O T V V V
, where i V is the velocity of the source during the i th leg and O V is the velocity of the observer. If the two legs are linked with an arc of a circle, this condition vanishes: an illustration of this result is given in Fig. 4. An example of estimation for such a trajectory can be found in [START_REF] Jauffret | Bearings-Only Maneuvering Target Motion Analysis from a Nonmaneuvering Platform[END_REF].

III

Maximum likelihood estimator in BO-CTTMA

III.1 Algorithmic aspect

The noise being assumed to be Gaussian, the MLE is identical to the least squares estimator. So the criterion to minimize is

        N k k k m k t Z t t Z C 1 2 2 ) , ( ) ( 1 ) (     .
The minimization is done in three steps:  initialization by a choosing an initial point in a coarse grid,  ten iterations of the Gauss-Newton routine,  then as many iterations as necessary of the Newton-Raphson routine up to convergence (declared when the routine can no longer minimize the criterion) [START_REF] Julien | Clavard was born in Ploemeur, France[END_REF].

However, the risk of stalling in a local minimum exists; so, the returned estimate The performance of the MLE must be compared to the Cramér-Rao lower bound (CRLB) in order to make a conclusion about its behavior. This motivates the next section (III.2) in which we compute the Fisher information matrix (FIM).

As in any problem of TMA, giving a general formula of the performance of the MLE is very difficult: the problem is highly nonlinear and depends strongly on the scenario. To overcome this, we have recourse to Monte Carlo simulations, run on a set of typical scenarios. Firstly, we focus our study on the accuracy of the estimated final range. Secondly, we evaluate the accuracy of each component of the state vector.

III.2 Computations of the FIM and the CRLB in the BO-CTTMA

Under the previous assumptions given in II.1, the FIM is given by the following classic formula

    ) , ( ) , ( 1
1 2 k T Z k N k Z k m t Z t Z t Z F           where ) , ( k Z t Z  
is the gradient of the measurement model w.r.t. the state vector.

In practice, the position of the source at time N t (the final time) is of great interest. So we compute the FIM, relative to

      T C N S N S N t y t x Z     .
Note that only its first two components are different.

    N N Z Z m T Z Z m N J Z F J Z F , ,    where                            1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 ) sin( ) sin( ) cos( 1 0 ) cos( ) cos( ) sin( 0 1 ,                 N C n N C N N C n N C N Z Z t t t t t t t t J N is the Jacobian of the transformation Z Z N  . The CRLB of N Z (respectively of Z ), denoted   m N Z B  (respectively   m Z B  ), is the inverse of the FIM   m N Z F  (respectively   m Z F  ). Note that because   1 det ,  N Z Z J , we have         m m N Z B Z B   det det  or in

III.3 Performance of the MLE of the final range

The final range of the source is the parameter of greatest interest in practice.

Moreover, it is a good indicator of the global behavior of the MLE in TMA problems. The accuracy of its estimate will be analyzed versus

      L l N l N R R R L RMSE N 1 2 , 1
, L being the number of accepted estimates and In all the scenarios used in our simulations, the observer starts its trajectory at the origin; its speed and its heading are respectively 6 m/s and 90°. The The standard deviation of the measurement is 0.5°; The standard deviation of the measurement is 0.5°; we chose

  t k t k   
1 , with t  to be equal to 1 s.

The number of Monte Carlo runs is 500.

Remark:

Any other scenario can be deduced from these by an appropriate rotation or axial symmetry.

The performance of the estimated range is not changed by these isometries.

III.3.a Effects of the final bearing

We have chosen a set of scenarios defined as follows:

-

The source speed is

5  S v m/s.
-The trajectories of the source are identical up to a rotation around the final position of the observer (the angle of rotation is chosen to be equal to

) ( N t 
).

-

The range of the center of the circle from the final position of the observer is 10 km, the radius

C  being equal to 1
km.

-

The initial angle  is chosen to be identical to the final bearing:

) ( N t    . -
The source makes a total turn, corresponding to a duration of 21 minutes (more precisely 1256 seconds, hence

1256  N measurements).
Fig. 5 illustrates five particular scenarios where the source motion is clockwise.

Symbol o shows the initial positions of each mobile. . The relative error being less than 15%, it is worth developing the BO-CTTMA for the chosen set of scenarios. The impact of the rotation direction on the CRLB hence on the performance of the MLE must be noted. This is due to the combination of two factors: the evolution of the bearings and of the range during the scenario.

III.3.b Effect of the final range

In this part, we focus on the effect of the final range only. The set of scenarios is now defined as follows:

-

the duration is still 1256 s, -the final range between the final positions of the observer and of the source is taken in  

21 , 17 , 13 , 9 , 5 (km),
-

the initial angle is taken in   90 , 45 , 0 , 45 , 90   (degree), - 5  S v m/s and 1  C  km.
This set of scenarios is depicted in Fig. 7.

III.3.c Effect of the duration of the scenario only.

To evaluate the effect of the duration, we use the scenarios presented in section III.3.a. Here only the duration changes: the minimum duration N t considered is 627 s (corresponding to a half turn), and the maximum is 1130 s (corresponding to 90 % of a total turn). Fig. 9 shows five scenarios for 1130

 N t
s and the direction is clockwise. The results of a 500 run simulation are presented in Fig. 11 and Fig. 12 (the confidence level of the ellipsoids is 95%). In the clockwise case, one estimate has been rejected by the test and seven have been rejected in the anticlockwise case.

The global statistics (concerning the accepted estimates only) are given in Table 1 and in Table 2. The column entitled CRLB  contains the root square of the elements of the diagonal of the CRLB. In a passive sonar system, additional measurements are often available; most commonly frequencies, which contain information about the trajectory of the source thanks to the Doppler effect.

In this section we propose to evaluate the potential gain of one or more frequency tracks in the BO-CTTMA. This new method will be denoted FB-CTTMA (for bearings-frequencies TMA in constant turn) or MFB-CTTMA (for bearings-multifrequencies TMA in constant turn). Such as in the BO-CTTMA, we start with a recall of hypothesis and notations. Then we will study observability of the MFB-CTTMA, compare its performance to that of the BO-CTTMA and introduce the MLE corresponding to this last case.

IV.1 FB-CTTMA

IV.1.a Notations

The kinematics of the platform are identical to those given in §II.1: the observer moves with a constant velocity while the source follows a circular trajectory at constant speed. This time, the source emits a single pure tone with constant and unknown frequency 0 f . The state vector is now defined as follows:

    T T T C C C Z f y x f Y , 0 0      (2)
where 0 f is the unknown emitted frequency.

The noise-free received frequency is at time

t       C t R f t f / 1 0    (3)
where

) (t R 
is the radial component of the relative speed at time t and C is the speed of sound in the medium (about 1500 m/s in water). The radial speed is expressed in terms of Z :

              t Z y t y t Z x t x t R O S O S , cos , sin            where   T O O y x  
is the observer's velocity vector and

      T S S t y t x  
is the source's velocity vector at time t , more precisely:

          t t x C S cos  and            t t y C S sin  .
In order to emphasize the relationship between Y and the noise-free frequency,

we will write   t Y f , instead of   t f .
Under those assumptions, the FB-CTTMA consists of estimating Y from a collection of pairs of measurements

                   k f k k m k k k m t t Y f t f t t Z t      , , for N k ,...., 1  where   k t   and   k f t
 are the additive noises that corrupt the bearing and frequency measurements, respectively. In the sequel, these noises are assumed to be independent, 0-mean Gaussian and their standard deviations are

  k t   and   k f t 
, respectively, assumed to be known.

IV.1.b Observability in FB-CTTMA

In §II.2, the observability conditions in the BO-CTTMA case have been given: the only case of non-observability is met when the observer is motionless. So, the first question we have to answer is: does taking into account frequency measurements make the source in CT motion observable when the observer is stationary?

The answer is given by the following result.

RESULT 5

Assume that the observer is motionless.

Any source in CT motion is observable from bearings and frequencies measurements if and only if the observer is not located at the center of the circle traveled by the source.

The proof of the result is given in the appendix §VII.2.

IV.2 MFB-CTTMA

IV.2.a Notations

In this section, the source is supposed to emit P constant and unknown frequencies

1 1 0 , , ,  P f f f  . The state vector is now   T T P p Z f f f f Y , , , , , , 1 1 0     .
The P measured frequencies are given by

     , , , k f k p k m p t t Y f t f p    for 1 , , 1 , 0   P p  , with, as previously (3)     C t R f t Y f k p k p / 1 ) , (    . The variance of   k f t ε p is denoted   k f t p 2  .
The set of frequency measurements corresponding to the pure frequency

p f is           N m p m p m p m p m p t f t f t f t f f , 3 , 2 , 1 , , , , , ,   , for 1 , , 1 , 0   P p  .

IV.2.b CRLB in MFB-CTTMA

Taking into account extra measurements (the frequencies) implies augmenting the dimension of the state vector, hence the number of unknowns. In this sense, the unknown emitted frequencies

      ? , , , , , 0 , 1 , 0 m m m m P m m Z B f Z B f f Z B        (4)
Remarks:

 If 1 M and 2
M are two positive definite symmetric matrices, then

2 1 M M  means that 1 2 M M 
is a positive semidefinite matrix.

 We implicitly assume that there is one single bearing measurement, the same one for all the frequencies at each sampling time. In reality, a measured frequency is always coupled to a measured bearing. Hence, we should have as many bearings as frequencies. Because all these bearings are relative to the same line of sight, they are averaged and the result is a more accurate single measured bearing. In order to make a fair comparison, the standard deviation of the bearing has been kept at the same value. So, the impact of the extra frequency lines will be objectively judged.

 The bearing rate is supposed to be not equal to zero.

 The numbering of the frequencies is arbitrary.

Under all the specified assumptions given in this section, we obtain the following result.

RESULT 6

The performance of the estimation of the sub-state-vector Z (concerning the trajectory only) is improved with increase of the number of (unknown) frequencies included in the state vector Y . This property can be summarized by the following inequality, in terms of CRLB:

        m m m m P m m m P m m Z B f Z B f f Z B f f Z B            , 0 , 2 , 0 , 1 , 0 , , , , , , ,  
.

Remark:

This result was obtained previously when the source was in CV motion (see [START_REF] Passerieux | Target Motion Analysis with Bearings and Frequencies Measurements via Instrumental Variable Estimator[END_REF])

IV.3 MLE in MFB-CTTMA

IV.3.a Numerical aspects

We choose the MLE which consists of minimizing the following quadratic criterion

              2 1 0 1 , 2 1 , ,                          P p N k k f k p k m p N k k k k m t t Y f t f t t Z t Y C p     
As previously, we employ the Gauss-Newton routine. The initial point

  T T P p Z f f f f Y , , , , , , 1 1 0    
is selected as follows:

 Z is a node of a coarse grid,  Each p f is equal to the mean value of each track.

The returned

Y ˆ is accepted if ) (Y C is less than       12 2 3 10 2 3 ) 6 5        N P N N P N
(99.5% of the population). Then, we compute the corresponding

  T T N P p N Z f f f f Y , , , , , , ˆ1 1 0     .

IV.3.b Monte Carlo simulations

The scenarios used in § III.4 are used here. Now, the target emits

P constant frequencies   4 , 2 , 1  P
. The emitted frequencies are:

 1  P : 3 0  f kHz.  2  P : 3 0  f kHz and 5 . 3 1  f kHz.  4  P : 3 0  f kHz, 5 . 3 1  f kHz, 4 2  f kHz and 5 . 4 3  f kHz.
 The standard deviation of each frequency track is equal to

1000 / p f f p   Hz for each p .
 The celerity in the medium is 1500  C m/s.

IV.3.b.1 Clockwise case

The two following tables contain the performance of the MLE for each value of P : In Table 3 the mean values of the estimates are listed while in Table 4 the empirical standard deviation is given. The column "Bearings only" corresponds to the previous results obtained in § III.4 for the bearings-only case. taken into account, the more accurate the estimates will be. As we observe in section III.4, the MLE for the BO-CTTMA problem is not efficient, in the anticlockwise case. The efficiency of the MLE is obtained as soon as at least one frequency track is available.

IV.3.b.2 Anticlockwise case

In both cases, the simulations confirm the inequalities of RESULT 6.

V To maneuver or not to maneuver?

We start this last section with a comparison of the performance of TMA when two platforms try to track each other from bearings only (each of them is the "source" of the other). One platform has a constant velocity vector while the other one travels on an arc of a circle. In this contest, the first one employs the technique of BO-CTTMA and the second carries out the classical BO-TMA.

Then, we extend this study when an additional frequency measurement is available for each platform.

V.1 BO-TMA against BO-CTTMA

The chosen scenario is the one used in section III.4 for the anticlockwise turn.

The duration ( N t ) goes from 753 seconds (60% of a turn) to 1130 seconds (90% of a turn). During the whole scenario, the standard deviation does not change: From Table 7 and Fig. 13, the MLE of the BO-TMA performs better than the MLE in BO-CTTMA. Moreover, the duration of the scenario must be longer for the nonmaneuvering platform to reach a good accuracy: in this scenario, a complete turn is necessary to obtain acceptable performance (about 5%). In conclusion, when bearings only are available, the tactical advantage is for the maneuvering platform. Again, the respective performance is presented in a figure and a table: on Fig. 14, the estimates and their 95% confidence ellipsoids are drawn while in Table 8 the values of The results show that the previous conclusion is no longer valid: if a frequency track is used together with bearings, the non-maneuvering platform obtains much better performance than the maneuvering platform. Moreover, in the both methods, the MLE is consistent whatever the scenario duration. Remark: these conclusions must be verified using a range of scenarios to be confirmed definitely.

  5 . 0   (for each platform).
N R R N  N R R RMSE N N R R N  N R R RMSE N N R R N  N R R RMSE N N R R N  N R R
N R R N  N R R RMSE N N R R N  N R R RMSE N N R R N  N R R RMSE N N R R N  N R R RMSE N N R R N  N R R

VI Conclusion

In this paper, we have considered a source in constant turn motion and an observer with a constant velocity vector.

Firstly, its observability has been analyzed when the observer measures bearings only: the trajectory of the source is observable, except when the observer is motionless. If the observer is motionless and not located in the circle in which the source is moving, then the set of trajectories detected in the same lines of sight are all homothetic. In this case, if the observer acquires an additional frequency measurement, then the system becomes observable.

Any trajectory of a target composed of a succession of legs and at least an arc of a circle is observable from a non-maneuvering observer.

Concerning the estimation aspect, the MLE has sufficient performance to present a practical interest in anti-submarine warfare. This performance is close to the CRLB. These results have been obtained with a set of representative scenarios.

Taking frequency measurements into account improves the accuracy of the estimator (the more frequencies, the better the accuracy).

Finally, a comparison between the performance of TMA of a maneuvering observer and a non-maneuvering one has been made: when only bearings are used, the maneuvering observer has advantage over the non-maneuvering one.

This is inverted when both acquire bearing and frequency measurements.

In the future, the robustness of the MLE merits to be studied when the assumption of constant speed is violated which is possible in reality as shown in [START_REF] Trevrrow | Directionality and maneuvering effects on a surface ship underwater acoustic signature[END_REF] for a surface ship. Note that we have presented some preliminary results in [START_REF] Jauffret | Bearings-Only Maneuvering Target Motion Analysis from a Nonmaneuvering Platform[END_REF]. The robustness against biased bearing measurements must also be treated.

Another axis of research concerns the model tests whose aim will be to choose the more appropriate source kinematic (between CT and CV). The extension to the 3D case is conceivable for aerospace applications in angle only or with additional frequency [24][25].

Acknowledgement:

The authors are grateful to Frederic Dambreville for his expertize regarding the proof of RESULT 2, and to the anonymous reviewers for their constructive suggestions.

VII Appendix

We need the following result for the so called "analytic continuation" [START_REF] Spiegel | Schaum's Outline Series : Complex Variables[END_REF] .

Proposition

Let g and h be two analytic functions on and U an open interval in .

If     x h x g  for any U x  , then     x h x g  for any  x .

VII.1 Proofs of Results 1, 2 and 3

With no loss of generality and for the sake of simplicity, we will assume that the observer is moving along the x-axis, i.e.

                     0 O O O x t t y t x  during   T , 0 or is stationary ( 0  O x 
).

We need to ascertain the existence of another source, denoted ' S , detected in the same bearing   t θ as S by the observer during   T , 0

. Its position at time

t being             t y t x S S ' ' , we get                 T t t y t x t x t y t x t x t S O S S O S , 0 , arg arg ' '                        (5)  A positive scalar   0  t  exists such that                 T t t y t λ x t t x t λ t y x t t x S O S S O S , 0 , ' '        which implies that               T t t y x t t x t y x t t x S O S S O S , 0 , ' '                      T t t
        (6)

VII.1.a Proof of RESULT 1 and RESULT 2

In this part, the source ' S is in CT motion:

' and ' ), 0 ( ' , ' , '      C C C y x such that                               ' ' cos ' ' sin ' ' ' ' '      t t y x t y t x C C C S S .
We recall that for S , we also have

                                   t t y x t y t x C C C S S cos sin . So (6) is equivalent to                         C C O C C C C C C O C C C C y t x t y t x t y t x t y t x t                                  cos cos ' ' ' sin ' ' ' ' cos ' ' ' ' cos ' sin                       C C O C C O C C C C C C C C C C C C C y y x t t t x t y x y x t x t y t x t y t                     ' cos ' ' cos ' ' ' cos ' ' ' sin ' ' ' cos ' sin ' ' ' sin '                           This equality stands for   T t , 0   .
For convenience, we call the first member of the last equality  

t G :               C C C C C C C C C C C C C C y x y x t x t y t x t y t t G ' ' cos ' ' ' sin ' ' ' cos ' sin ' ' ' sin '                                 (7)
And the second term  

t H :           C C O C C O y y x t t t x t t H       ' cos ' ' cos '         (8)
The functions

  t G t  and   t H t  being analytic on   T , 0
, they are equal everywhere following the proposition. Hence

    0 ,    t t t H t t G . Since   t G is bounded, we have:   0  t t G when   t . Hence   0  t t H . But           C C O C C O y y x t t x t t H       ' cos ' ' cos '         . Convergence is possible if and only if         0 ' cos ' ' cos '       C C O C C O y y x t t x         i.e.   0 , 0    t t H . As a consequence,   0  t G . The equality   0  t H is satisfied  if 0  O x  , which implies         0 ' cos ' ' cos '       C C C C y y t t       (the observer is not stationary -case A-),  or if 0  O x 
(the observer is stationary -case B -).

1) case A (non stationary observer)

                            0 ' 0 cos ' ' cos ' 0 ' cos ' ' cos ' C C C C C C C C y y t t y y t t            
We start by exploiting the first equality:

                                                 t t t t t t C C C C C C C C ' and 0 ' or ' and 0 ' or 0 ' 0 cos ' ' cos '
Let us consider three cases:

 The case 0 '   C C   must be discarded.               t t C C ' and 0 ' Now, let us exploit the equality   t t G   , 0 :             C C C C C C C C C C C C C y x y x t x t y t x t y t t G ' cos ' sin cos sin 2 2 sin 2                                     C C C C C C C C C y x x t x x t y t ' cos sin 2 2 2 sin 2                    The equality   t t G   , 0 is incompatible with 0  C  . This case must be discarded.              t t C C ' and 0 ' Now, let us exploit the equality   t t G   , 0 :         C C C C C C y x x t x x t G ' cos            0  t G implies that C C x x '  . Finally,                          t y t x t y t x S S S S ' ' . 55
2) Case B (the observer is motionless):

We start by developing  

t G :                       t y x y x t y x t y x t y x t y x t t t G C C C C C C C C C C C C C C C C C C C C                    , 0 ' ' ' cos ' sin ' cos ' ' sin ' cos ' sin ' cos sin ' cos ' sin cos ' sin ' ' cos ' sin ' ' sin ' cos '                            
Again, we have to consider two sub-cases:

 ' ω ω  Because the functions     t ' sin    ,     t ' cos    , t  sin , t  cos ,
    t ' cos    :            0 ' sin ' 0 ' cos '         C C C C which implies that 0  C  or 0 '  C  , which is in contradiction to the fact that 0  C  and 0 '  C  .
Hence this sub-case must be discarded.

 ' ω ω  In this case,   t G becomes                 . ' ' cos ' sin ' cos ' sin ' cos ' sin ' cos ' sin ' cos ' sin ' ' sin ' C C C C C C C C C C C C C C C C C C y x y x t y x y x t y x y x t G                                                                 0 ' sin ' cos ' sin ' cos ' 0 ' cos ' sin ' cos ' sin ' 0 ' ' ' sin ' , 0                 C C C C C C C C C C C C C C C C C C y x y x y x y x y x y x t t G Let us denote by   T C C R  and   T C C R    the respective polar coordinates of        C C C y x P and           C C C y x P .
The last two equations are equivalent to

                       C C C C C C C C C C C C R R R R             sin ' sin cos ' cos hence equivalent to           C C C C C C R R       ' or           C C C C C C R R       '
We define now the positive constant

C C C C R R       .
We inject this double equality in the first equation: The source S  whose motion is defined by

        0 ' sin 0 sin ' sin ' 2 2                     C C C C C C C C R R R This equality is satisfied iff   0 ' sin    or C C R   . a)
                                    t t y x t y t x C C C S S cos sin ' ' (9)
is detected in the same bearings than

S during   T , 0 .
See equation

      '
In this case,

      C C
and, as a consequence,

       C C C C y y x x   ' '                                          t t y x t y t x C C C S S cos sin ' '                           
                               t t R t y t x C C C S S cos cos sin sin and                                       t t R t y t x C C C S S cos cos sin sin or equivalently,                                                                                             2 cos 2 sin 2 cos 2 2 cos 2 cos 2 cos 2 sin 2 C C C C C C C C C S S t t t R t t t t R t y t x                     
and, using the same formula and

                                                        2 cos 2 sin 2 cos 2 C C C C S S t t t R t y t x          Since C C          , we got                                                     2 cos 2 sin 2 2 cos 2 C C C C C S S t t t R t y t x          
As a consequence, the sources S and S  will be detected in the same bearings if and only if the sign of

        2 cos C t   
and the sign of

          2 2 cos C C t    
are the same. Because the source never meets the observer,

        2 cos C t    is either positive or negative. (i) When 0 2 cos          C t    , then 2 2 2 2              C C t which is equivalent to   T t t t C C C , 0 2 2                     . In this case,   2 C t t        .
This implies that

                           2 2 , 0 , 0          C T t C C T t t Inf t Sup . If 0   , this double inequality is equivalent to 2 2                   C C C C T ,     2 0 2                  C C C C T If 0   , it is equivalent to     2 2 0                 C C C C T . (ii) When 0 2 cos          C t    , then            2 C t t .
Similar calculations yields the same constraints:

If 0   , then     2 0 2                 C C C C T , If 0   , then     2 2 0                 C C C C T .

VII.1.b Proof of RESULT 3 (distinguishability between CT and CV motion)

Let the source ' S in CV motion:

    ' ' ' ' and , 0 , 0 S S S S y x y x    such that                             ' ' ' ' ' ' 0 0 S S S S S S y x t y x t y t x   .                     t t y x x t x y t y x t t x C C O S S S S O C C            , cos 0 0 sin 5 ' ' ' '                                   t t x x t y x x t t x y x y x t t y t t y y x y x t y x O S C C O S C S C S S O S C S C S O S C S C                  , cos cos 0 0 sin sin 0 0 0 ' ' ' ' ' 2 ' ' ' ' '                     
which can be re-arranged as follows

                        t t x x t t y t t y t x y x t y x y x y x y x t y x y x O S S S S C S O C O S O C S S C C S S C                 , cos sin sin 0 cos 0 0 0 0 ' ' ' ' ' 2 ' ' ' ' '                  
This equality between a polynomial in t and a function of sine and cosine is impossible. Hence, there is no source in CV motion that can be seen in the same bearing as S during   T , 0 .

VII.2 Proof RESULT 5 (observability in FB-CTTMA)

Again, for the sake of simplicity, we consider the observer located at the origin.

So, the observer position at any time

  T t , 0   is:       T t t y t x O O , 0 , 0 0                .
Let two sources S (the one of interest) and ' S another source in CT motion i.e.

  

                                t t y x t y t x C C C S S cos sin and                               ' ' cos ' ' sin ' ' ' ' '      t t y x t y t x C C C S S
detected in the same bearings and emitting a pure tone 0 f and 0 f  . Under these hypotheses, the common received noise-free frequency for the sources S and ' S is

          C t R f C t R f t f / 1 / 1 0 0         (10)
Since the observer is motionless, the radial speed is

 for S ,           t t y t t x t R S S   cos sin       and for ' S ,           t t y t t x t R S S   cos sin         .
On the other hand, we have,

           t t x C S cos  and            t t y C S sin                 t t x C S cos '  and                 t t y C S sin  .
We know from RESULT 2 that for some homothetic ratio  , we have

C C    ' .
The turn rates and initial angles are respectively equal:

         
, where

0   or C C       . Hence               t t x C S cos  and                t t y C S sin  . We deduce that                                   t t t R t t t R C C sin sin   Eq. ( 10
) is equivalent to                                          t t C f t t C f C C sin 1 sin 1 0 0 Hence, 0 0 f f   and                       t t t t sin sin . As a consequence, 0   and 1   .
The source S  is identical to S .

VII.3 Proof of RESULT 6 (MFB-CTTMA).

VII.3.a Expression of the FIM in a block structure for the FB-CTTMA

The Fisher information matrix (FIM) about Y takes the following form:

                        N k k T Y k Y k f N k k T Y k Y k m m t Y f t Y f t t Z t Z t f Y F 1 2 1 2 , , 1 , , 1 ,       (11)
Due to the special structure of the state vector (2), the FIM (11) can be partitioned into four blocks:

              m m T m m f Z F Z F c c f Y F    0 0 0 , (12)
with:

              N k k T Z k Z k m t Z t Z t Z F 1 2 , , 1     
, which is the usual FIM about the state vector Z when only the bearings are measured;

              N k k T Z k Z k f m t Y f t Y f t f Z F 1 2 , , 1  (13)
, which is the FIM about Z

given the frequency measurements is the following   We are going to use the following classic result of linear algebra (see [29]):

Lemma:

Consider a non-singular matrix

                   q q A p q A q p A p p A A
c c f Z F f Z F Z F f f Z B      (16)
This first result will help us to prove the property of the BMF-TMA in the coming section.

VII.3.c Proof of RESULT 6

Now we are able to prove the double inequality.

        m m m m P m m m P m P m m Z B f Z B f f Z B f f f Z B            , 0 , 2 , 0 , 1 , 2 , 0 , , , , , , , ,  
c c f Z F f f Z B f f f Z B 1 1 1 1 , 1 1 , 2 , 0 1 , 1 , 2 , 0 , , , , , , ,  
      m T m m Z F c c f Z F Z F     0 0 1 0    , hence     m m m Z B f Z B    , .
This inequality has a meaning if the observer is not motionless (observable case). Otherwise,   m Z B  does not exist and by extension, the inequality remains valid. This completes the proof of (4).

  the location of the center of the circle, -C  is the radius of this circle. -0   is the constant turn rate, positive if the motion of the target is clockwise,

Fig. 1 .

 1 Fig. 1. Observer and source geometry of BO-CTTMA.

.

  circles, the rotation center of the similarity being at   T O O y x . The turn rate of these sources is the same. The first part of this result allows us to construct easily a  -homothetic solution:The center of the circle C P  of the  -homothetic solution is given by The lines of sight are the same.

Fig. 2 .

 2 Fig. 2. Examples of homothetic trajectories: motionless observer outside the

Fig. 3 .

 3 Fig. 3. Example of homothetic trajectories: motionless observer inside the

Fig. 4 .

 4 Fig. 4. Unobservable and observable trajectories.

  other words, the generalized variances are the same. As a consequence, the volumes of the confidence ellipsoids computed with the CRLB of Z and of N Z are the same. 20 The orientation of the ellipsoid changes only in the 2D domain corresponding to the position (the first two components of Z or N Z ).

-

  the final bearing, -the final range (simply denoted N R in this section), -and the duration of the observation. Two characteristics of the performance will be used: the relative standard deviation (RSD) of the final range

  trajectory of the source takes place in the upper half of plane ( 0  y ). In this configuration, the source travels along the arc of a circle either clockwise ( all the figures, symbols + and o will represent the values of case and the anti-clockwise case, respectively. The evolution of parameter of interest will be drawn in continuous and dashed lines for clockwise and anticlockwise cases, respectively.

Fig. 5 .

 5 Fig. 5. Five scenarios for 5  S v m/s (clockwise cases).

Fig. 6

 6 Fig. 6.

Fig. 7 .

 7 Fig. 7. Scenarios when N R is in   21 , 17 , 13 , 9 , 5 (km) in the clockwise case.

Fig. 8

 8 Fig. 8 (c).

Fig. 9 .

 9 Fig. 9. Scenarios used to evaluate the performance of the MLE vs. the duration.

Fig. 11 .

 11 Fig. 11. Scenario together with the 95% confidence ellipsoid and estimated

Fig. 12 .

 12 Fig. 12. Scenario together with the 95% confidence ellipsoid and estimated

  the role of nuisance parameters: in short we have more information but more unknowns. So, the fundamental question of the MFB-CTTMA is the following: Does the MFB-CTTMA improve the accuracy of the estimate of Z (parameter concerning the trajectory only)? In terms of the Cramér-Rao lower bound, the question is

Fig. 13 Fig. 13 .

 1313 Fig.13depicts the MLE of each method together with their respective 95%

Fig. 14 .

 14 Fig. 14. Scenario used for the comparison between FB-TMA and FB-CTTMA.

  Let us exploit the nullity of have to consider two sub-sub-cases:



  the source S  is detected in the opposite bearings. Hence this sub-sub-case must be discarded. b) Now, let us exploit the equality Hence the observer is in the circles in which S and S  are travelling. The motion of S and S  are then given respectively by



  of the TMA when the number of received frequencies increases.VII.3.b Expression of the FIM in a block structure for the MFB-CTTMAAs previously (see[START_REF] Jauffret | Bearings-Only Maneuvering Target Motion Analysis from a Nonmaneuvering Platform[END_REF]), the FIM of MFB-CTTMA can be partitioned as: corresponding to the position and the velocity of the source.

11 A

 11 rate is not equal to zero, the frequency rate is non-null too and as a consequence the matrix is nonsingular. The lemma can be applied as follows

  reason as previously, we have

Table 1 :

 1 Performance at final time (clockwise)

					True
				Units		Bias		CRLB	ˆ
					values
	x	  N S t	km	7.54	0.02	0.29	0.29
	y	  N S t	km	9.00	0.03	0.65	0.66
			C	km	1.00	0.04	0.09	0.10
			°	0.00	0.47	7.28	7.35
			°/s	0.287	0.002	0.025	0.026
		R		km	9.76	0.03	0.71	0.72
			N

Table 2 :

 2 Performance at final time (anticlockwise)

					True
				Units		Bias		CRLB	ˆ
					values
	x	  N S t	km	7.52	0.22	1.08	1.22
	y	  N S t	km	9.00	0.52	2.59	2.92
			C	km	1.00	0.04	0.25	0.23
			°	0.00	32.7	28.5	60.7
			°/s	-0.287	0.123	0.06	0.236
		R	N	km	9.76	0.57	2.81	3.22
	 clockwise case

case, the bias of the last two components of the state vector (the initial angle  and the turn rate  ) are not negligible; moreover the empirical standard deviation is not close to CRLB  . So, we cannot conclude that the MLE is efficient. However, the first three components are efficiently estimated.

IV

Exploitation of additional frequency measurements (FB-CTTMA and MFB-CTTMA)

Table 3 :

 3 Bias of the MLE (clockwise)

							Bearings only			One freq.			Two freq.		Four freq.
				Z	N	True	Z ˆ	N	Average	Bias	Z ˆ	N	Average	Bias	Z ˆ	N	Average	Bias	Z ˆ	N	Average	Bias
	x	  N S t	km 7.54		7.52	0.02		7.53	0.01		7.53	0.01		7.53	0.01
	y	  N S t	km	9		8.97	0.03		9.00	0.00		9.00	0.00		9.00	0.00
			C	km	1		1.04	0.04		1.00	0.00		1.00	0.00		1.00	0.00
			°	0		0.47	0.47		0.06	0.06	-0.04	0.04	-0.06	0.06
			°/s 0.288 0.286 0.002 0.287 0.001 0.287 0.001 0.287 0.001

N Z

Units

Table 4 :

 4 Theoretical and empirical standard deviations of the MLE (clockwise)

								Bearings only One freq.		Two freq.	Four freq.
					Z	N	True		CRLB	ˆ		CRLB	ˆ		CRLB	ˆ		CRLB	ˆ
	x	  N S t	km	7.54 0.29 0.29 0.09 0.09 0.07 0.73 0.06 0.06
	y	  N S t	km		9	0.65 0.66 0.20 0.20 0.15 0.15 0.12 0.12
			C	km		1	0.09	0.1	0.04 0.04 0.03 0.03 0.03 0.03
			°		0	7.28 7.35 2.79 2.79 2.23 2.29 1.81 1.84
			°/s 0.288 0.026 0.026 0.077 0.077 0.006 0.006 0.005 0.005
				We observe that the bias is negligible on each component of

N Z Units N Z and the empirical standard deviations are very close to the values deduced from the CRLB. The MLE is hence efficient. Moreover, the more frequencies

Table 5 :

 5 Bias of the MLE (anticlockwise)

	Bearings only	One freq.	Two freq.	Four freq.

N Z

Units

Table 6 :

 6 Theoretical and empirical standard deviations of the MLE

										(anticlockwise)
								Bearings only One freq.		Two freq.	Four freq.
					Z	N	True		CRLB	ˆ		CRLB	ˆ		CRLB	ˆ		CRLB	ˆ
	x	  N S t	km	7.52	1.08	1.22	0.11 0.11	0.08	0.08	0.06	0.06
	y	  N S t	km		9	2.59	2.92	0.26 0.26	0.19	0.19	0.15	0.15
			C	km		1	0.248 0.227 0.046 0.048 0.038 0.038 0.033 0.034
			°		0	28.5	60.7		3	3.1	2.2	2.3	1.6	1.6
			°/s -0.287 0.060 0.236 0.009 0.009 0.007 0.007 0.005 0.005

N Z

Units

Table 7 :

 7 Respective performance of BO-TMA and BO-CTTMA (in %)

	Duration (s)	753	879	1004	1130

Table 8 :

 8 Respective performance of FB-TMA and FB-CTTMA (in %).

	Duration (s)	627	753	879	1004	1130

  

																																								.
	 Left inequality:  Z B		m	,	f	0	,	m	,	, 	f	P		2	,	m	,	f	P	, 1 	m	  Z B 		m	,	f	0	,	m	,	, 	f	P		2	,	m		.
	We can re-write (16) as follows
		m	m	P	m			P			m	 			m		m	P		m	 				P	m		P	P	T P

A User's Guide to Nonlinear Optimization Algorithms.

Proceedings of IEEE, 72, 12 (1984), 1765-1776.

[29] Frank Ayres, JR.

Schaum's Outline Series : Theory and Problems of Matrices (1962), 55-57.

France. From 1992 to 1999, he was consultant at the DCN sonar laboratory. He worked on new sonar arrays and various submarine combat systems. Since 2000, he has been sonar expert at Thales Underwater Systems (Sophia-Antipolis). His current researches are about passive sonar performances estimation, submarine and torpedo array processing, and long term prospective studies for submarine warfare.


Anne-Muriel Arigon
email: arigon@biomserv.univ-lyon1.fr

Guy Perrière

Manolo Gouy

Automatic identification of large collections of protein-coding or rRNA sequences

Keywords: Automatic identification, similarity, alignment, phylogeny, chimera

The number of available genomic sequences is growing very fast, due to the development of massive sequencing techniques. Sequence identification is needed and contributes to the assessment of gene and species evolutionary relationships. Automated bioinformatics tools are thus necessary to carry out these identification operations in an accurate and fast way. We developed HoSeqI (Homologous Sequence Identification), a software environment allowing this kind of automated sequence identification using homologous gene family databases. HoSeqI is accessible through a Web interface (http://pbil.univ-lyon1.fr/software/HoSeqI/) allowing to identify one or several sequences and to visualize resulting alignments and phylogenetic trees. We also implemented another application, MultiHoSeqI, to quickly add a large set of sequences to a family database in order to identify them, to update the database, or to help automatic genome annotation. Lately, we developed an application, ChiSeqI (Chimeric Sequence Identification), to automate the processes of identification of bacterial 16S ribosomal RNA sequences and of detection of chimeric sequences.

Introduction

Identification is used in many fields, such as microbiology, medicine, environment.

Sequence identification consists in the attribution of an unknown taxonomic unit to a taxonomic group of a pre-established classification. Thus, to identify a new taxon or a new sequence, it is necessary to find its nearest known taxon. In the medical field, methods of identification are used to detect and recognize micro-organisms implied in pathologies, which thus helps choosing the most suitable treatment. Identification can also be used in the agroalimentary field as tools for food traceability. In other contexts such as identification of species or taxons from environmental organism molecular markers, the confrontation of a new sequence with a database, or sequence database update, the assignment of a new sequence to a collection is necessary. The number of available biological sequences increasing considerably with the development of massive sequencing techniques, it is necessary to rapidly classify these sequences into existing databases.

According to analyzed data, the approach used for identification differs and several tools exist. Identification tools often vary with the type of sequences and thus with the sequence databases for which they were developed. Several tools exist to make sequence identification and most of them are domain specific or data specific. For instance, some applications allow bacterial identification as BIBI (Bioinformatic Bacterial Identification) [START_REF] Devulder | BIBI, a bioinformatic bacterial identification tool[END_REF], PhyID/CD [START_REF] Flandrois | Génération et visualisation de la phylogénie des Bacteria pour l'étude des incohérences taxinomiephylogénie[END_REF] or MicroSeq (Microbial identification System), others are specialized for the medical domain as RIDOM (Ribosomal Differenciation Of Medical Organisms) [START_REF] Harmsen | RIDOM : comprehensive and public sequence database for identification of Mycobacterium species[END_REF] or for the identification of Ribosomal RNA sequences as the RDP classifier (Ribosomal Database Project) [START_REF] Cole | The Ribosomal Database Project (RDP-II): sequences and tools for high-throughput rRNA analysis[END_REF], or TaxI [START_REF] Steinke | TaxI : a software tool for DNA barcoding using distance methods[END_REF] based on DNA barcodes.

We are interested in the homologous gene family databases HOVERGEN and clustered into families, i.e., sequences of the same family share a common ancestor. Sequence alignments and phylogenetic trees for each family are also stored in these databases. Thus, these databases can be used for different purposes, among which phylogenetic analyses, and they allow the study of sequence evolutionary relationships. In order to build these family databases, several complex automated procedures are needed (similarity search, gene clustering, multiple alignment and tree computations). With the very fast growth of biological data, gene family database updates are time-consuming and tedious. Moreover, the addition of a single sequence to a given family from these databases can have many repercussions on the topology of the associated phylogenetic tree; these changes may be located near the introduced sequence, but they may also be located in deep nodes. In such case, the phylogenetic information brought by the whole family should be taken into account. Also, as HOVERGEN and HOGENOM contain large families, with several thousand sequences, powerful algorithms are required in order to manage large amount of sequences. Available identification tools, such as those presented previously, are developed to treat specific data and cannot be used effectively with large family databases. Thus, it is necessary to develop methods and bioinformatics tools (i) to carry out identification processes in a precise and rapid way, and (ii) to quickly add sequences to these databases without integrally updating them.

Two applications adapted to homologous gene family databases: HoSeqI and

MultiHoSeqI

We have developed an application -HoSeqI (Homologous Sequence Identification)and an other derived from the first -MultiHoSeqI. HoSeqI [START_REF] Arigon | HoSeqI: automated homologous sequence identification in gene family databases[END_REF] is a web application (http://pbil.univ-lyon1.fr/software/HoSeqI/) that allows to automatically identify sequences in large gene family databases. The identification process of an unknown sequence into these databases consists in (i) finding the homologous gene family to which this sequence belongs, using similarity search, (ii) aligning the analysed sequence with the whole family and (iii) reconstructing the phylogenetic tree of the family including the new sequence. HoSeqI proposes an interface allowing the user to submit his/her sequence and to choose the database.

When the family of the studied sequence is determined, the user can obtain information on the selected family and choose between several multiple alignment and tree building programs.

Then it is possible to visualize the resulting alignment and phylogenetic tree (figure 1).

The developments carried out for HoSeqI were also used to create another application -MultiHoSeqI -allowing to quickly add several thousand sequences to a homologous gene family database. MultiHoSeqI corresponds to a generalization of HoSeqI to n sequences. For each one of these n sequences, the application identifies the family to which it belongs, then for each family containing at least an added sequence, alignments are computed and phylogenetic trees are built including the new sequences. MultiHoSeqI is publicly usable on the HoSeqI web interface with a restriction on the number of sequences: the user can choose between the identification of only one sequence or of several sequences. If "several sequences" option is selected, the user submits his/her sequences, chooses the database, the multiple alignment and tree building programs. The process is then started on the server and the results are sent to the user by e-mail.

Use of MultiHoSeqI with sequences of bacterial genus Frankia

MultiHoSeqI has been used to add genes from several collections of protein sequences to the databases developed by the PBIL (Pôle BioInformatique Lyonnais): putative protein sequences from metagenomes and from completely sequenced bacterial genomes. In collaboration with Philippe Normand (Laboratory of Soil Microbial Ecology, University of Lyon), Vincent Daubin and Simon Penel (Laboratory of Biometry and Evolutionary Biology, University of Lyon), this application was used to add predicted protein sequences from two completely sequenced genomes of the bacterial genus Frankia into the HOGENOM database in order to study the evolution of these genomes and to detect possible horizontal gene transfers to Frankia.

The bacterial genus Frankia belongs to the class Actinobacteria. Among Actinobacteria, there are in particular genus Mycobacterium (agents of tuberculosis and leprosy) and genus Streptomyces (soil bacteria at the origin of many antibiotics). Twelve species of Frankia are recognized today. These bacteria fix nitrogen and convert atmospheric N2 gas into ammonia, this in symbiosis with a large spectrum of dicot plants, called actinorhizal. These plants, with their symbiotic bacteria, are collectively responsible for approximately 15% of the biologically fixed nitrogen in the world. This association presents a major ecological interest and many actinorhizal plants are used by the pharmaceutical industry because of their large production of phenolic molecules of various activities (e.g., antimicrobial, antioxydant, antiviral, anti-inflammatory drugs, antispasmodic, antitumor). So, it is interesting to search information about genes involved in symbiosis and to study how symbiosis evolved.

Three strains of Frankia were available when we made this study: HFPCcI3 (CcI3), By using the database thus updated, phylogenetic trees were analyzed in order to detect possible horizontal gene transfers to Frankia. Firstly, we carried out a pattern search using the tool FamFetch [START_REF] Perrière | HOBACGEN : database system for comparative genomics in bacteria[END_REF][START_REF] Dufayard | Tree pattern matching in phylogenetic trees : automatic search for orthologs or paralogs in homologous gene sequence databases[END_REF]: we searched genes of Frankia whose closest relatives were not from other Actinobacteria. Secondly, we re-built phylogenetic trees of families selected with the pattern search using Gblocks [START_REF] Castresana | Selection of conserved blocks from multiple alignments for their use in phylogenetic analysis[END_REF] to filter alignments and then PhyML to compute the trees.

Possible horizontal gene transfers were detected if Frankia proteins were significantly clustered with sequences from distant species.

An example of a possible horizontal gene transfer to Frankia of the gene coding for prephenate dehydratase is shown in figure 2. Sequences from the three Frankia strains are localised within sequences of Alpha-Proteobacteria, a group phylogenetically distant from Frankia. So some ancestor of Frankia probably acquired this gene from an Alpha-Proteobacterial donor. It is interesting to notice that Alpha-Proteobacterial species of this tree are also nitrogen fixing bacteria.

An application adapted to 16S ribosomal RNA sequence databases: ChiSeqI

We are also interested in 16S ribosomal RNA databases, such as the American database, RDP [START_REF] Cole | The ribosomal database project (RDP-II): introducing myRDP space and quality controlled public data[END_REF] or the European database, Ribosomal RNA Database [START_REF] Wuyts | The European ribosomal RNA database[END_REF]. These databases contain 16S ribosomal RNA (rRNA) sequences which are commonly used for bacterial identification because these molecules are ubiquitous, abundant in cells and having a conserved structure.

When sequences come from PCR amplification, chimeras, i.e. artefactual sequences produced by the experimental protocol and composed of several DNA fragments of distinct origins, can occur. Chimeras represent an important problem because they suggest the presence of non existing organisms. It is thus necessary to be able to detect them. The tasks of identification and chimera detection require the chaining of different programs (for similarity search, alignment and tree computation) that are sometimes complex to handle. When these tasks must be carried out on a large number of sequences, these two processes then become timeconsuming. So, it is necessary to have automated tools making it possible to carry out these operations in a precise and fast way.

Several available tools allow to identify rRNA sequences, some we presented previously (BIBI, RDP classifier); others can detect chimera, such as the Robison-Cox et al. method [START_REF] Robison-Cox | Evaluation of nearestneighbor methods for detection of chimeric small-subunit rRNA sequences[END_REF],

Check chimera [START_REF] Cole | The Ribosomal Database Project (RDP-II): sequences and tools for high-throughput rRNA analysis[END_REF], mglobalCHI package [START_REF] Komatsoulis | A new computational method for detection of chimeric 16S rRNA artifacts generated by PCR amplification from mixed bacterial populations[END_REF], Bellerophon [START_REF] Huber | Bellerophon : a program to detect chimeric sequences in multiple sequence alignments[END_REF], PhyID/CD, CCODE (Chimera and Cross-Over DEtection) [START_REF] Gonzalez | Evaluating putative chimeric sequences from PCR-amplified products[END_REF], Mallard [START_REF] Ashelford | At least one in twenty 16S rRNA sequence records currently held in public repositories estimated to contain substantial anomalies[END_REF] or Pintail [START_REF] Ashelford | New Screening software shows that most recent large 16S rRNA gene clone libraries contain chimeras[END_REF]. However these methods give various results. They are complementary and none is known to be the best. They allow to obtain information to help the user to determine if the analyzed sequence is chimeric and they do not allow automatic detection of chimera and identification of non-chimeric sequences in a single operation.

In the context of a collaboration with the Laboratory of Soil Microbial Ecology, we developed an application -called ChiSeqI (Chimeric Sequence Identification) -allowing to automate the processes: (i) of identification of non chimeric sequences using a database of 16S rRNA sequences; and (ii) of detection of chimeras among a set of 16S rRNA sequences.

In both cases, developed methods employ a phylogenetic approach. The database used for the identification was created from a data set of bacterial 16S rRNA sequences of cultivated strains (made available by Richard Christen, Laboratory of Virtual Biology, University of Nice). The algorithm developed for the application is divided into two parts: first, for each analyzed sequence, it determines if the sequence is not a chimera; second, it identifies the species to which the treated sequence belongs. This algorithm allows to detect and to discard chimeric sequences and then, it allows to identify the species to which the non chimeric sequences belong. But it does not analyse chimeras and does not determine break points.

In order to identify the species to which belongs a sequence, it is necessary to determine the closest relatives of the database. Firstly, the set of the most similar sequences is selected.

Then these sequences are aligned, including the analyzed sequence, and finally, the corresponding phylogenetic tree is built. Various alignment methods are proposed to the user: CLUSTAL W [START_REF] Thompson | CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position specific gap penalties and weight matrix choice[END_REF], MULTALIN [START_REF] Corpet | Multiple sequence alignment with hierarchical clustering[END_REF], MABIOS [START_REF] Abdeddaïm | Fast and sound two-step algorithms for multiple alignment of nucleic sequences[END_REF], MENTALIGN [START_REF] Dufayard | Incremental algorithms for the alignment and the phylogeny of large homologous sequence families[END_REF] and MUSCLE [START_REF] Edgar | MUSCLE: amultiple sequence alignment method with reduced time and space complexity[END_REF], and for tree building: QuickTree [START_REF] Howe | QuickTree: building huge Neighbour-Joining trees of protein sequences[END_REF], FastME [START_REF] Desper | Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle[END_REF], BIONJ [START_REF] Gascuel | BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data[END_REF] and PhyML [START_REF] Guindon | A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood[END_REF]. The species to which the studied sequence belongs, is considered to be close (even identical) to the species of the nearest sequence in the phylogenetic tree.

The principle used for chimera detection is also based on closest neighbours. A chimeric sequence corresponds to the fusion of several sequence segments. Thus, if a chimera is compared to a set of sequences, one expects to find several phylogenetically distant matches, which obtain good alignment scores with various parts of the chimeric sequence. In the developed detection method, the analyzed sequence is cut in two halves of equal length. Then, for each half-sequence, the set of the most similar sequences is identified in the 16S rRNA sequence database and the redundancy between the two sets is eliminated. The alignment of these two sets of homologous sequences is then computed, and the two half-sequences are added to this alignment. If the two half-sequences are distant in the corresponding phylogenetic tree, i.e. if the phylogenetic distance calculated between the nearest nodes to the half-sequences is higher than a threshold, then the two parts of the studied sequence come from different organisms. The sequence is then considered as a chimera.

Here is an example of chimera detection. The analyzed sequence is a 16S rRNA sequence of an unknown proteobacterium (Genbank accession number: X68474). ChiSeqI was used to determine if this sequence is chimeric. After the similarity search with the two half-sequences, the alignment and the phylogenetic tree (figure 3) were computed. On this tree, the two halfsequences are circled. The first half-sequence is close to a group of Acetobacteraceae and the second is close to a group of Hyphomicrobiaceae. So the analyzed sequence seems to be a chimera between at least these two distinct organisms.

Conclusion

We have presented here three applications allowing to rapidly and automatically identify genomic sequences. Firstly, HoSeqI and MultiHosSeqI are adapted to homologous sequence databases. Via a web interface, HoSeqI determines homologous gene families to which the series of query sequences belong and proposes to visualize alignments and phylogenetic trees of these families, including analyzed sequences. HoSeqI thus contributes to the study of the evolutionary background of new sequences. MultiHosSeqI is used to add many sequences to a homologous family database. This program can be used to quickly identify a large amount of sequences, but also to make an immediate update of a database or to annotate sequences. This application was used to add sequences of Frankia genomes to the HOGENOM database, which allowed us to detect potential horizontal gene transfers to Frankia. Finaly, ChiSeqI is adapted to the 16S rRNA sequence databases and proposes a module to detect chimera. The usefulness of ChiSeqI is thus to automatically identify a set of 16S rRNA sequences by determining, for each sequence, the species to which it belongs and its taxonomy, after having discarded chimeras.

Legends of figures:

  EAN1pec (EAN) and ACN14a (ACN). The two first strains were sequenced in the DOE Joint Genome Institute in collaboration with D. Benson (University of Connecticut) and L. Tisa (University of New Hampshire). The third strain was sequenced in the Génoscope in collaboration with P. Normand. Genomes of these strains are circular and their size vary between 5.38 millions of base pairs (Mb) for CcI3, 7.50 Mb for ACN and 9.08 Mb for EAN. MultiHoSeqI was used to add sequences of genomes of the strains CcI3 (4557 sequences) and EAN (7976 sequences) to a local version of the database HOGENOM (based on the version 2 of October 2004) containing sequences of the strain ACN of Frankia. Among the 12533 sequences that were analysed, 2450 (19,5%) sequences could not be identified. These sequences are orphan for which no recognizable homolog exits in the HOGENOM database. So MultiHoSeqI identified 10083 sequences of Frankia and computed alignments and phylogenetic trees of 4435 families containing at least one Frankia sequence.

Figure 1 .

 1 Figure 1. Screenshot of HoSeqI interface showing an example of sequence identification. Information on the family to which the analyzed sequence belongs and the resulting multiple sequence alignment and phylogenetic tree can be visualized. The query sequence name is boxed in the tree and is at the top line in the alignment.

Figure 2 .

 2 Figure 2. Example of possible horizontal gene transfer to Frankia.

Figure 3 .

 3 Figure 3.Phylogenetic tree obtained using ChiSeqI in order to determine if the analyzed sequence, named X68474 and circled in the tree, is chimeric.

Figure 3

 3 Figure 3