David Guerrero
email: david.guerrero@ifsttar.fr

Ifsttar Madis IMPACTS OF TRANSPORT CONNECTIONS ON PORT HINTERLANDS

Keywords: port, hinterland, containerization, spatial interaction models, intermodality

In this paper is examined the spatial distribution of international trade flows between the French NUTS-3 regions and West-European ports. The research question focus on the impacts of the quality of inland and maritime connections on the scope of hinterlands. The results of a spatial interaction analysis show that distance remains a strong barrier for port choice but slightly less than in the past. Its effect is significantly lower when intermodal connections -such regular barge or rail servicesare available. A case study focused on East Asian trade shows that factors related to maritime connectivity such the frequency of containerized services at ports and their ability to accommodate large vessels also contribute to limit the distance impedance. However these effects considerably vary depending on the value density of cargo.

INTRODUCTION

In this paper spatial interaction models are used to measure the impact of the quality of land and maritime connections on hinterlands, i.e. the market areas of ports. It is focused on the case of France, an developed country served by the two main European port ranges, where hinterland data is available at a detailed geographical level. A former work [START_REF] Guerrero | Deep-sea hinterlands: Some empirical evidence of the spatial impact of containerization[END_REF]) is updated and expanded in several ways. First, cargo heterogeneity is taken in account by distinguishing four groups of flows based on their value density. Second, intermodal connections between ports and inland regions are considered. Third, an origin-constrained model is used to measure the impact of maritime transport supply at ports on hinterland's scope.

Understanding the impacts of transport connections on hinterlands is important from several perspectives. First, a better assessment can be done of the consequences of major shifts in maritime transport, such the recent introduction of mega-vessels or changes in service frequency, on hinterlands. Second, the influence of intermodal connections on hinterland expansion can be estimated, for different types of shippers. This could be helpful for planners and policy makers aiming to evaluate the impact of infrastructure improvements on specific industries and regions. From the perspective of regions relying on distant suppliers or clients, securing access to one or several ports, at a reasonable cost, is a key issue for their economic development. In the specific context of France, this is particularly true for retail and manufacturing industries highly dependent on distant inputs (e.g. automobile, household appliances, agri-food sector). Access to ports is also a major issue for firms doing most of their sales overseas such those in the fields of wine and spirits, electronic or luxury products.

This paper also aims to assess the importance of geographical proximity in port choice. It seeks to test if the preference of shippers for closer ports has diminished or not in the recent years, in favor of other forms of proximity [START_REF] Hall | Shifting proximities: The maritime ports sector in an era of global supply chains[END_REF][START_REF] Rallet | Proximity and localization[END_REF]. To assess the link between geographical proximity with changes in maritime industry, a case study is carried out on the trade with East Asia. The article is strongly focused on the relevance on the quality of inland and maritime transport connections in the interpretation of the changes on hinterlands. Less attention is paid to other aspects explaining port choice such the strategies of shipping companies and terminal operators, border effects, or governance issues. Nevertheless, these factors have an impact on hinterland friction, so they receive some attention as well.

The rest of the paper is structured as follows. A review of literature is provided in the next section. Section 3 presents data and method. Section 4 provides detailed results of spatial interaction models for different years, testing the effects of both inland and maritime transport connections. Section 5 presents the conclusions and some implications for port actors and policymakers.

BACKGROUND

This article aims to contribute to two types of studies in port geography: (a) those related to containerization and its impact on hinterlands, (b) those more specifically related to distance impedance and barriers.

Containerization and hinterland expansion

Containerization has challenged the hypothesis of captive hinterlands that are spatially concentrated around ports. New kinds of liner shipping services such those organized as hub-and-spokes networks, involving increasing concentration of flows and then . As a matter of fact, the overall efficiency of shipping networks increasingly relies on the individual efficiency of a small number of nodes, generally a few in each world region [START_REF] Ducruet | The worldwide maritime network of container shipping: spatial structure and regional dynamics[END_REF]. For pure hubs, efficiency simply relies on sea-sea transshipment activities, but for the vast majority of ports the interconnection with hinterland should also be achieved [START_REF] Hayuth | Multimodal freight transport. Modern transport geography[END_REF][START_REF] Robinson | Ports as elements in value-driven chain systems: the new paradigm[END_REF].

Between 1960s and 2000s, container has enabled important changes in liner shipping, making possible the transport of almost any kind of cargo on a same ship. For shippers, it offered the opportunity to ship low volumes of cargo at low cost. For carriers and terminal operators, it offered the opportunity to concentrate flows and achieve economies of scale. Each container can be easily transferred between ships and terminals or another means of transport without unpacking. These characteristics, made possible by standardization, allowed significant economies in handling activities and maritime transport [START_REF] Neufville | Productivity and returns to scale of container ports[END_REF][START_REF] Cullinane | Economies of scale in large containerships: optimal size and geographical implications[END_REF]. However, the high capital cost of container ships and handling tools necessitate a push for its maximum utilization. This push can only be achieved when the ships are sailing at their full capacity. However when the demand is weak, such during the past ten years, shipping lines should reorganize themselves in alliances in order to optimize their transport capacities, avoiding -as far as possible-empty slots.

In the recent period (2007)(2008)(2009)(2010)(2011)(2012)(2013)(2014)(2015)(2016)(2017), the emergence of mega-vessels and the development of alliances have drastically affected ports. Larger vessels imply higher container volumes at each call, requiring infrastructure upgrading, and also improved coordination with efficient inland connections. A recent work has showed that a single call between Europe and the Far East now typically generates an annual container volume of 300,000 TEU [START_REF] Notteboom | The relationship between port choice and terminal involvement of alliance members in container shipping[END_REF]. There are less services, concentrated in fewer ports per range, and inducing changes all along the supply chain, particularly on the land side. One of the aims of this work is to better assess the impacts of these shifts on the hinterlands.

As shipping lines compete for achieving economies of scale in maritime transport, ports struggle for securing hinterland access, which is becoming more than ever a key element in their competitiveness. This idea is well summarized by the concept of port regionalization [START_REF] Notteboom | Port regionalization: towards a new phase in port development[END_REF]. It implies strong integration of ports with both inland and maritime segments. Ports are viewed as nodes within intermodal networks and competition takes place between transport chains instead of between ports [START_REF] Robinson | Ports as elements in value-driven chain systems: the new paradigm[END_REF]. Inland terminals are used to alleviate congestion and lack of space at ports, and high capacity intermodal connections by rail and barge are developed. Attracted by lower land costs and high levels of accessibility, logistic zones emerge around these inland terminals, offering services such the fulfillment of customs formalities, depots for empty containers, cargo consolidation, inventory management or pre-assembly of components. Although the regionalization process is essentially driven by market forces (2005), public actors also play an active role in the inland expansion of port systems [START_REF] Wilmsmeier | The directional development of intermodal freight corridors in relation to inland terminals[END_REF]. The direction of regionalization, initially considered from the sea to the land is debated. It is not systematically driven from ports, but it also can be driven from the land (intermodal operators, public organizations) to the sea (Monios and Wilmsmeier 2012a). In a recent work based on the successful case of Venlo-Rotterdam, Raimbault et al. [START_REF] Raimbault | Port regionalisation from a relational perspective: The rise of venlo as dutch international logistics hub[END_REF] further adds on the complexity of the model, by demonstrating that both directions can be at play simultaneously. As compared to the situation observed in the Netherlands, it should be noted that the scope of regionalization process in France is more limited, partly because of the lower volumes handled by its ports. To address this issue, the recent reforms of French ports (2006)(2007)(2008)(2009)(2010)(2011)(2012)(2013)(2014)(2015)(2016) have largely promoted the association of maritime and waterway ports, and allowing them to be directly involved in dry port development [START_REF] Lacoste | The adaptation of the landlord port model to france's major seaports: a critical analysis of local solutions[END_REF][START_REF] Debrie | From national reforms to local compromises: The evolution of france's model for port management, 2004-2015[END_REF].

Borders and other sources of impedance

Despite a stronger integration in the context of port regionalization, important barriers remain to hinterland expansion. Recent works continue to underline the importance of borders and distance in the configuration of European hinterlands, showing their unequal effects depending on the geographical position of countries: coastal or landlocked. The former are more constrained by inland distance than the latter. While coastal countries are tied to their national logistics networks, landlocked ones have historically expanded their logistics networks beyond in order to get access to the sea [START_REF] Kashiha | The functional spaces of major european forwarding ports: study of competition for trade bound to the united states[END_REF]. The impact of borders on hinterland flows would also be more or less strong depending on the ports considered, borders are more easily crossed to reach Belgian or Netherlands ports.

Border effects also considerably vary depending on the direction of flows. Therefore, the effect of the alpine border would be stronger for Italian ports than for those of the Northern Range, both competing for the North Italian market [START_REF] Ferrari | Measuring the quality of port hinterland accessibility: The ligurian case[END_REF]. This asymmetry would result not only from the different levels of service of ports but also on the unequal level of skills of the actors involved on hinterland connections on both sides of the Alps [START_REF] Acciaro | Contested port hinterlands: An empirical survey on adriatic seaports[END_REF]. The latter differences are not just limited to language proficiency but also commercial skills and the ability to cope with different cultures.

Another factor which still heavily shape the hinterlands is the geographical proximity between ports and inland markets. This has been proven to be true in several regional contexts [START_REF] Malchow | A disaggregate analysis of port selection[END_REF][START_REF] Xu | Density economies and transport geography: Evidence from the container shipping industry[END_REF][START_REF] Itoh | Market area analysis of ports in Japan[END_REF][START_REF] Charlier | L'arrière-pays national du port du havre [une approche macro-géographique[END_REF][START_REF] Guerrero | Deep-sea hinterlands: Some empirical evidence of the spatial impact of containerization[END_REF][START_REF] Wang | The effect of distance on cargo flows: a case study of chinese imports and their hinterland destinations[END_REF][START_REF] Garcia-Alonso | Analysis of the evolution of the inland traffic distribution and provincial hinterland share of the spanish port system[END_REF][START_REF] Tiller | Spatial patterns of landside trade impedance in containerized south american exports[END_REF]. However, its impact on inland flows varies considerably depending on the shape of the countries: large countries with broad inland regions such the United States tend to exhibit lower friction values [START_REF] Pitts | Inter-port competition and cargo tributary areas for international containerized exports from the United States[END_REF]) than much smaller coastal countries such France or Italy [START_REF] Ferrari | Measuring the quality of port hinterland accessibility: The ligurian case[END_REF]). In the latter, the relatively high values of friction partially result from the few alternatives to road haulage, this is different from the US context where there is an extensive use of rail intermodal transport.

