Philippe Jacquet
email: philippe.jacquet@inria.fr

Ieee Fellow

Information Theoretic Study of Covid 19 Genome

Keywords: Genome, Covid, Joint Complexity, pattern matching

In this paper we analyse the genome sequence of covid 19 on a information point of view and we compare with past and present genomes. We use the powerful tool of joint complexity in order to quantify the various potential parent genomes.

I. INTRODUCTION

The outbreak of the pandemic SARS-2 Covid 19 disease has been the major event of these two last years. There have been many speculations on the origin of the virus and about its future and pasts mutations. Therefore the genome of the SARS-2 has draw many attention. The foundation of Information Theory is to extract patterns and similarities between structures without necessarily relying on the functional significance of the common fragments, e.g. the meaning of words in texts, or the proteins translated in genomes. Nevertheless we will show that the information theoretic tools, such as the joint complexity, are powerful enough to draw some conclusions about the recent speculations on the origin of the virus even in absence of medical specific background.

The paper is organized as follows: first we will shortly introduce the concept of joint complexity and reminds the background results on random strings about "weak" pattern matching and establish some new results about "strong" pattern matching. Second we will present our result about weak pattern matching which establish that the covid 19 is a descendant of bat coronaviruses. We also establish that the virus of the HIV should not be an ancestor. Third we address the area of strong pattern matching in analysing the similarities with recent bat coronaviruses.

II. THE JOINT COMPLEXITY TOOL AND PERFORMANCE

Let's take a finite alphabel A and a finite sequence X over A. A factor is sequence v such that there exists two other sequences u and w such that X = uvw. We call "string complexity" of X the number of different factors of X [START_REF] Jacquet | Classification of Markov sources through joint string complexity: Theory and experiments[END_REF], [START_REF] Milioris | Joint Sequence Complexity: Introduction and Theory[END_REF]. Let Y be another sequence, we call "joint complexity" the number of different factors common to X and Y .

These quantities are easy to compute. Indeed the string complexity is simply the number of internal nodes in the extended suffix tree [START_REF] Jacquet | Common words between two random strings[END_REF] (also called the spaghetti suffix tree). It can also be computed via the compressed suffix tree but with leave extensions pointing in the string. Since the later can be built in a time proportional to the length X, denoted |X|, thus computing C(X) is proportional to |X|.

The genomes are written in the alphabet A = {A, C, G, T }, made of the four nucleo-bases. Although the genomes sequences are not purely random, we will use for comparison, randomly generated sequence over A. Since the bases mostly appear uniformly in each genome, most of the time we will rely on memoryless uniform generation on A, but all the results which will be stated below have been obtained under more general sequence generation models, such that biaised memoryless, Markov with finite memory, mixing models [?].

Theorem 1 ( [2]): The average complexity of a string X built on a memoryless or a Markov source satisfies:

E[C(X)] = (|X|+1)|X| 2 + |X| -|X| log |X| h -1 2 + γ h |X| +O(log |X|), (1)
where h is the per symbol entropy rate of the source model and γ is the Euler-Mascheroni constant.

When the source model is uniform memoryless on the four bases we have h = log 4. We notice that the string complexity in our models is mostly quadratic, indicating that almost the factor comprised between every pair of position in X is unique.

A. Weak and accidental pattern matching

By weak and accidental pattern matching we mean the joint complexity between two random sequence X and Y independently generated.

Theorem 2 ( [3], [START_REF] Jacquet | Analytic pattern matching: from DNA to Twitter[END_REF] chapter 10): When X and Y are of same length but generated on two different source models (e.g. a Markov transition matrix with different parameters): when

|X| → ∞ E[J(X, Y )] ∼ |X| κ a log |X| + b (2)
with κ < 1, and some parameter a and b > 0. When X and Y are of different length but on the source model then when both