Last, but not least, recent works have pointed out the development of port-centric logistics, implying container stripping at ports and re-distribution of imported goods from port-based distribution centers (DCs). One of the advantages of this location would be the reduction of inland transport costs, allowed by the elimination of empty inland running of containers [START_REF] Mangan | Port-centric logistics[END_REF][START_REF] Ng | Port-focal logistics and global supply chains[END_REF]. However, when the inputs of DCs are sourced not exclusively from overseas, the location at ports, generally at the margins of countries, may be sub-optimal with regard of the location of clients (Monios and Wilmsmeier 2012b;[START_REF] Acciaro | Efficient hinterland transport infrastructure and services for large container ports[END_REF]. Another limitation of port-centric logistics is that the reduction of transport cost obtained by the elimination of empty returns of containers would be partly offset by the increase of volume of cargo resulting from the use of pallets and individualized packages [START_REF] Acciaro | Efficient hinterland transport infrastructure and services for large container ports[END_REF]. The distribution of the load of one single container of densely packed goods would even require several trucks (McKinnon 2014). Finally, the impact of port-centric logistics on hinterlands would be mixed. On one hand, it involve an increasing weight of distribution activities in port surrounding areas, implying a kind of captivity vis-à-vis specific ports. On the other hand, the increased efficiency of inland transport would contribute to the intensification of long haulage flows, and then to an increasing competition between ports. However, given its relative newness, and it's still limited development in France compared to other countries such UK or the Netherlands, its impacts on friction are likely to be minimal.

In this article the friction is used as a measurement of trade impedance between regions and ports (for a compelling conceptual framework on trade impedance see [START_REF] Tiller | Spatial patterns of landside trade impedance in containerized south american exports[END_REF]). The last work on French hinterlands based on 2005 data is updated. The 2008/2009 crisis, changes on production and distribution systems such manufacturing off-shore and the generalization of e-commerce would have considerable impacted the organization of the catchment areas ports. In such a context an update of the former works devoted to French hinterlands appears to be necessary. guerrero, d.

DATA AND METHOD

Data

To measure the variations of hinterlands for different types of flows a database has been built with information from French Foreign Trade Statistics. The data, provided in a disaggregated and exhaustive fashion, delivers information on the value and weight of trade between French NUTS-3 regions and European ports (see Figure 1). Data on 2008 (exports) and 2012 (imports and exports) is used. An important methodological break has occurred in foreign trade data collection in 2007 [START_REF] Guerrero | Deep-sea hinterlands: Some empirical evidence of the spatial impact of containerization[END_REF], meaning that comparisons between the periods before and after 2007 are problematic. Moreover, due to changes in procedures on data collection between 2007 and 2010, important data problems have been observed, particularly for imports. It is for that reason that temporal comparisons have only been made for exports.

Figure 2 depicts the market shares of the ports serving the five French macro-regions during the 1999-2012 period. The top container ports of Le Havre, Marseilles-Fos and Benelux ports attract between 60% and 80% of the trade generated by each macro-region. While Le Havre captures most of the exports from Western France and the Paris region, Benelux ports dominate the strongly industrialized North East. Marseilles-Fos handles almost a half of the trade generated by the South-East, but the local share of Benelux ports has increased in the recent period. Unsurprisingly, during the overall period, secondary ports have been losing ground against the top container ones.

The spatial units used in the model are the French NUTS-3 regions, also known as départements. 95 NUTS-3 regions have been considered, excluding those of Overseas French Territories. Customs offices located in French ports were aggregated into ports.

Information about ports of foreign countries handling French foreign trade is only available at the country level. Then, ports have been divided into two types: (a) 16 individual ports located in France and (b) 5 foreign country port sets, which handle together 98% of the value and 97% of the tonnes of French foreign trade. The truck time-distances between centroids of NUTS-3 regions and ports used in the spatial interaction model have been extracted from ESPON inter-NUTS-3 distance database [START_REF] Spiekermann | Accessibility and spatial development in Europe[END_REF]. To measure the impacts of intermodal connections, two datasets have been created with high capacity waterway links (Voies Navigables de France) and rail intermodal services in 2012 (Naviland Cargo). Data on shipping services between East Asia and European ports has been obtained from International Transport Handbook in 2012, edited by Ocean Commerce Ltd, headquartered in Japan.

Method

A doubly constrained spatial interaction model has been used to model the geographical distribution of trade flows between the NUTS-3 regions and the ports, by testing variables related to the interactions between both. In its basic form factors related to the cargo volumes generated by the NUTS-3 region and to the port, and a distance variable are fitted. The doubly constrained spatial interaction model used is formulated as follows:

I ij = A i • O i • B j • D j • d -α ij • IW T ij • RAIL ij
where O i is the total maritime traffic of the NUTS-3 region called i, D j is the total maritime traffic of the port called j; d ij is the distance between i and j; α is the friction parameter; and A i and B j are the balancing factors ensuring that the origin i and the destination j constraints are satisfied. A NUTS-3 region is referred to as i and a port is referred to as j. •IW T ij and RAIL ij are two dummies indicating when at least one weekly intermodal service is available between a NUTS-s region and a port.

However, doubly constrained models doesn't allow to model factors exclusively related to ports. To overcome this limitation, an origin-constrained spatial interaction model has been fitted to the data. This involved fitting a factor representing the NUTS-3 regions and variables representing port attractiveness and distance. It has been assumed that the volume of trade generated by each NUTS-3 region is fixed. The total volume captured by each port is not fixed, however, and it has been estimated on the basis of the frequency of services and the average size of vessels calling at the port. It can be formulated as follows:

I ij = •O i • V F REQ j • V SIZE j • d -α ij • IW T ij • RAIL ij
where O i is the total maritime traffic of the NUTS-3 region called i, V F REQ j is the number of weekly services with East Asia for the port called j, V SIZE j is the average size of vessels serving East Asia for the port called j, •IW T ij and RAIL ij are two dummies indicating when intermodal infrastructure or services are available between regions and ports.

The choice of measure of distance influences the results of the spatial interaction model. The truck time-distance has been selected because it seemed to be consistent with the French context, where road transport plays a largely dominant role in the ports modal split. Moreover, the explanatory power of the model appeared to be slightly higher when the truck time-distance was used, as compared to the distance as the crow flies. The data finally used is a matrix of freight flows, usually measured in annual tonnes moved. As the o/d matrices contained many zero values, a Poisson regression has been used to fit the spatial doubly constrained model [START_REF] Flowerdew | Fitting constrained poisson regression models to interurban migration flows[END_REF][START_REF] Fotheringham | Spatial interaction models: formulations and applications[END_REF][START_REF] D'aubigny | Approche poissonnienne des modèles d'interaction spatiale[END_REF].

The friction parameter (α) is interpreted as a measure of the decrease of flows between ports and NUTS-3 regions with distance, other things being equal (see [START_REF] Tiller | Spatial patterns of landside trade impedance in containerized south american exports[END_REF] for a compelling discussion on distance impedance). A friction parameter lower than 1 means that the friction parameter is less than proportional to distance. A friction parameter of 1 means that the friction parameter is proportional to distance. The higher the friction the more limited is the scope of the hinterlands. A friction of ∞ would imply that the area of the hinterland is equal to zero. The friction parameter provides an overall indicator of a combination of factors which vary with distance, to which subsequent reference will be made. In this paper it is also considered as a proxy of the sensitivity of shippers to transport cost depending on the types of commodities.

RESULTS OF THE MODEL

A doubly constrained spatial interaction model has been used on flows on different years to measure how the sensitivity of different kinds of shippers to distance has evolved, particularly since the 2008 crisis, which is supposed to have widen the gap between largest ports and the secondary ones [START_REF] Notteboom | Concentration and the formation of multi-port gateway regions in the European container port system: an update[END_REF]. To take in account the heterogeneity of cargo, four datasets have been considered depending on the density of value of flows.

A recent relaxation of the distance constraint

Table 1 reports the estimates of a doubly constrained spatial interaction model without dummies for four subsamples of cargo flows based on value density, in 2008 and 2012. It shows that inland distance has a negative relationship with port choice, and its effect is slightly stronger for low value cargo (Group 1). For the latter, the preference for nearer ports has even increased between 2008 and 2012. This change in friction partly results from a relative specialization of large ports in higher value cargo, mostly containerized, meaning that smaller ports usually located closer to the shippers, catch a higher proportion of them.

The other groups of flows, implying cargo of higher value, have evolved in the opposite direction. Inland distance is valued less negatively than in 2008. Factors others than inland transport cost such time or reliability seem to become comparatively more important in port choice. Moreover, as stated by [START_REF] Kashiha | Border effects in a free-trade zone: Evidence from european wine shipments[END_REF],price increase resulting from higher transport costs will probably have little effect on the final demand of high value goods. The trend towards load centering and hubbing in container shipping lines has helped to encourage this trend. Large distribution centers and warehouses, mostly located at large urban areas mostly located inland are also crucial, because they concentrate increasing amounts of cargo, mainly manufactured. This might indicate that distance is a factor to contend with for both containerized and non-containerized cargo, but the dominance of large ports in containerized goods is much important than for the other types of cargo, thus confirming the prominent role of economies of scale allowed by containerization.

Despite the substantial differences which exist between the methods, it is worthwhile to put these results in perspective by comparing them with those obtained in other countries. France turns out to be in an intermediate position, somewhere between the U.S. context where friction is relatively weak [START_REF] Levine | Estimating an origin-destination table for US imports of waterborne containerized freight[END_REF]) and the strong one in Northern Italy [START_REF] Ferrari | Measuring the quality of port hinterland accessibility: The ligurian case[END_REF]). These differences result of several factors, such distinct types of organization of inland connections to ports, uneven geographical configurations or institutional frameworks.

A significant impact of intermodal connections on hinterland expansion

Table 2 shows the results of a doubly constrained spatial interaction model including modal dummies in 2012 for imports and exports. It shows that the preference for nearer ports is stronger for exports than for imports. The availability of waterway and rail connections significantly reduces the impedance of inland distance. But the impacts greatly vary depending on imports and exports and on the value density of cargo flows.

Inland waterways have a significant and strong impact on all the groups of flows except those of low value, both for imports and exports. This result is counterintuitive to what would usually be thought of as a slow transport system for low value cargo such cereals or raw materials. However, inland waterways turn out to be increasingly used for the supply of imported high value goods to heavily congested metropolitan areas such Paris. Moreover, some manufacturers in electronics and home appliances sectors are using waterway transport to strategically delay their deliveries to retailers, to save warehousing costs, and having the possibility to accelerate the flow by shifting from waterway to road in case of emergency.

The impact of the availability of intermodal rail services on flows is also significant, but less than in the case of inland waterways. Its influence is more limited for exports, being particularly high for both lowest and highest value ones. For the latter, the use of intermodal rail services imply certain advantages such for example extra periods for parking at intermodal terminals.

To gain insights into how economies of scale in shipping affect friction information on the shipping services at ports have been included into a new version of the model focused on East Asian trade.

The quality of maritime transport supply at ports also contributes to hinterland expansion

To test the impact of port-related factors an origin-constrained interaction model has been used. Table 3 summarizes the friction values, which unsurprisingly vary depending on the value density of cargo, both for imports and exports. The higher the value density the lower is the sensitivity to inland distance. The frequency of services has a significant impact on all groups of flows but its contribution varies considerably between imports and exports. For the former, the impact of frequency is higher for high value flows. For exports the higher impact is rather on low value added cargo. These important results confirms the impact of the quality of maritime transport supply on transport distance [START_REF] Wilmsmeier | Determinants of maritime transport costs-a panel data analysis for latin american trade[END_REF][START_REF] Guerrero | Explaining international trade flows with shipping-based distances[END_REF].

Vessel size also has a significant and positive impact on flows, meaning that the ports where large ships calls are less constrained by inland distance than the others. There are no substantial differences depending on the value density of cargo.

As in the previous versions of the model, intermodal services also significantly contribute to reduce the impedance of inland distance. In the case of the trade with East Asia, rail intermodal services affect all groups of flows both for imports and exports. Waterway connections have a much more significant impact on imports than on exports.

CONCLUSION

In this paper the geographical distribution of flows between French NUTS-3 regions and ports has been modeled. Using doubly and origin constrained models, we examined how distance and transport connections affect the port choice for flows of different value density. The major results of this study may be interpreted as follows:

First, it was shown that the friction associated to inland distance is valued more negatively when the value density of flows is low. For this group of flows, the distance constraint has even increased between 2008 and 2012. However for the other groups of flows, mostly containerized, distance is valued less negatively, and its impact has slightly diminished between 2008 and 2012. This shift is illustrative of the hinterland expansion of the largest container ports concentrating most of the calls of large container vessels. In view of the fast increase of vessel size in the recent years and the order books of shipping lines, this trend is expected to further port concentration.