|X| |Y | tend to infinity E[J(X, Y )] ∼ (|X|+|Y |) log(|X|+|Y |)-|X| log |X|-|Y | log |Y | h . (3)
Proof: All the proof are [START_REF] Jacquet | Analytic pattern matching: from DNA to Twitter[END_REF] chapter 10 the only new result is the refinement of the result about E[J(X, Y ) when X and Y are on the same source model. To simplify we only hint the proof on a memoryless source. We know from [START_REF] Jacquet | Analytic pattern matching: from DNA to Twitter[END_REF] that J(X, Y ) ∼ C(|X|, |Y |) where C(z 1 , z 2 ) is function which satisfies:

C(z 1 , z 2 ) = (1 -e -z1 )(1 -e -z2 ) + a∈A C(p a z 1 , p a z 2 ) (4)
with p a the probability of the occurrence of symbol a in a random sequence. If we denote f λ (z) = C(z, λz) we get the functional equation

f λ (z) = (1 -e -z )(1 -e -λz ) + a∈A f λ (p a z) (5)
whose asymptotic is obtained via the Mellin transform as described in [START_REF] Flajolet | Mellin transforms and asymptotics: Harmonic sums[END_REF].

B. Strong pattern matching

We call strong pattern matching when the sequences X and Y are so close that they are just a light alteration of each other. Theorem 3: Let k ≥ 1 be a fixed integer, assume X is generated by a memoryless or a Markov source and Y differs via k symbol substitution. We have the estimate when |X| → ∞:

E[J(X, Y )] ∼ (|X| + 1)(|X| + 2 -k) (k + 2)(k + 1) . (6)
Notice that when k = 0 we don't find back the estimate E[C(X)] since C(X) = J(X, X). In strong pattern matching mode the joint complexity remains quadratic.

Proof: To compute the leading term we look at the factors which don't overlap the positions where the k substitution occurs between X and Y . These factors are common to both X and Y and we know that almost surely they are unique. Thus our analysis rigorously is a lower bound, since we have no room to develop the upper bound proof. Let J k n be the cumulated number of such factors considering all the n k combination of substitued positions between nX and Y . Therefore

E[J(X, Y )] = J k n ( n k )
. We know that

J 0 n = (n+1)n 2 . The generating function J 0 (z) = n J 0 n z n = z (1-z) 3 for |z| < 1.
We have the recurrence

J k n = n-k m=0 J 0 m + J k-1 n-m-1 (7)
which translated in generating function gives

J k (z) = z k 1-z J 0 (z)+J k-1 (z) z 1-z which resolves in J k (z) = z k (1-z) 4 1+z (1-z) k-1 -1 + z . The asymptotic leading term is contained in 1+z (1-z) k+3 which is n (n + 2 -k) (n+1)n(n-1)•••n-k+1 (k+2)!
z n . The coefficient of z n divided by n k gives the claimed asymptotic term.

III. ACCIDENTAL PATTERN MATCHING ON GENOMES

The genome of the Covid totalizes 29,866 bases (first variant 2020). In the figure 1 we show the joint complexity of the SARS-2 Covid genome with "Bat coronavirus HKU2" [START_REF] Wu | A new coronavirus associated with human respiratory disease in China[END_REF] (discovered in 2007) which has 27,165 bases. The SARS-2 genome is parsed from right to left, and the plot shows the joint complexity between this portion of the genome withh the genome of the bat alpha. In dash we show the average joint complexity between two random genomes obtained via the same uniform memoryless source over the four bases. This last plot is directly obtained via the formula (3). Since the last plot is below the joint complexity with the bat alpha, we can conclude that indeed the SARS-2 Covid and bat alpha are indeed related.

On figure 2 we display the same plot but normalised with formula (3). We add in red the joint complexity with an HIV virus HIV-1 isolate 060SE from Sweeden (1997) [START_REF] Neogi | Recent increased identification and transmission of HIV-1 unique recombinant forms in Sweden[END_REF] (8,732 bases) and see that the genomes are indeed unrelated. In fact we get the surprising result that the plot is below the average between random sequences indicating that that some factors in SARS-2 covid and in HIV are excluding each other.

However in [START_REF] Perez | COVID-19, SARS and Bats Coronaviruses Genomes Unexpected Exogenous RNA Sequences[END_REF] the authors claim to have found 19 short portions of HIV genomes from different sources which appear in the SARS-2 genome. This paper is only a preprint but resulted in lot of noise when it went public. Some found in this insertion the proof that the SARS-2 covid genome would have been forged for malignant. Indeed we have the theorem: Theorem 4 ( [6] Chapter 4): Let {w 1 , w 2 , . . . , w k } a set of k different sequences. Let X be sequence built on a memoryless source. The probability that the sequence contains all the k factors together is smaller than |X| k P (w 1 ) • • • P (w k ), where the P (w i )'s are the respective probability of occurrence of sequence w i from the memoryless source.

Since the average putative HIV fragments in SARS-2 genomes depicted in [START_REF] Perez | COVID-19, SARS and Bats Coronaviruses Genomes Unexpected Exogenous RNA Sequences[END_REF] are or length 20 bases or more each, under the archetypal hypothesis that the SARS-2 is from a uniform memoryless source, the probability to have all these 19 copied fragments would be 2.10 -144 . Thus these accidental insertions would be virtually impossible. The table above lists the 19 matching genomes. The (R) attribute means that the genome must be reversed in order to get the claimed match. Figure 3, shows the repartition of the matching between SARS-2 genome [START_REF] Wu | A new coronavirus associated with human respiratory disease in China[END_REF] and the 19 HIV genomes (plus the bat coronavirus alpha, which is number 20). The figure has been created the following way. The SARs-2 genome has been cut in slices of length 24 bases starting every 2 bases. For each HIV candidate genome, we compute its joint complexity with every slices, which give a mean and the variance, then we display for each slice the deviation from the mean in multiple of the standard deviation (it can be negative). This way the accidental matching will be made more apparent. The blue vertical lines are the positions where the maximum deviation appears for each HIV genome. For example for the genome 18 the position of the maximum is 20,400 and is of intensity 15 times the standard deviation, which is very large. The brown plot gives for each slice of SARS-2 genome the maximum of the deviations obtained with the joint complexity over the 20 genomes. Notice that second largest deviation is obtained with "Bat coronavirus HKU2" indicated by index 20. 15 times the standard deviation would mean a probability around 7.2.10 -100 in a pure gaussian context. It should nbe noted that the high peaks correspond to slices with almost exact copy in the other genome, the weaker peaks when there are more mismatches as an illustration of the strong matching theory. The paper [START_REF] Perez | COVID-19, SARS and Bats Coronaviruses Genomes Unexpected Exogenous RNA Sequences[END_REF] lists sequence matching within up to three or four mismatches. As a matter of comparison, we display in figure 4 the same plot but with the reversed SARS-2 genome. The maxima are way less dramatic. But we notice that all these genomes are coming from very diverse sequences, on HIV-1, other on HIV-2, some on ape origin (the simian IV). Many have been even tested in reversed sequences. We can imagine the author may have tested much more sequences than the 19 selected sequence. Maybe here is the explanation of this paradox. Let M the cumulated number of bases of the tested database. Due to the large sampling of HIV and HIV related sequence in the databases, we can estimate M to the order of half a million bases. The number of positions that can be tested for each match is M |X|, X being the SARS-2 genome sequence. If 20 is the size of expected matches, the average number of matches of length 20, is M |X|4 -20 in the uniform memoryless model. If we include the possibility of up to three errors in the matching, we have to multiply this number by 20 3 . Using Tchebychev inequality we would get

P (19 matches) ≤ M |X| 19 20 3 ∼ 0.8. ( 8
)
Under this perspective the matchings are no longer exceptional. But one could argue that the Tchebychev upper bound is very rough and the real probability could be much smaller. But it should be noted that the probability becomes much larger when the data are strongly positively correlated. This is confirmed by figure 5 which display the numerous accidental matching between HIV-2UC1 and the other matcher genomes. Dating of 1993 the DNA editing technology was not existing.

IV. STRONG PATTERN MATCHING ON COVID GENOMES

In this section we try to analyse the hypotheses of the relation of the covid with its potential ancestors and descendants. The current landscape is summarized in the following figure 6 In short a first putative ancestor is the bat coronavirus "Bat coronavirus HKU2" [START_REF] Lau | Complete genome sequence of bat coronavirus HKU2 from Chinese horseshoe bats revealed a much smaller spike gene with a different evolutionary lineage from the rest of the genome[END_REF] (let's call it bat-α) which has been discovered in 2007 and has 27,165 bases. The next ancestor is the another bat coronavirus RaTG13 [START_REF] Zhou | A pneumonia outbreak associated with a new coronavirus of probable bat origin[END_REF], [START_REF] Zhou | Addendum: A pneumonia outbreak associated with a new coronavirus of probable bat origin[END_REF] discovered in 2013 and has 29,855 bases (let's call it bat-β). Then the first SARS-2 covid coronavirus for human, discovered late 2019 and another bat coronavirus RaCCS203 [START_REF] Wacharapluesadee | Evidence for SARS-CoV-2 related coronaviruses circulating in bats and pangolins in Southeast Asia[END_REF], discovered early 2020 and has 29,775 bases. Thus the pivot genome is the bat-β RaTG13. In the following figure we have sliced the bat-β genome in slices of 50 bases each, and computed the joint complexity with other genomes. Figure 7 shows the bat-β slice joint complexity with the whole genome bat-α. Apparently the ancestor seems too distant to look nothing more than random, we are on a weak pattern matching level indicated by the lower dashed horizontal line determined by the estimate produced in (3). The figure 8 shows the bat-β slice joint complexity with its whole genome. In this case the joint complexity naturally find the position of the slice in the whole genome as its best match and the figure basically shows the complexity of the slice and illustrate the formula of theorem 1 (indicated by the dashed upper line). Between the two lines lies the transition between weak pattern matching and strong pattern matching. Figure 9 shows the bat-β slice joint complexity with its whole SARS-2 covid genome. Surprisingly the slice joint complexity seems to be in strong matching regime (very close to the upper horizontal dashed line), indicating a high degree of similarity. This is unexpectede because there is the same time span between the discovery of bat-α the discovery of bat-β than there is between the discovery of bat-β and the SARS-2 covid (6 years in both cases). Even more surprising there is even more similarities with SARS-2 than with the genome of the last bat coronavirus RaCCS203, although the latter is for the same specie (bat), and the former is for two different species (human versus bats). Indeed the plot of pattern matching between bat-β and RaCCS203 shows many places where the pattern matching is weak, in particular between the position 21,500 and 24,000 probably indicating the possibility of a large insertion of exogen genetic material.

The three genomes are so close that we can make in correspondence the segments of each genome with the segment in the other genome. Via a straightforward adaptation of the joint complexity program we can compute the offset between the segments in one genome with the segments in the other genome. It consists to spot the largest common factor instead of enumerating the common factors. In term of programming it is just replacing the operator of summation evaluation with the operator of maximum evaluation. Thus for each slice of bat-β we detect the position of its largest match in the other genome. The difference of positions between the two matches in their respective genome is the offset. If the offset is positive then the match is in advance in the first genome compared with the second genome, otherwise when it is negative it is in advance in the second genome. The figure 11 shows the offset per bat-β slice with the SARS-2. Two surprises. First surprise is that except for an extreme minority of slices marked by the three dotted vertical blue lines, the offset is constant and flat and increases from -26 to -16. The offset stability indicates that the mutation sequence between the two genomes are mostly substitution. The three slices which does not fit well are slices where the substituted bases are too numerous and corrupt the largest match to make it jump by a large value, since the correspondence can be anywhere in the genome sequence: the interval [-29, 855, +29, 855]. For the readability of the figure we have truncated the abscissas. The second surprise is that the offset monotonically increases, indicating that the mutation happened by insertions and never by deletion. That against the common belief that virus mutations mostly proceed by deletion. Maybe it is the consequence of the inter-specie transfer from bat-β to SARS-2. The figure 12 shows the result of the same exercise of offset determination from bat-β genome to the last bat coronavirus RaCCS203. Contrary to the transition between bat-β genome to SARS-2 genome, the offset value is decreasing, sometimes sharply, indicating that the mutation proceeded more by deletion than by insertion, confirming the natural trends in virus evolution. However we notice some insertion small at some positions where the offset value slightly bumps up. We again notice the large corrupted area between position 21,500 and position 24,000. But the offset value drops too after, thus this exogen insertion does not push the material to the right. Figure 13 displays the mismatch rate between each slice of bat-β genome and its corresponding slice in SARS-2 genome in blue. We see the very few strongly corrupted slices with poor correspondence, elsewhere the substitution rate oscillates between 0 and 10% per 50 base slices. In green we do the same exercise with the RaCCS203 genome. Although in the same lineage, the corruption are much more important. We notice again the area between 21,500 and 24,000 where the Hamming distance is around 65%, ten point below the expected 75% with both portions uniformly and independently generated, but which can be explained by the fact that the largest match should isolate around 5-6 bases.

V. CONCLUSION

We have presented an analysis of the covid genome and its possible origins via pure information theoretic tool. Our investigations are not addressing any medical and biogenetic considerations and are mainly based on the pure randomness in the genome mutation process. Therefore they cannot lead to definite answers. Anyhow we can establish that the accidental insertion of HIV segment in the SARS-2 covid is not so exceptional and be easily explained by the abundance of existing materials in the genetic database of HIV. On the other size the strong pattern matching with the putative ancestor bat coronavirus RATG13 is a surprise since the two sequences are more than 6 years apart and two different species. The matching are much weaker with putative descendant of RATG13, RACS203, despite they are both related to bats.

Fig. 1 .

 1 Fig.1. Joint complexity of SARS-2 genome with bat coronavirus alpha (solid), with random genomes (dashed).

Fig. 2 .

 2 Fig. 2. (Normalized Joint complexity of SARS-2 genome with bat-α, and with HIV genome (red).

Fig. 3 .

 3 Fig. 3. Joint complexity deviations of SARS-2 genome with the 19 HIV genomes.

Fig. 4 .

 4 Fig. 4. complexity deviations of Reverse SARS-2 genome with the 19 HIV genomes.

Fig. 5 .

 5 Fig. 5. Joint complexity deviations of HIV-2UC1 genome with other matchers

Fig. 6 .

 6 Fig. 6. Putative genealogic tree of SARS-2 Covid.

Fig. 7 .

 7 Fig. 7. Joint complexity of bat-β genome with bat-α.

Fig. 8 .

 8 Fig. 8. Joint Complexity of bat-β with itself

Fig. 9 .

 9 Fig. 9. Joint complexity of bat-β genome with SARS-2 Covid genome.

Fig. 10 .

 10 Fig. 10. Joint Complexity of bat-β with with the RaCCS203 genome.

Fig. 11 .

 11 Fig. 11. Local offset value of bat-β genome with SARS-2 Covid genome.

Fig. 12 .

 12 Fig. 12. Local offset value of bat-β with with the RaCCS203 genome.

Fig. 13 .

 13 Fig. 13. Mismatch rates between bat-β genome slices and corresponding SARS-2 genome slices (blue) and corresponding RaCCS203 genome slices (green).


Philippe Mongin

Le Comité éditorial de la Revue de Philosophie Economique / Review of Economic Philosophy salue avec admiration et affection la mémoire de Philippe Mongin, récemment disparu. Ancien directeur de la publication (avec Daniel Hausman) de la revue Economics and Philosophy, Philippe Mongin avait également compté parmi les premiers soutiens de notre Revue. Il lui a permis de bénéficier de sa compétence exceptionnelle, de sa vaste culture, de son ouverture aux débats théoriques internationaux et de son exigence méthodologique.

Formé à la philosophie et aux mathématiques, il avait investi les domaines de l'analyse de la décision et de l'économie sans jamais se départir des exigences qui, à ses yeux, rendaient nécessaire un retour fréquent à la philosophie et aux mathématiques, pour ne pas perdre de vue l'argumentation, la preuve, la maîtrise complète d'un processus cohérent d'acquisition de connaissances. Inquiet de la méthode, Philippe Mongin mettait volontiers en communication l'avancement des sciences et l'épistémologie générale (domaine fortement structuré pour lui par l'héritage revendiqué du positivisme logique et par les travaux de Karl Popper et d'Imre Lakatos). Son association durable aux travaux de l'Institut d'Histoire et de Philosophie des Sciences et des Techniques, à la Sorbonne, en a témoigné.

C'est avec un esprit de rigueur, frappant pour ses lecteurs et pour ses collègues, qu'il a abordé les grands domaines de la théorie de la décision et des sciences économiques, montrant une grande générosité dans l'accompagnement des recherches entreprises par d'autres, notamment les doctorants qu'il a dirigés ou suivis. Circulant avec aisance d'un pays à un autre, et entre les institutions d'accueil (dans la fidélité à son cher CNRS), jouant un rôle des plus importants dans plusieurs communautés de recherche, il put réaliser des contributions décisives.

Ainsi, nul ne peut ignorer sa contribution à la théorie des choix collectifs (avec le réinvestissement dans un cadre « multi-profil » des fameux théorèmes dits « utilitaristes » de J. Harsanyi). C'est également à lui que l'on doit une caractérisation exacte des choix méthodologiques possibles dans la théorie des choix individuels en situation d'incertitude ou de risque, face à l'émergence puis à la consolidation des grands paradoxes venus de l'observation empirique et de l'expérimentation (en particulier dans son travail sur la thèse de Duhem-Quine sollicitée en rapport avec le « paradoxe d'Allais » et la théorie de l'espérance d'utilité). On lui doit encore l'examen épistémologique le plus subtil, sans doute, de la place du « postulat » de la maximisation du profit dans la méthodologie friedmanienne de l'économie positive. Il se consacra également avec passion à la théorie de l'agrégation des préférences et à de nombreux autres domaines, allant de la mesure de l'utilité à la stratégie militaire, en passant par la macro-économie et les risques nucléaires.

Ayant déployé ses premiers efforts de chercheur à propos de l'oeuvre de Karl Marx (sous la direction de Raymond Aron), très bon connaisseur aussi de l'utilitarisme et de certaines contributions importantes à la théorie économique dite néoclassique, à la macro-économie et à la théorie des jeux, il était familier de la complexité des rapports entre conviction personnelle et raisonnement objectif, entre idéologie et science. Les travaux de séminaire -par exemple, dans « Méthodologie de la science empirique » avec Alain Boyer, ou encore dans le séminaire parisien sur la justice sociale et l'économie normative, dont il fut l'un des responsablesétaient pour lui une sorte de milieu naturel, propice à l'examen approfondi des questions les plus difficiles.

Philippe a quitté ce monde au terme d'une maladie pénible, montrant à ses collègues et à ses amis, dans ces circonstances, une attention marquée aux autres. Conscient des limites de l'empathie et du jeu des sentiments en matière de science sociale et de philosophie, il aura cependant embrassé des causes et témoigné à sa manière de l'importance des enjeux humains et de l'engagement personnel face aux problèmes sociaux, économiques et politiques de notre temps. Endosser un rôle public au moment opportun et témoigner de la valeur de la science, c'était pour lui tout un. Dans son rôle de conseiller économique, il connaissait le prix d'un maniement responsable des modèles et des protocoles de mesure.

Aux frontières de l'économie et de la philosophie, les chercheurs savent ce qu'ils lui doivent, pour ne rien dire de ses disciples proches. Confions à l'histoire de la pensée, mais aussi aux tâches nécessaires d'une épistémologie rigoureuse et créative, telle qu'il en donnait l'exemple, le soin de faire comprendre les acquis de ses recherches et de déterminer les meilleures manières de suivre les pistes fécondes qu'il lui a été donné d'ouvrir.

Le comité éditorial de la Revue de philosophie économique