Second, our study confirmed that the availability of intermodal connections to ports strongly attenuates the distance impedance. Quite surprisingly, the impact of inland waterways appears to be higher for cargo groups of high value density, and theoretically less sensitive to inland transport costs. Conversely, rail services has stronger impact on low value cargo than on the other groups. In the case of East-Asian trade, the contribution of intermodal connections is more significant on imports than on exports, and impacts are generally stronger when the value density of cargo is high. This has been demonstrated in aggregated fashion. To properly understand how intermodal connections contribute to change modal choice behavior, market areas of inland terminals should be studied in detail. Indeed, the relevance of intermodal transport for shippers can greatly vary depending on their location not just within a NUTS-3 region, but even between different locations within a large urban area ( [START_REF] Nierat | Market area of rail-truck terminals: pertinence of the spatial theory[END_REF].

Third, the characteristics of maritime supply at ports, in terms of frequency and vessel size, strongly affect the port choice behavior. In the case of imports from East-Asia, the sensitivity to frequency of services is positively correlated with the value of cargo. In the case of exports, there is no clear relationship between frequency and value. The fact of being called by large vessels has proven to be determinant in hinterland expansion, both for imports and exports. This confirms the relationship between the scale economies achieved in maritime transport with hinterland expansion. Between 2012 and 2017 the size of vessels on the trade Northern Europe -East Asia has increased from 9.2 to 15.6 thousand TEUs [START_REF] Toutain | Impacts of the crisis of liner shipping on secondary ports: The case of le havre[END_REF]. This has probably resulted in a further decrease of the inland distance impedance on the hinterlands of ports. For other deep sea routes, such North-South ones, the growth in vessel size has been more limited. To assess the impacts of these different evolutions on shippers, more research is needed, particularly through qualitative surveys on sectors highly dependent on deep sea transport. Also, such an analysis raises the complex issue of the benefits and disadvantages of distant sourcing.

This study showed that both geographical proximity and the quality of transport connections, have a strong influence on port choice, even in a developed country like France. In developing countries, where transport costs are much higher, their effect is expected to be stronger. Yet, in many developing regions, such in Africa or Latin America, contestable hinterlands are very limited, so port choice issues may not always be relevant. In Africa, significant investments have been done in the recent years to develop inland corridors to ports [START_REF] Pelletier | Benchmarking the integration of corridors in international value networks: the study of african cases[END_REF][START_REF] Fraser | A strategic appraisal of the attractiveness of seaport-based transport corridors: the southern african case[END_REF][START_REF] Dooms | Lions or gazelles? the past, present and future of african port authorities: The case of east africa[END_REF], eventually contributing to expand contestable hinterlands.

Furthermore, in view of the extant literature on port geography (Ng and Ducruet 2014), these results demonstrate that the ports chosen for deep sea flows could vary considerably depending, not just on the location of the shipper, but also on the overseas regions. Hence shippers are more likely to choose transport chains passing through ports with direct services or with higher frequency. Port authorities or terminal handling operators could then adopt different pricing strategies depending on the overseas regions they serve, in order to attract customers beyond the extent of their usual spheres of influence.

TABLES

FIGURESFigure 1 .Figure 2 .

 12 FIGURES

Table 1 .

 1 Results of a doubly constrained model. All Overseas regions. Author's calculations (2017) based on French Foreign trade data.

	Exports, 2008	Group 1 Group 2 Group 3 Group 4
	α Inland distance (Log) -1.433*** -1.3061*** -1.6609*** -1.3506***
		(0.1716)	(0.0809)	(0.1667)	(0.1154)
	Observations	1505	1129	753	941
	Exports, 2012	Group 1 Group 2 Group 3 Group 4
	α Inland distance (Log) -1.7841*** -0.9745*** -0.8857*** -0.6156***
	Observations	1787	1223	1317	1505
	Source:

Table 2 .

 2 Results of a doubly constrained model. All Overseas regions Imports, 2012 Group 1 Group 2 Group 3 Group 4 α Inland distance (Log) -1.6237*** -0.8505*** -0.5516*** -0.6777*** Author's calculations (2017) based on French Foreign trade data.

		(0.0634)	(0.0623)	(0.0896)	(0.0799)
	IW T ij	0.2227	0.8372*** 1.4753*** 1.0947***
		(0.1527)	(0.1069)	(0.1684)	(0.1217)
	RAIL ij	-0.3898	0.382**	0.3898**	-0.0026
		(0.2458)	(0.1606)	(0.1982)	(0.1706)
	Observations	1975	1505	1317	1303
	Exports, 2012	Group 1 Group 2 Group 3 Group 4
	α Inland distance (Log) -1.8566*** -1.0267*** -0.9127*** -0.6712***
		(0.0738)	(0.0955)	(0.077)	(0.0823)
	IW T ij	-0.234	0.6161*** 1.0382*** 0.8945***
		(0.164)	(0.154)	(0.1288)	(0.1383)
	RAIL ij	1.7614*** 0.5712**	0.4026** 0.9689***
		(0.2435)	(0.1931)	(0.1435)	(0.1643)
	Observations	1787	1223	1317	1505
	Source:

Table 3 .

 3 Results of an origin-constrained model. East Asia Imports, 2012 Group 1 Group 2 Group 3 Group 4 α Inland distance (Log) -1.1997*** -0.9982*** -0.8228*** -0.6166***

		(0.0631)	(0.0808)	(0.0914)	(0.1143)
	V F REQ j	0.0876*** 0.0923*** 0.1332*** 0.1898***
		(0.0137)	(0.0923)	(0.1332)	(0.1898)
	V SIZE j	0.0003** 0.0005*** 0.0005*** 0.0004***
		(0)	(0.0001)	(0.0001)	(0.0001)
	IW T ij	0.715*** 1.0946*** 1.504***	2.331***
		(0.1367)	(0.1682)	(0.1795)	(0.2087)
	RAIL ij	1.1326*** 0.8528*** 0.4397**	1.1915**
		(0.1453)	(0.1757)	(0.1968)	(0.3674)
	Observations	1505	931	941	802
	Exports, 2012	Group 1 Group 2 Group 3 Group 4
	α Inland distance (Log) -1.6355*** -1.4447*** -1.0773*** -0.745***
		(0.0817)	(0.1132)	(0.12)	(0.1248)
	V F REQ j	0.1259*** 0.086*** 0.0964*** 0.0853***
		(0.0189)	(0.0217)	(0.0226)	(0.0231)
	V SIZE j	0.0003** 0.0004*** 0.0006*** 0.0005***
		(0)	(0.0001)	(0.0001)	(0.0001)
	IW T ij	0.1043	-0.2879	0.421*	1.1791***
		(0.1827)	(0.2213)	(0.245)	(0.2422)
	RAIL ij	1.1614*** 2.6034*** 1.4051** 0.9741***
		(0.2166)	(0.1869)	(0.2287)	(0.2344)
	Observations	1129	820	901	713
	Source: Author's calculations (2017) based on French Foreign trade data.

ACKNOWLEDGMENTS

This research has been funded by Grand Port Maritime de Marseille (Port Authority of Marseilles), in the context of the project RP4F14138. The author thanks the Associate Editor, Thomas Kemeny, and the three anonymous referees for their valuable comments on the different versions of the paper. Special thanks go to Hidekazu Ito (Kwansei Gakuin University, Japan), Kenmei Tsubota (Institute of Developing Economies, Japan), Emmanuel Cohen, Martin Koning and Patrick Niérat (Ame-Splott, Ifsttar, France) for their feedback. The author remains sole responsible for the contents of this paper.


Sophie Lèbre

Olivier Gascuel

The combinatorics of overlapping genes

Keywords: double-coding sequences, genetic code, Stop codons, codon usage, amino-acid composition, linear and logical constraints, overlapping gene detection

Overlapping genes exist in all domains of life and are much more abundant than expected upon their first discovery in the late 1970s. Assuming that the reference gene is read in frame +0, an overlapping gene can be encoded in two reading frames in the sense strand, denoted by +1 and +2, and in three reading frames in the opposite strand, denoted by -0, -1, and -2. This motivated numerous researchers to study the constraints induced by the genetic code on the various overlapping frames, mostly based on information theory. Our focus in this paper is on the constraints induced on two overlapping genes in terms of amino acids, as well as polypeptides. We show that simple linear constraints bind the amino-acid composition of two proteins encoded by overlapping genes. Novel constraints are revealed when polypeptides are considered, and not just single amino acids. For example, in double-coding sequences with an overlapping reading frame -2, each Tyrosine (denoted as Tyr or Y) in the overlapping frame overlaps a Tyrosine in the reference frame +0 (and reciprocally), whereas specific words (e.g. YY) never occur. We thus distinguish between null constraints (YY = 0 in frame -2) and non-null constraints (Y in frame +0 ó Y in frame -2). Our equivalence-based constraints are symmetrical and thus enable the characterization of the joint composition of overlapping proteins. We describe several formal frameworks and a graph algorithm to characterize and compute these constraints. As expected, the degrees of freedom left by these constraints vary drastically among the different overlapping frames. Interestingly, the biological meaning of constraints induced on two overlapping proteins (hydropathy, forbidden di-peptides, expected overlap length …) is also specific to the reading frame. We study the combinatorics of these constraints for overlapping polypeptides of length 𝑛 , pointing out that, (i) except for frame -2, non-null constraints are deduced from the amino-acid (length = 1) constraints and (ii) null constraints are deduced from the di-peptide (length = 2) constraints. These results yield support for understanding the mechanisms and evolution of overlapping genes, and for developing novel overlapping gene detection methods.

Introduction

In the late 1970s, it was discovered that a single DNA sequence may code for several overlapping genes, that is, protein-coding genes sharing a common section of DNA sequence read in different frames. The genetic code associates a section of DNA sequence (comprised of four nucleotides: a, c, g, t) with a protein, which is a sequence of amino acids. Each sequence of three nucleotides or codon codes for an amino acid (among 20, denoted as A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, Y; see Tab. 1, provided for completeness). Thus, shifting the reading frame by one or two nucleotides results in a different protein. As DNA consists of two strands, up to six reading frames are possible for a given DNA sequence. Several notations have been used to refer to the various frames. We will use a simple notation in which the reference frame is denoted by +0 and the overlap reading frame is given by the number of shifted nucleotides, preceded by a plus "+" or minus "-" sign indicating whether the overlap occurs in the same or opposite direction, respectively (Fig. 1). For example, overlap in the opposite direction by shifting two nucleotides to the right is denoted by reading frame -2.

The first overlapping genes were discovered in viruses [START_REF] Barrell | Overlapping genes in bacteriophage φX174[END_REF]Fiddes and Godson 1979), but they are also known to be present in prokaryotic (in particular bacterial) and eukaryotic genomes. The existence of overlapping genes in bacterial genomes was strongly denied initially and, consequently, putative overlapping genes were excluded from annotation programs [START_REF] Warren | Missing genes in the annotation of prokaryotic genomes[END_REF]. Although experimental verification of two protein-coding genes in the same DNA sequence is challenging, an increasing number of overlapping genes have been identified in prokaryotes in recent years (for example, see [START_REF] Fellner | Phenotype of htga (mbia), a recently evolved orphan gene of escherichia coli and shigella, completely overlapping in antisense to yaaw[END_REF]. Overlapping genes are also present in vertebrates, in particular among de novo genes [START_REF] Makalowska | Birth and death of gene overlaps in vertebrates[END_REF]. It recently came to light that the number of overlapping genes could be greater than expected, particularly in the virus world. Examining the gene coordinates (from GenBank) available for virus sequences, [START_REF] Belshaw | The evolution of genome compression and genomic novelty in RNA viruses[END_REF] pointed out 819 instances of gene overlap among the 701 reference RNA virus genomes, with 56% of the viruses having at least one gene overlap. A recent study by [START_REF] Pavesi | Viral Proteins Originated De Novo by Overprinting Can Be Identified by Codon Usage: Application to the "Gene Nursery" of Deltaretroviruses[END_REF] assembled a dataset of 27 experimentally-identified overlapping genes longer than 140 nucleotides.

Gene overlap is thought to play a major role for increasing the coding space in genomes highly constrained for their maximum length [START_REF] Miyata | Evolution of overlapping genes[END_REF][START_REF] Sakharkar | Comparative study of overlapping genes in bacteria, with special reference to Rickettsia prowazekii and Rickettsia conorii[END_REF], notably in viruses [START_REF] Cassan | Concomitant Emergence of the AntiSense Protein Gene of HIV-1 and of the Pandemic[END_REF]. It has been shown to participate in gene regulation of functionally related proteins [START_REF] Normark | Overlapping genes[END_REF][START_REF] Cooper | Divergently transcribed overlapping genes expressed in liver and kidney and located in the 11p15.5 imprinted domain[END_REF][START_REF] Zheng | Computational identification of operons in microbial genomes[END_REF][START_REF] Wagner | Antisense RNAs in bacteria and their genetic elements[END_REF]. Gene overlap also seems to be involved in the creation of new genes, or "overprinting" [START_REF] Keese | Origins of genes: "big bang" or continuous creation?[END_REF], particularly in viruses [START_REF] Pavesi | Viral Proteins Originated De Novo by Overprinting Can Be Identified by Codon Usage: Application to the "Gene Nursery" of Deltaretroviruses[END_REF], but also in the human genome [START_REF] Knowles | Recent de novo origin of human protein-coding genes[END_REF]. In addition, overlapping coding regions could represent a process with the beneficial effect of limiting the evolution of these regions in viral genomes [START_REF] Simon-Loriere | The effect of gene overlapping on the rate of RNA virus evolution[END_REF]. Indeed, the evolution of double-coding nucleic acid sequences is highly constrained, as any mutation affects both genes and may affect both associated proteins. Overlapping coding regions in viruses could thus represent favorable therapeutic targets, where viruses have less freedom to escape drug effects.

The first mathematical analyses of this double-coding were published in the early 1980s [START_REF] Sander | Degeneracy of the information contained in amino acid sequences: evidence from overlaid genes[END_REF]Schultz 1979, Siegel and[START_REF] Siegel | Degeneracy when DNA codes for overlapping genes[END_REF][START_REF] Smith | Protein constraints induced by multiframe coding[END_REF]. As the genetic code is degenerated (18 of the 20 amino acids are encoded by several codons, Tab. 1), it is possible to measure the information contained in the amino acid sequence encoded by a gene in the reference frame with respect to possible overlapping genes in the five other reading frames. These theoretical considerations, based in particular on information theory, have shown that the five possible overlapping reading-frame configurations differ significantly in their coding flexibility and thus in their information content. In particular, frame -2 is highly constrained and thus expected to be "very rare in nature" [START_REF] Smith | Protein constraints induced by multiframe coding[END_REF]. However, the existence of overlapping genes in the anti-sense reading frame -2 has been suggested in several viruses. For example, in HIV-1, [START_REF] Miller | Human immunodeficiency virus may encode a novel protein on the genomic DNA plus strand[END_REF] discovered a long Open Reading Frame of ~185 codons overlapping the env gene in frame -2, and named it the "AntiSense Protein" (ASP) gene. The existence and function of ASP are still controversial, but several pieces of evidence argue in favor of this hypothesis (see [START_REF] Torresilla | Reviving an old HIV-1 gene: the HIV-1 antisense protein[END_REF] for a review, and two recent studies showing an immune response in vivo: [START_REF] Berger | Immune Screening Identifies Novel T Cell Targets Encoded by Antisense Reading Frames of HIV-1[END_REF][START_REF] Bet | The HIV-1 Antisense Protein (ASP) induces CD8 T cell responses during chronic infection[END_REF]. Moreover, we demonstrated [START_REF] Cassan | Concomitant Emergence of the AntiSense Protein Gene of HIV-1 and of the Pandemic[END_REF]) that a strong selection pressure acts to maintain the ASP ORF in the group M of HIV-1, which is responsible for the human pandemic. Interestingly, out of the 819 pairs of overlapping genes pointed out in viruses by [START_REF] Belshaw | The evolution of genome compression and genomic novelty in RNA viruses[END_REF], +1 frameshifts are significantly more frequent than +2 frameshifts, while these two same sense overlaps are comparable regarding information theory predictions [START_REF] Smith | Protein constraints induced by multiframe coding[END_REF]. [START_REF] Belshaw | The evolution of genome compression and genomic novelty in RNA viruses[END_REF] proposed several possible explanations for this difference, notably related to codon usage. Specific evolutionary models have been developed for DNA sequences encoding two overlapping genes (e.g. [START_REF] Hein | A maximum-likelihood approach to analyzing nonoverlapping and overlapping reading frames[END_REF][START_REF] Krakauer | Stability and evolution of overlapping genes[END_REF][START_REF] Pedersen | A dependent-rates model and an MCMC-based methodology for the maximum-likelihood analysis of sequences with overlapping reading frames[END_REF], and more recently for detecting selection pressure specific to double-coding (e.g. [START_REF] Sabath | A Method for the Simultaneous Estimation of Selection Intensities in Overlapping Genes[END_REF], 2011[START_REF] Pavesi | Viral Proteins Originated De Novo by Overprinting Can Be Identified by Codon Usage: Application to the "Gene Nursery" of Deltaretroviruses[END_REF][START_REF] Simon-Loriere | The effect of gene overlapping on the rate of RNA virus evolution[END_REF][START_REF] Firth | Mapping overlapping functional elements embedded within the protein-coding regions of RNA viruses[END_REF][START_REF] Mir | Selection Pressure in Alternative Reading Frames[END_REF]Schober, 2014, Wei and[START_REF] Wei | A Simple Method for Estimating the Strength of Natural Selection on Overlapping Genes[END_REF]. However, little has been done to evaluate the interdependent constraints elicited by the overlap on the amino-acid sequence of the associated proteins. Some studies reported that overlapping protein regions are enriched in amino acids with high codon degeneracy [START_REF] Pavesi | On the informational content of overlapping genes in prokaryotic and eukaryotic viruses[END_REF] -that is, Arginine (R), Leucine (L) and Serine (S), which are encoded by six differing codons -and that they often respectively encode a cluster of either basic or acidic amino acids [START_REF] Pavesi | Detection of signature sequences in overlapping genes and prediction of a novel overlapping gene in hepatitis G virus[END_REF]. More recently, [START_REF] Rancurel | Overlapping Genes Produce Proteins with Unusual Sequence Properties and Offer Insight into De Novo Protein Creation[END_REF] showed a significant bias towards structural disorder, that is, the lack of a rigid 3D structure for protein regions encoded by genes overlapping in the same sense (frame +1 or +2).

In this paper, we study constraints (and their combinatorics) acting on the composition of two overlapping proteins. First, their amino-acid composition is subject to specific constraints depending on the overlapping frameshift. For example, a Tyrosine (Y) in reading frame -2 always overlaps with a Tyrosine in the reference frame, and reciprocally. More constraints appear when considering the protein composition in terms of di-peptides. In particular, some constraints reveal "forbidden" di-peptides, that is di-peptides that never occur in one frame (reference or overlap), as it would necessarily induce a Stop codon in the other frame (e.g. YY in frame -2). The biological meaning of these results is discussed, yielding support for understanding the mechanism of overlapping genes and for developing overlapping gene detection methods. After introducing notation and first results in section 2, we propose a graph traversal algorithm for deriving a set of frameshift specific constraints in terms of amino-acid composition in Section 3. Di-peptide constraints are analyzed in Section 4 and generalization to 𝑛peptides is given in Section 5. [START_REF] Firth | Detecting overlapping coding sequences in virus genomes[END_REF], SW [START_REF] Smith | Protein constraints induced by multiframe coding[END_REF], K [START_REF] Krakauer | Stability and evolution of overlapping genes[END_REF], R [START_REF] Rogozin | Purifying and directional selection in overlapping prokaryotic genes[END_REF].

Notations and first results

Overlapping frame reciprocity

Reciprocity underlies the various overlapping frames and is specific to the direction of the overlap. When considering overlap in the same direction, the second reading frame (+1 or +2) depends on the sequence chosen as the reference (frame +0). If a sequence x' overlaps a reference sequence x with frame +1, then, in turn, sequence x overlaps sequence x' with frame +2. For the three types of overlap occurring in the opposite direction (-0, -1 or -2), the overlapping reading frame with respect to the reference frame is the same regardless of the sequence chosen as the reference (e.g., reading sequence x in frame +0 and x' in frame -1 leads to the same overlap as reading x' in frame +0 and x in frame -1). Although very simple to derive from observing the five overlapping reading frames (Fig. 1), these reciprocity properties are important, as they generate symmetries among the constraints induced on proteins coded by overlapping genes.

Quadons

Overlap in the opposite strand without shifting (i.e. frame -0) is a particular case where the two overlapping codons fully overlap: sites 1, 2, 3 in the reference frame respectively match sites 3, 2, 1 in the overlap. When considering overlap with shifting (frame +1, +2, -1 or -2, Fig. 1), the overlapping codons only have two DNA bases in common. Thus, a suite of four nucleotides is required for a complete description of two overlapping codons. A tetra-nucleotide or "quadon", taken at a chosen position in the sequence, describes exactly one codon in each reading frame. Both the starting site of a quadon describing two overlapping codons, and the reading frames of the two overlapping codons inside the quadon, are specific to the type of overlap. To simplify reading, we use an explicit notation (derived from [START_REF] Rogozin | Purifying and directional selection in overlapping prokaryotic genes[END_REF] for quadons and the corresponding codons. For example, if we assume the quadon sequence in the reference frame is acat, then we have the following overlapping pairs of quadons in each frame (remember that in DNA double helix, the reverse complement is defined by the nucleotide pairs a↔t and c↔g):

Frame +1 acat/acat Frame +2 acat/acat Frame -1 acat/atgt Frame -2 acat/atgt where bold and italic letters are used for the reference and the overlap, respectively; both codons are underlined and read from left to right.

Fewer Stop codons in frame -2

From the genetic code (Tab. 1), a Stop codon can be encoded by three codons taa, tag, and tga. Thus, for each of the two overlapping reading frames, 12 differing quadons include a Stop (three possible Stop codons times four possible nucleotides for the remaining letter of the quadon), totaling 24 quadons that are never observed in double-coding sequences. However, in frame -2 and only in that frame, two Stop codons may overlap (themselves or each other): taa and tag. This leads to four "double Stop" quadons denoted using the above-defined notation as ttaa/ttaa, ctaa/ttag, ttag/ctaa, and ctag/ctag. Therefore, only 20 quadons are not observable in frame -2. Moreover, the absence of a Stop codon in the reference frame reduces the probability of observing a Stop in the overlapping frame -2. As only half of the ta* codons are permitted in the reference frame (" * " represents any nucleotide; tat and tac are permitted, whereas taa and tag are forbidden), the frequency of taa and tag Stop codons should be divided by two in frame -2, compared to other frames, assuming uniform codon usage. Consequently, the probability of long open reading frames (part of a reading frame that contains no Stop codon) is increased in frame -2, compared to other frames. Such findings are indeed observed in gene coding sequences. For example, in HXB2 (the first discovered strain of HIV, Barré-Senoussi et al. (1983), [START_REF] Ratner | Complete nucleotide sequence of the AIDS virus, HTLV-III[END_REF]), Stop codons in the non-overlapping coding regions are much less frequent in frame -2 (2.5% of the codons) than in the other frames (5.5%, 5%, 10.5%, and 7.5% in frames -1, -0, +1, and +2, respectively). An additional factor explaining these striking frequency differences could be that the presence of Stop codons is positively selected in sense frames +1 and +2, to interrupt translation quickly in case of an erroneous frameshift. [START_REF] Seligmann | The ambush hypothesis: hidden stop codons prevent offframe gene reading[END_REF] suggested that particular codon usage biases have evolved so as to increase the frequency of Stop codons in unused ORFs and hence reduce the wastage caused by the translation of accidentally frameshifted genes (see also [START_REF] Cusack | Preventing Dangerous Nonsense: Selection for Robustness to Transcriptional Error in Human Genes[END_REF] for such results in the human genome). Hence gene overlap probability depends strongly on codon usage [START_REF] Belshaw | The evolution of genome compression and genomic novelty in RNA viruses[END_REF]) in particular through the Stop codon frequency in all the reading frames. Moreover, GC-rich genomes reduce the chance for spurious Stop codons in any frame, as Stop codons are made essentially of a and t nucleotides. HXB2 strain is AT-rich (57.4% of a and t); this is an additional factor to explain the high frequencies of Stop codons.

Amino-acid composition constraints

Two proteins encoded by overlapping genes are subject to amino-acid composition constraints which result directly from the genetic code. For example, with frame -2, two overlapping proteins are subject to the constraint that amino acids C or W in the reference frame are necessarily overlapped by amino acids H or Q in the overlapping frame -2, and reciprocally. We denote this constraint as:

(reference frame) C + W ó H + Q (overlapping frame -2)
where the left, bold part of the constraint corresponds to the reference frame, and the italic part on the right, to the overlapping frame -2. Figure 2 illustrates the derivation of this constraint from quadons. Such amino-acid composition constraints can be interpreted as logical equivalences, where + stands for "or": in double-coding sequences, amino acid C or W in the reference frame overlaps with either amino acid H or Q in frame -2, and reciprocally. They can also be read in terms of frequency equalities as the number of occurrences of amino acids C and W in the reference frame equals the number of occurrences of H and Q in the overlapping frame -2. Note that due to reciprocity, the relation ó is symmetric in frame -2 and relation H + Q ó C + W also holds.

(B) atgc atgt gtgc gtgt ctgc ctgt ttgc ttgt atgg gtgg ctgg ttgg

C 1 1 1 1 1 1 1 1 0 0 0 0 W 0 0 0 0 0 0 0 0 1 1 1 1 H 1 1 1 1 0 0 0 0 1 1 0 0 Q 0 0 0 0 1 1 1 1 0 0 1 1

Deriving amino---acid composition constraints

In order to study the combinatorics of these logical constraints in overlapping proteins, we use a graph-based approach for listing the constraints exhaustively (not only for single peptides, but also for 𝑛-peptides, as described in the following sections). Codon overlap is only partial, except for the reading frame -0 (opposite overlap without shifting). This generates codon dependency along the sequence, as each amino acid read in one frame overlaps with two codons in the other frame. This aspect will become apparent when examining constraints that apply to polypeptides (Sections 4 and 5). In this section, we consider constraints that apply to single amino acids (or mono-peptides).

Graph traversal algorithm

The amino-acid constraints are a direct consequence of the genetic code, and they can be derived efficiently from a tri-partite graph, where the three types of vertices are: (i) the amino acids read in the reference frame, (ii) the quadons, and (iii) the amino acids read in the overlapping frame. Each quadon is linked by an edge to exactly one amino acid in the reference frame and one amino acid in the overlap. The tri-partite graph defined in this manner is frame-specific, as the two amino acids encoded by a given quadon depend on the overlapping reading frame (see the illustration with quadon acat in Section 2). The tri-partite graph for frame -0 is similar, but uses codons instead of quadons.

To obtain an exhaustive list of amino-acid constraints, we leverage the fact that each connected component (i.e. maximal sub-graph in which any two vertices are connected to each other by paths) in the full tri-partite graph (including the 4 4 possible quadons) defines an irreducible equivalence constraint, binding a set of amino acids in the reference frame with a set of amino acids in the overlapping frame. For example, Figure 2 describes the connected component associated with the amino-acid constraint C + W ó H + Q occurring in frame -2.

We implemented a graph traversal algorithm for finding the set of all of these connected components and thus listing the corresponding irreducible amino-acid constraints. The search begins at a chosen amino acid, finds the set of amino acids included in the connected component containing this amino acid, and then returns the associated amino acid constraint. Our algorithm is outlined in Figure 3. In order to find all the connected components of the graph, we loop through the 20 amino acids in the reference frame, starting a new search whenever the loop reaches an amino acid that has not already been included in a previously-found connected component. This algorithm is similar to conventional graph traversal algorithms allowing the computation of connected components in linear time in terms of the number of edges in the graph (Hopcroft and Tarkan, 1973), that is, here, twice the number of quadons in the tri-partite graph (see Figure 2). This graph traversal algorithm is easily extended to polypeptides by replacing quadons (four nucleotides) with "heptons" (seven nucleotides) for di-peptides and, more generally, by DNA words of length 3𝑛 + 1 for 𝑛-peptides. This algorithm is implemented in the R package DCODE available from the CRAN: https://cran.r-project.org/web/packages/DCODE.

Other frameworks may be used to derive these constraints. Using a linear algebraic approach, graph connectivity is described by an adjacency matrix of size 40 (total number of amino acids in both frames, reference and overlap) times the number of quadons (4 4 ). From graph theory, the adjacency matrix has rank 40 -c, where c is the number of connected components of the graph (for instance, see (Biggs 1993), p.25). Each connected component corresponds to a set of linearly dependent rows of the adjacency matrix (see Fig. 2 for an illustration with constraint C + W ó H + Q in frame -2). Finding the connected components comes down to finding the null linear combinations of the rows of the adjacency matrix. This approach works nicely for deriving amino-acid constraints, but requires more computations than a single graph traversal algorithm, in particular when increasing the length of the overlapping peptides.

A ó A (1) Y (+ Stop) ó Y (+ Stop) (2) G ó P (3) P ó G (4) T ó V (5) V ó T (6) H + Q ó C + W (+ Stop) (7) C + W (+ Stop) ó H + Q (8) I + M ó I + M (9) + Trivial constraint: D + E + F + K + L + N + S + R ó D + E + F + K + L + N + S + R (10) --0 F + L ó E + K + Q (+ Stop) (1) E + K +Q (+ Stop) ó F + L (2) I + M + V ó D + H + N + Y (3) D + H + N + Y ó I + M + V (4

) + Trivial constraint: A + C + G + P + R + S + T + W (+ Stop) ó A + C + G + P + R + S + T + W (+ Stop)

(5) +1

D + H + N + Y ó I + M + T (1) + Trivial constraint: A + C + E + F + G + I + K + L + M + P + Q + R + S + T + V+ W (+ Stop)

ó A + C + D + E + F + G + H + K + L + N + P + Q + R + S + V + W + Y (+ Stop) (2)
+2

I + M + T ó D + H + N + Y (1) + Trivial constraint: A + C + D + E + F + G + H + K + L + N + P + Q + R + S + V + W + Y (+Stop) ó A + C + E + F + G + I + K + L + M + P + Q + R + S + T + V+ W (+ Stop)

(2)

--1 Trivial constraint only: All amino acids (+ Stop) ó All amino acids (+ Stop)

(1)

Table 2: Amino-acid constraints for the five overlapping frames. For the sake of completeness, we also indicate the locations at which the Stop codons may occur; for example, in frame -2, a Stop codon may overlap a Y (Tyrosine). The overlap with reading frame -2 shows the greatest number (10) of constraints and includes the most specific ones, whereas frame -1 is subject to a unique, trivial constraint. The four major constraints in frame -0 oppose strongly hydrophobic amino acids (blue) in one frame to strongly hydrophilic amino acids (green) in the other frame, that is [START_REF] Kyte | A simple method for displaying the hydropathic character of a protein[END_REF] hydropathy index within brackets): L (3.8) and F (2.8) overlap Q (-3.5), E (-3.5) and K (-3.9) in Constraints (1, 2); whereas I (4.5), V (4.2) and M (1.9) overlap Y (-1.3), H (-3.2), D (-3.5), and N (-3.5) in Constraints (3, 4).

Amino-acid constraints list

The exhaustive list of the frame-specific amino-acid constraints obtained with our graph traversal algorithm is provided in Table 2. As expected, the overlap with reading frame -2 shows the greatest number of constraints (10) and includes the most specific constraints (i.e., binding the most restricted subsets of amino acids). Six constraints describe a single amino acid overlap: each Alanine (A) in the overlapping frame overlaps an Alanine in the reference frame +0 (and reciprocally); similarly, the Tyrosine (Y) amino acids necessarily overlap themselves; while amino acids Glycine (G) and Proline (P) (resp. Threonine (T) and Valine (V)) overlap each other. The latter is a strong constraint, as Glycine is frequent in standard proteins (the 3 rd most frequent amino acid [START_REF] Eitner | Statistical distribution of amino acid sequences: a proof of Darwinian evolution[END_REF]) in proteins from the UniProt TREMBL database), whereas Proline is established as a potent breaker of both alpha-helical and beta-sheet protein structures, and is among the least frequent amino acids in proteins (the 12 th most frequent). At the amino acid scale, the number of constraints for the other types of overlap is more limited: frame -0 overlap is subject to 5 amino-acid constraints; same sense overlaps (frame +1 and +2) are subject to two amino-acid constraints; and frame -1 is only subject to a unique, trivial constraint. Note that this trivial constraint holds true in all frames given that a double-coding sequence has the same number of amino acids in each frame (reference and overlap). However, in all the frames except frame -1, this trivial constraint can be reduced. Hence, the number of effective constraints within each overlapping frame is better viewed as the total number of constraints minus one (nine effective constraints in frame -2, four in frame -0, only one in frames +1 and +2, and none in frame +1). Moreover, we (unfairly) call the largest constraint of each frame the "trivial" constraint (Tab. 2).

Most of the (numerous) constraints in frame -2 are interpreted easily. The first two letters in this frame (on their own almost sufficient to determine an amino acid) of a codon in the reference also face the first two letters of the codon in the overlap. Thus, the 2 nd and 3 rd letters of a quadon restrict the possibilities to only one or two amino acids in both the reference and the overlap. For example, the constraint C + W ó H + Q (Fig. 2) is derived from the set of quadons with form xtgy/ycax, where x and y represent any of the four nucleotides, and x, y are their reverse complements; moreover, codon tgy in the reference reading frame and codon cax in the overlap respectively code for {C, W or Stop} and {H or Q} (Tab. 1). Another simple example is A ó A (Constraint (1)), which is induced by the quadons with the form xaty/yatx. Again, the set of quadons with the form xtay/ytax induces Y(+Stop) ó Y(+Stop) (Constraint (2)). However, Constraint (10) includes more amino acids, due to the fact that some of them, namely L, R and S, are encoded by codons starting with two different di-nucleotides, and not only ones such as C, W, H, Q, A, Y in our previous examples. For example, both codons cty and tty may code for L (Tab. 1). Consequently, we obtain a much larger connected component in the tri-partite graph. The same holds for the other frames. In particular, in frame -1, the 2 nd and 3 rd codon positions face each other in both strands. Thus a larger number of amino acids corresponds to any codon with a given di-nucleotide in 2 nd and 3 rd positions (e.g. xtt may code for F, L, I, or V, depending on nucleotide x). Hence, we obtain a unique, global connected component in the graph, defining a unique, trivial amino-acid constraint.

Each of our constraints (Tab. 2) is a logical equivalence resulting from a set of implications. Obviously, each implication may yield information that is more specific. For example, we have 5 implications in frame -0:

F ⇒ E+K, L ⇒ E + K + Q + Stop, F + L ⇐ E, F + L ⇐ K, L ⇐ Q,
which we summarize by the equivalence (Constraint (1) in frame -0):

F + L ó E + K + Q + Stop.
This constraint thus divides into implications that are more specific. The consequent set can be reduced for some antecedent sets (e.g. when considering the antecedent F in the reference frame, we have F ⇒ E+K and the consequent set in the overlap does not include Q or Stop). However, this division of our equivalence constraints only occurs for the amino-acid constraints in frame -0, and for the largest "trivial" equivalence constraint of each frame (Tab. 2). Indeed, the effective ("non-trivial") constraints in all frames except -0 are based on implications in which the consequent set is not reduced (e.g. Constraint (8) in frame -2 (Tab. 2, Fig. 2) results from:

C ⇒ H + Q, W ⇒ H + Q, C + W ⇐ H and C + W ⇐ Q).
Compared to implications, our equivalence constraints summarize the information in terms of joint amino-acid composition of two overlapping protein regions. This offers the advantage of giving a compact, comprehensive representation of information, which can be interpreted easily. For example, an overlap in frame -0 generates specific biochemical constraints in terms of hydropathy. Indeed, constraints (1-4) in frame -0 oppose strongly hydrophobic amino acids to strongly hydrophilic amino acids (Tab. 2). These four constraints include most of the amino acids with strong hydropathic properties (e.g. L (3.8) and F (2.8) overlap Q (-3.5), E (-3.5), and K (-3.9), where the numbers in parentheses correspond to the [START_REF] Kyte | A simple method for displaying the hydropathic character of a protein[END_REF] hydropathy index). Consequently, the alternations of hydrophilic and hydrophobic amino acid stretches (which form the very basis of protein structures) in two proteins overlapping in frame -0 strongly depend on one another. For example, assuming a membrane protein being encoded on one strand, that is, a highly hydrophobic protein, we will see a highly hydrophilic protein on the other strand, typically a disordered protein with long, exposed stretches of amino acids.

Di-peptide constraints and dependency between successive codons

Absence of dependency in frame -0

Most di-peptide constraints result from the combination of two amino-acid constraints. This is obviously the case in frame -0, as the positions of two overlapping codons fully match. Thus, every di-peptide (and n-peptide) constraint corresponds to the combination of two (n) amino-acid constraints. For example, the combination of amino-acid Constraints (1) and ( 3) in frame -0 (Tab. 2), leads to four di-peptide constraints, depending on the ordering of the two amino-acid constraints:

(F + L) (F + L) ó (E + K + Q) (E + K + Q) (F + L) (I + M + V) ó (D + H + N +Y) (E + K + Q) (I + M + V) (F + L) ó (E + K + Q) (D + H + N +Y) (I + M + V) (I + M + V) ó (D + H + N +Y) (D + H + N +Y)
As the di-peptide in the reference frame (bold letters) and the overlap (italic letters) are read in opposite directions, the combination of the two amino-acid constraints is obtained by concatenating the amino acids from the part and from the left part of the constraints in opposite order ((1, Left) (3, Left) ó (3, Right) (1, Right) and reciprocally). Moreover, the product notation denotes letter concatenation and thus the factor ordering matters. For example, (F + L) (I + M + V) describes the set of six di-peptides obtained by concatenating F or L (first) with I, M, or V (second). Hence, overlapping proteins in frame -0, subject to 5 amino-acid constraints (Tab. 2), are subject to 5 & di-peptide constraints, but no information is added in practice, compared to the 1-peptide analysis.

Extension of the graph traversal algorithm

In all overlapping reading frames except -0, the constraints cannot be derived in a straightforward manner from the amino-acid constraints due to the dependencies between successive overlapping codons (each codon overlaps two codons in the shifted reading frame). Clearly, the constraints resulting from the combination of two amino-acid constraints still hold, but they may be decomposed into subconstraints (when corresponding to several, different, connected components in the tri-partite graph for di-peptides). To compute these constraints, we thus launched the extension of our graph algorithm (Fig. 3) using "heptons". The total numbers of di-peptide (and amino-acid) constraints for all frameshifts are given in Table 3. The additional constraints exist mainly because some di-peptides induce a Stop codon in the alternative reading frame systematically and thus are forbidden in an overlapping context. However, other constraints also appear in frame -2, and only in that frame. We discuss these two types of additional constraints in the following sub-sections.

Additional "null" constraints for the di-peptides inducing Stop codons in the overlap

In most overlapping frames, some di-peptides induce a Stop codon in the alternative reading frame systematically. Whichever codon is used for coding each of the two successive amino acids, the overlap is necessarily a Stop codon. Such di-peptides cannot be observed in a double-coding region with this frameshift, thus generating what we call "null" constraints. For example, the di-peptide YY in the reference frame necessarily generates a Stop codon in the overlap with frame -2. Indeed, whichever codon is used for coding each Y (tat or tac), the overlapping codon in frame -2 is either taa or tag, that is, a Stop codon. Then YY is never observed in a coding sequence with an overlapping gene in frame -2. Due to the reciprocity of frame -2 (Section 2), the absence of YY is also true for the overlapping frame. The set of forbidden di-peptides for each frame is given by the set of isolated di-peptides in the associated tri-partite graph (as a forbidden di-peptide is always overlapped by a Stop). Our graph traversal algorithm allows us to quickly identify the exhaustive set of forbidden di-peptides for all frames (null constraints in Tab. 3); we then find connected components with only one di-peptide on one side (reference or overlap). The reciprocity of the reference and overlap frames (Section 2) induces reciprocity of the null constraints. In total for frame -2, six di-peptides necessarily code for a Stop codon in the overlapping frame: CY, DY, FY, HY, NY, YY, which results in 12 "null" constraints, implying the absence of these di-peptides in both strands. A particularity of frame -0 is that none of the di-peptides is overlapped by a Stop codon systematically, and thus no null-constraint is found. For same sense overlaps, none of the di-peptides in the overlap with frame +1, or in the reference for frame +2, induces a Stop systematically in the other overlapping frame, and we only have five null-constraints, without reciprocity.

Di-peptides in Table 3 are special in that they impose Stop codons in alternative reading frames and are thus forbidden in an overlapping context. This notion of forbidden di-peptide is based on simple considerations that are directly from code. However, to the best of our knowledge, this notion and the lists of the di-peptides forbidden in frame-specific overlapping contexts have not been suggested before in the large body of literature dedicated to overlapping genes. In addition, several authors (e.g. [START_REF] Cusack | Preventing Dangerous Nonsense: Selection for Robustness to Transcriptional Error in Human Genes[END_REF]) have shown that Stop codons are more frequent than expected in alternative reading frames, in order to limit the translation of accidentally frameshifted transcripts. We thus expect that these forbidden di-peptides could be favored in regions that are free of gene overlap. Table 3: Mono-and di-peptide constraints for each overlapping frame. We provide the number of constraints and list of the "forbidden" di-peptides (inducing a Stop codon in the overlapping frame). For each frame, except frame -0 where the codons fully overlap, the number of di-peptide constraints is greater than the square of the number of amino-acid constraints. The bold numbers refer to the number of additional di-peptide constraints that cannot be derived from the amino-acid constraints: additional "non-null" constraints for frame -2 only, and additional "null" constraints for all frames except frame -0. The last two columns list the forbidden di-peptides corresponding to "null" constraints in the reference and overlap frames.

Frame

Monopeptide

Di-peptide

Additional "non-null" constraints in frame -2 only

Based on the results of our graph algorithm (Tab. 3), it turns out that for all overlapping frames except frame -2, the set of di-peptide constraints is given exactly by the ordered combination of two aminoacid constraints, plus the null constraints generated by the "forbidden" di-peptides. In frame -2, the codon dependency also generates novel "non-null" di-peptide constraints, which cannot be derived from the amino-acid constraints. For example, the constraint SY ó Y (D+E) existing in frame -2 (see Appendix), cannot be deduced from constraints for amino acid S and Y (constraints ( 10) and (2) in Tab.

2) as amino acid S is included in the large constraint (10) involving eight amino acids in each frame.

Actually, the ordered combination of constraints ( 10) and ( 2) in frame -2, leads to two di-peptide constraints:

SY ó Y (D+E) (E+K+L+R) Y ó Y (F+K+L+N+R+S)
while the simple ordered combination would produce one single constraint:

(D + E + F + K + L + N + S + R) Y ó Y (D + E + F + K + L + N + S + R)
Clearly, this latter constraint is valid, but it is subdivided into the two preceding constraints, which have been simplified by accounting for null constraints with di-peptides DY, FY, and NY (Tab. 2). The complete list of the additional "non-null" constraints in frame -2 (which cannot be derived from the amino-acid constraints) is given in Appendix A. This decomposition was expected for frames where the codons do not fully overlap, that is, all frames except -0. Indeed, the amino-acid constraints are derived from the quadons where only two nucleotides (sites 2 and 3 of the quadon) are constrained, whereas the nucleotides at both ends of the quadon (sites 1 and 4) are kept free as they are involved in only one codon (either in the reference or in the overlap). When considering di-peptides, the constraints are induced by the overlap of two codons, that is, "heptons", where five nucleotides (sites 2 to 6) are constrained, instead of four (2x2) with the two corresponding quadons. Thus di-peptide would be expected to generate more specific constraints than amino-acid overlap. Surprisingly, our results (Tab. 3) show that this expectation occurs only in frame -2. In the other overlapping frames with shifting {-1, +1, +2}, the "non-null" di-peptide constraints simply correspond to the ordered combinations of two amino-acid constraints. Thus, the analysis of the non-null di-peptide constraints in frames {-1, +1, +2} brings no practical contribution as they can be deduced directly from the amino-acid constraints. Analysis of the non-null di-peptide constraints only matters for frame -2, where the dependence structure brings up rules at level 2 (dipeptides) which are not deduced from level 1 (amino acids). In the next section, we shall see that the same is found with 𝑛-peptides, 𝑛 > 2.

What about higher length peptides?

Counting the 𝑛-peptide null constraints For all frames, the peptides of length 𝑛 inducing a Stop codon in the alternative coding sequence are simply those containing a "forbidden" di-peptide (Tab. 3). Hence, the number of null constraints for 𝑛peptides is computed recursively from the list of forbidden di-peptides for each frame. Using the recursive formula, we easily derive a closed formula to count the null constraints associated with that frame. Again, we will detail these calculations with frame -2, but the approach is similar for the other frames (detailed in Appendix B).

Let us denote by 𝐴 9 the set of "allowed" peptides of length 𝑛, that is, those not containing any forbidden di-peptide in the reference frame. Due to reciprocity, this set of allowed 𝑛-peptides is the same in the overlap frame. The set of di-peptides inducing a Stop codon in the overlapping frame -2 is {CY, DY, FY, HY, NY, YY} (Tab. 3). The set 𝐴 9 can be divided into two disjoint subsets: 𝐴 9 = 𝐴 9,; ∪ 𝐴 9,9=/{;} where 𝐴 9,; is the subset containing the allowed 𝑛-peptides ending with amino acid Y, and 𝐴 9,9=/{;} is the subset made of the allowed 𝑛-peptides ending with any amino acid except Y. The subset 𝐴 9,9=/{;} contains exactly the set of allowed (𝑛 -1)-peptides suffixed with an amino acid different from Y, as suffixing one of the 20 -1 amino acids different from Y will not generate a forbidden di-peptide (necessarily ending with amino acid Y). Thus, 𝐴 9,9=/{;} has size (20 -1) 𝐴 9A# , where . denotes cardinality. The subset 𝐴 9,; contains the elements of the subset 𝐴 9A#,9=/{C,D,E,F,G,H} of allowed (𝑛 -1)peptides ending with any amino acid except {C, D, F, H, N, Y}, suffixed with amino acid Y. In turn, 𝐴 9A#,9=/{C,D,E,F,G,H} is made of the allowed (𝑛 -2)-peptides suffixed with any amino acid except {C, D, F, H, N, Y} and thus sizes (20 -6) 𝐴 9A& . Then the total number of allowed 𝑛-peptides in frame -2 (reference or overlap) is computed recursively as follows:

𝑘 # = U V AW V U X W X W X AW V ≈ 1.014; 𝑘 & = U X AY X W X W V ≈ -0.014;
The total number of null constraints in frame -2 is thus equal to 2× 20 9 -𝐴 9 , where factor 2 accounts for the two frames (reference and overlap). Given that the absolute value of 𝑟 & is lower than 1, the number 𝐴 9 of allowed 𝑛-peptides in each frame is approximated for large values of 𝑛 by 𝐴 9 ~ 𝑟 # 9 , and consequently the number of forbidden 𝑛-peptides by 2 20 9 - 𝑟 # 9 . Similar computations yield recursive and closed formulae for the number of null constraints in the other frames, which are summarized in Table 4 (see Appendix B for details). Note that the total number of null constraints (including reference and overlap) equals 2× 20 9 -𝐴 9 for anti-sense overlap (frames -2 and -1), whereas it equals 2×20 9 -𝐴 9 for same sense overlap (frames +1 and +2), as forbidden peptides appear in only one of the two alternative frames (Tab. 3).

A consequence of these results is that the fraction of allowed 𝑛-peptides converges to 0 when 𝑛 grows to infinity. This result holds true for the reference frame with frame +1, the overlapping frame with frame +2, and for both frames with frames -2 and -1. This finding is interpreted easily: the longer the sequence, the more likely it is that it will contain a forbidden di-peptide. Moreover, the probability of finding an allowed/forbidden 𝑛-peptide for a given frame is computed easily using our formulae. This may form the basis for a quick and simple method to detect overlapping regions within proteins. For example, assume a window of size 𝑛 = 200, and consider frame -2: if this window contains a forbidden di-peptide {CY, DY, FY, HY, NY, YY}, then this is not an overlapping region. Oppositely, if the window does not contain any forbidden di-peptides, the probability (under a simple model, with uniform amino-acid frequencies) of observing such a 200-peptide is of |U V^^| &_ V^^≈ W X &_ &__ ≈ 0.05, thus providing significant support that the window does correspond to an overlapping region in frame -2. This approximation could be refined by incorporating realistic amino-acid frequencies and/or codon usage statistics in probability computations. This method could be used as a first filtering step, for example to scan the very large existing protein databases quickly (e.g. The UniProt Consortium, 2015). Clearly, another option involves using the genes encoding these proteins directly, and checking for the absence of Stop codons at the DNA level in the alternative reading frames. At this point in time, we can hardly envisage a situation where one would have a long peptide sequence and not have the corresponding nucleotide sequence, and thus the search for Stop codons and long ORFs remains the simplest approach for detecting overlapping genes. However, proteomic sequencing (mass spectrometry or Edman degradation) is still used, in particular for exploring variants, and could become popular again with novel technological advances, thus making this simple method useful for a first check.

Counting the 𝒏-peptide non-null constraints

Due to the codon independency in frame -0 (see Section 4), the non-null, 𝑛-peptide constraints are derived easily in this frame, and their number equals 5 9 . For all the other frames, we computed the nonnull constraints for 𝑛-peptides up to length 𝑛 = 5 with our graph traversal algorithm extended to 𝑛peptides (Section 3). As expected from the di-peptide analysis (Section 4), the number of non-null 𝑛peptide constraints equals 2 a in frame +1 and +2, 1 in frame -1, and is larger than 10 a in frame -2 (Tab. 4). We did not achieve formal proof of these results for frame +1/+2, or find an exact formula for frame -2. All of our results are displayed in Table 4. A complete list of the non-null 𝑛-peptide (n ≤ 5) constraints in frame -2 is available at: http://www.univ-montp3.fr/miap/~lebre/DCODE.html.

Constraint

Conclusion and perspectives

A formal framework and a graph algorithm allowed us to introduce and characterize the constraints that bind the polypeptide composition of two proteins encoded by overlapping genes. Each constraint is a logical equivalence resulting from a set of implications. Even though implications may give more specific information, the equivalence constraints offer the advantage of yielding compact and comprehensive information, which can be interpreted directly in terms of amino-acid and polypeptide composition constraints imposed on two overlapping proteins. For example, in frame -0, four out of the five constraints correspond to specific biochemical constraints in terms of hydropathy (Section 3). Moreover, most of the theoretical approaches for understanding the constraints imposed by overlapping genes assume that the sequence of one of the two proteins is (in the reference frame), and then evaluate the remaining degrees of freedom for the overlapping protein (for example, see [START_REF] Smith | Protein constraints induced by multiframe coding[END_REF] or, more recently, [START_REF] Mir | Selection Pressure in Alternative Reading Frames[END_REF]). In other words, they provide directional results, typically based on logical implications or conditional probabilities. However, the sequence of a protein is never entirely fixed. All proteins have variants and (generally) a large number of degrees of freedom. Thus, a major interest of our equivalence-based approach is that our constraints are symmetrical and enable characterization of the joint composition of overlapping proteins.

In agreement with previous results derived from information theory, frame -2 (anti-sense overlap when the first two sites of the codons in the two reading frames overlap) is the most constrained among the five possible reading frames. However, considering polypeptides and not single amino acids, that is, taking into account the dependency between successive codons, highlights a second type of constraint: null constraints, stating that a polypeptide cannot be observed in a given reading frame as it would induce a Stop codon in the overlap. Except in frame -0 which is not subject to dependency, these null constraints are induced in all reading frames by a specific subset of di-peptides (six di-peptides in frame -2; five di-peptides in frames -1, +1, and +2). A logical approach allowed us to study the combinatorics of both the null and non-null 𝑛-peptide constraints, thus pointing out that: (i) except for frame -2, non-null constraints are deduced from the amino-acid constraints, and (ii) null constraints are deduced from the di-peptide constraints. Moreover, we give a closed formula for the number of null constraints for peptides of length 𝑛 in each frame, which may form the basis for a fast scanning method to select possible overlapping regions within protein sequences.

From that point on, the various frames can be studied and compared in the light of these two types of constraints. Frame -2 (the most constrained) is comparable to frame -1 in terms of null constraints. The two possible overlaps in the same sense (frame +1 or +2) are subject to null constraints in only one of the two reading frames. Non-null polypeptide constraints are derived simply using ordered combinations of amino-acid constraints, except for frame -2, where novel constraints appear when increasing the length of the overlapping peptides, due to codon dependency. Analytical computation of the exact number of non-null constraints in frame -2 is left open, and is an interesting direction for further research, to fully understand the combinatorics of double-coding in this reading frame. A general open question in this article is that of fully understanding what are the patterns and trajectories of joint evolution that can be taken simultaneously by two proteins encoded on the same portion of DNA.

APPENDIX

A. List of additional non-null constraints in frame -2

• The combination of constraints ( 7) and (8) (Tab. 2) in this order gives the 2 following di-peptide constraints: C (H+Q) óW (H+Q) W (H+Q) ó C (H+Q)

• The combination of constraints ( 8) and ( 7) gives:

H (C+W) ó Q (C+W) Q (C+W) ó H (C+W)
• The double combination of constraint (7) gives:

W (C+W) ó H (H+Q) C (C+W) ó Q (H+Q)
and the double combination of constraint (8) gives the reciprocal constraints.

• The combination of constraints ( 2) and ( 10) in this order gives:

Y (D+E) ó SY Y (F+K+L+N+R+S) ó (E+K+L+R) Y

where terms DY, FY, and NY are removed from the right part of the constraints as they are forbidden di-peptides (Tab. 3), i.e. DY = 0, FY = 0, NY = 0). The (ordered) combination of Constraints ( 10) and (2) gives the reciprocal constraints.

• The combination of constraints ( 8) and ( 10 Hence, six amino-acid constraint combinations ((2)(10), (7)( 7), (7)(8), (8)( 7), (8)( 8), (10)(2)) lead to a di-peptide constraint that divides into two di-peptide constraints; and four combinations ((7)(10), (8)(10), (10)( 7), (10)(8)) lead to three di-peptide constraints. This increases the total count of "non-null" constraints by 14. Moreover, one of the 10 2 constraints derived from the amino-acid constraints, YY ó YY, is removed from the constraint set, as it is redundant with the two null constraints excluding dipeptide YY both in the reference and in the overlapping frame (Tab. 3). This results in 10 2 -1 + 14 = 113 non-null di-peptide constraints in frame -2, as found by our graph algorithm (Fig. 3) applied to "heptons".

B.

Counting the 𝒏-peptide null constraints in frames ---1, +1, +2

In frame -1, the set of di-peptides inducing a Stop codon in the overlapping frame is {FI, FM, FT, FN, FK} (Tab. 3) and the total number of allowed 𝑛-peptides (reference or overlap) is: ∀𝑛 > 2, 𝐴 9 = 𝐴 9,c + 𝐴 9,9=/ c where 𝐴 9,c (respectively 𝐴 9,9=/ c ) is the subset containing the allowed 𝑛-peptides starting with amino acid F (resp. starting with any amino acid except F). From 𝐴 9,c = 𝐴 9A#,9=/ d,e,f,g,h = 𝐴 9A# -5 𝐴 9A& and 𝐴 9,9=/ c = 19 𝐴 9A# follows: In frame +1 or +2, the set of di-peptides inducing a Stop codon in the overlapping frame is {MI, MK, MM, MN, MT} either in the reference (frame +1) or in the overlap (frame +2) (Tab. 3). The total number of allowed 𝑛-peptides (reference in frame +1 or overlap +2) is: ∀𝑛 > 2, 𝐴 9 = 𝐴 9,9=/ e + 𝐴 9,e where 𝐴 9,e (resp. 𝐴 9,9=/ e ) is the subset containing the allowed 𝑛-peptides starting with amino acid M (respectively starting with any amino acid except F). From 𝐴 9,9=/ e = ( 20

Figure 1 :

 1 Figure 1: Our notation (Us) for the six overlapping reading frames, and correspondence with alternative notations found in literature: FB[START_REF] Firth | Detecting overlapping coding sequences in virus genomes[END_REF], SW[START_REF] Smith | Protein constraints induced by multiframe coding[END_REF], K[START_REF] Krakauer | Stability and evolution of overlapping genes[END_REF], R[START_REF] Rogozin | Purifying and directional selection in overlapping prokaryotic genes[END_REF].

Figure 2 :

 2 Figure2: Representation of amino acid constraint C + W (+Stop) ó H + Q occurring in frame -2. Bold letters (C, W, Stop) and italic letters (H, Q) correspond respectively to the amino acids read in the reference frame and the overlapping frame. (A) Graphical representation. The middle column lists the possible quadons (reference/frame -2) for each possible amino acid overlap. The codon read in each frame of a quadon is underlined. Amino acid C, which can be encoded by two codons {tgc, tgt}, is present in 8 quadons, which encode in reading frame -2 for either amino acid H {cac, cat} or Q {caa, cag}. The latter amino acid Q can, in turn, be overlapped by W {tgg} or by a Stop codon {tga}. Amino acid W may not be overlapped by any other amino acid and the Stop codons are assumed absent from a coding sequence. The set of amino acids involved in the constraint defines a connected component in the "tri-partite graph" associated with frame -2 (Section 3). (B) Associated adjacency matrix. Columns refer to the quadons (read in the reference frame), and rows to the amino acids. The rows correspond to the four amino acids (two in the reference, two in the overlap) included in the connected component of graph (A). These rows are linearly dependent, i.e. R # + 𝑅 & -R ( -R ) = 0 where R -is the 𝑖 /0 row of the matrix (B).

Figure 3 :

 3 Figure 3: Tri-partite graph traversal algorithm. This algorithm lists the set of amino acids (reference and overlap) defining a connected component in the tri-partite graph for a given overlapping frame in {-2, -1, -0, 1, 2}, and returns the associated amino-acid composition constraint.

  ) in this order gives (the reverse order gives the reciprocal constraints):Q (N+K) ó F (C+W) (H+Q) (D+E) + Q (F+L) ó (S+N) (C+W) H (F+K+L+N+R+S) + Q (S+R) ó (D+E+K+L+ R) (C+W)• The combination of constraints (7) and (10) in this order gives (the reverse order gives the reciprocal constraints):C (D+E) + W (D+E+F+L) ó (S+N) (H+Q) C (F+K+L+N+R+S) + W (S+R) ó (D+E+K+L+R) (H+Q)W (N+K) ó F (H+Q)

  -1) 𝐴 9A# and 𝐴 9,e = 𝐴 9A#,aij k,l,m,G,n = (20 -5) 𝐴 9A& follows,∀𝑛 > 2, 𝐴 9 = 19 𝐴 9A# + 15 𝐴 9A& 𝐴 # = 20 𝐴 & = 20 & -5 = 395Lastly, the total number of allowed 𝑛-peptides (reference or overlap) is: ) values are given in

Table 1 : Standard genetic code.

 1

  ∀𝑛 > 2, 𝐴 9 = 𝐴 9,9=/ ; + 𝐴 9,; = 19 𝐴 9A# + 14 𝐴 9A& 𝐴 # = 20 and 𝐴 & = 20 & -6 = 394This equation defines a second order linear homogeneous recurrence relation with constant coefficients 𝐴 9 = 𝑐 # 𝐴 9A# + 𝑐 & 𝐴 9A& , which is satisfied for all 𝑛 > 2. The same coefficients yield the characteristic polynomial, 𝑝 𝑡 = 𝑡 & -𝑐 # 𝑡 -𝑐 & , with roots 𝑟 # and 𝑟 & (if distinct). 𝑘 # , 𝑘 & fit the initial conditions of the recurrence(Greene and Knuth, 1982, section 2.1.1). This leads to the following expression of the roots 𝑟 # , 𝑟 & , and coefficients 𝑘 # , 𝑘 & :

			The solution of
	the recurrence is given by:
	∀𝑛 > 2, 𝐴 9 = 𝑘 # 𝑟 # 9 + 𝑘 & 𝑟 & 9
	where coefficients 𝑟 # = # & 19 + 19 & + 56 ≈ 19.710; 𝑟 & =	# &	19 -19 & + 56 ≈ -0.710;

Table 4 : Total number of constraints (null and non-null) as a function of the size of the peptides for all frames.

 4 The number of constraints for peptides with size 𝑛 lower than five are obtained with our graph algorithm (Sections 3 and 4). The numbers of null 𝑛-peptide constraints are obtained from the recursive formulae described in Section 5 and Appendix B. The number of non-null 𝑛 -peptides constraints in frame +1/+2 and -1, with 𝑛 > 5, are conjectured from the results with 𝑛 ≤ 5. With frame -2 we only know that this number is larger than 10 9 (number of ordered combinations of amino-acid constraints).

Table B1 : Coefficients defining the closed formula for the number |A n | of allowed

 B1 Table B1 for each frame. 𝑛-peptides in frames -1, +1, and +2 (values of 𝑟 # , 𝑟 & , 𝑘 # , and 𝑘 & , are approximated).

	Frame	𝒄 𝟏	𝒄 𝟐	𝒓 𝟏	𝒓 𝟐	𝒌 𝟏	𝒌 𝟐
	--1	20	--5	19.747 0.253 1.013	--0.013
	+1 (reference) +2 (overlap)	19	15	19.759 --0.759 1.012	--0.012

Acknowledgements

We would like to thank Elodie Cassan, Antoine Gross, and Jean-Michel Mesnard for stimulating and fruitful discussions, Alain Jean-Marie for its relevant indications and references, Etienne Simon-Lorière for his helpful comments on this paper, and the anonymous reviewers for their constructive advice.