domain: scco sde shs stat qfin

text:
Alberto Costantiello
email: costantiello@lum.it.

Angelo Leogrande

The Ease of Doing Business

Keywords: Analysis of Collective Decision-Making, General, Political Processes: Rent-Seeking, Lobbying, Elections, Legislatures, and Voting Behaviour, Bureaucracy, Administrative Processes in Public Organizations, Corruption, Positive Analysis of Policy Formulation, Implementation. JEL Classification: D7, D70, D72, D73, D78

In this article, we estimate the variable Ease of Doing Business-EDB in the context of Environmental, Social and Governance-ESG model. We use data from ESG World Bank dataset. We have used data from 193 countries in the period 2011-2020. The level of EDB is positively associated, among others, to "Individuals Using the Internet", "Government Effectiveness", "Cooling Degree Days", and negatively associated to "Agriculture, Forestry, and Fishing, Value Added", "Forest Area" and "Strength of Legal Rights Index". Furthermore, we have applied a cluster analysis with the application of the k-Means algorithm optimized with the Elbow Method and we have found the presence of four clusters. Finally, we have proposed a confrontation among eight different machinelearning algorithms to predict the future value of EDB. We have found that Linear Regression is the best algorithm and that the level of EDB is expected to improve of 1.66% for the analysed countries.

However, environmental issues are also equally relevant especially for multinational companies that have stringent ethical criteria, and which are monitored in their investments by investors or stock exchange control companies. Finally, the social aspects are also of some relevance for the purposes of the EDB, such as in the case of the spread of the number of internet's users. Finally, it must be considered that at present all countries accept the idea that the maximization of EDB is a necessary and good policy for economic development at the country level. In the past, there was a debate relating to the optimal modalities for the production of goods and services i.e. the contraposition between market societies and socialists societies. Today this contraposition does not exist anymore. Even China, which is a State formally governed by a communist party, accepts the idea that economic development takes place through private companies and therefore tends to create a system oriented to promoting EDB. Obviously, this does not mean that there are identical conditions and visions between the countries relating to EDB's opportunity. And in fact, there is a certain degree of heterogeneity in terms of defense and protection of private property rights that contrasts the western world to the countries of new industrialization. The article proceeds as follows below: the second paragraph contains the analysis of literature, the third paragraph presents the econometric model, the fourth paragraph shows the results of the cluster analysis, the fifth paragraph analyzes the prediction obtained with machine learning algorithms, the sixth paragraph concludes. The appendix has further graphic contents and metric results.

2) Literature Review

A part of the scientific literature relating to the role of EDB is reported below. The literature analyzes the role of EBD in promoting economic development, economic growth, FDI and good governance.

EDB and Economic Growth.

There is a close relationship between the value of EDB and economic growth. In fact, countries that have a very high level of economic growth also have high levels of EDB. These are economies that host big corporations, multinational companies that combine billions of dollars and sometimes have a market value higher than the GDP of many countries worldwide. However, to reach this level of development of the private sector economy, it is necessary that institutional reforms are built. Among these reforms, those that facilitate EDB have a crucial role in allowing the settlement and development of new companies, which also in the presence of adequate financial markets and banking intermediaries, can become multinational companies and operate globally. Obviously, the value of EBD is high in western countries that in fact tend to have a high growth and economic development. However, also the countries of new industrialization, such as China, India, Indonesia, Pakistan, and Nigeria, are facing the theme of EDB to prepare themself to participate as protagonists in the future of global economic growth. The linkages between EDB and economic growth change over time: that's the result of a comparison between 2008 and 2017 in a set of African Countries. It follows that it is not possible to set a unique and one for ever set of politics to promote the positive relationship between EDB and economic growth even if the quality of regulation seems to play a strategic role either for EDB either for the increase in GDP [START_REF] Estevão | The doing business ranking and the GDP. A qualitative study[END_REF]. EDB is positively associated to capital market development and the diffusion of electricity in Economic Community of West Africa-ECOWAS countries in the period 2004-2017 [START_REF] Nageri | Ease of doing business and capital market development in a demand following hypothesis: Evidence from ECOWAS[END_REF]. EDB has a positive effect on economic growth in Indonesia [START_REF] Nawawi | The Effect of Human Development Index, Ease of Doing Business, Corruption, and Distribution of ZIS Funds on Indonesia's Economic Growth[END_REF].

EDB and Land Management. The possibility of increasing the EDB value also depends in some way on land management. Above all, the urban structure of the cities, the possibility of being able to establish in the cities of the production neighborhoods, which hosting companies, is an essential element for the development of EDB. In this sense, it is not possible for a country to obtain high levels of EDB without adequately investing in improving the tools of land and space management. The connection between the organization of the cities from an urban point of view, the transport system and also the sources of energy supply is also very relevant. Finally, the issue of pollution becomes increasingly relevant within the urban context and companies are looking for not only places equipped to establish their own offices as well as cities that are clean and that can respect the criteria of environmental sustainability These requests for adequate spaces for the settlement of companies become increasingly pressing with the growth of the quality of the human capital employed. There is a positive relationship between EDB and land and spatial management in the case of Indonesia [START_REF] Indrajit | Implementation of the spatial plan information package for improving ease of doing business in Indonesian cities[END_REF]. Indonesia is implementing a Rights, Restrictions, and Responsibilities-RRRs system to improve EDB through land management [START_REF] Indrajit | The Role of the Revised Land Administration Domain Model and Spatial Data Infrastructure in Improving Ease of Doing Business in Indonesia[END_REF].

EDB and FDI.

The role of FDI is important for new industrialized countries. In fact, the low-income income countries try to attract the investments of multinationals by focusing on the low labor cost and on the ability to offer public and financial incentives to the big corporations. However, the ability of a country to attract multinationals depends on the quality of its political institutions, its laws, on the safety of its judicial system and on its police system. In fact, international companies do not invest only for economic reasons, that is to reduce the price of raw materials, lower the cost of labor or approach the outlet markets or to optimize the supply chain. Multinational companies also invest considering international politics as demonstrated by the transition between off-shoring and friendshoring. That is, companies try to invest in countries that also have common political values, namely the fact of sharing the ideal of democracy, economic freedoms, and a market system capable of protecting property rights. There is a positive relationship between EDB and FDI [START_REF] Malik | Ease of doing business and foreign direct investment: A review paper[END_REF]. There is a positive relationship between EDB and FDI in North Macedonia [START_REF] Jusufi | An overview of Doing business in Western Balkan: The analysis of advantages of Doing Business in Kosovo and North Macedonia[END_REF]. EDB has a positive impact on moderating the negative effect of political risks on FDI for Thailand [START_REF] Pertiwi | Understanding Country Risk Toward Foreign Direct Investment Moderated By Ease Of Doing Business Ranking[END_REF]. There is a positive connection between EDB and FDI in Indonesia [START_REF] Fibra | The Ease of Doing Business in Indonesia[END_REF]. There is a positive relationship between some sub-variable of EDB and FDI in 16 European transition countries i.e.: Starting a Business, Registering Property, Getting Electricity and Resolving Insolvency [START_REF] Haliti | The impact of the ease doing business indicators on foreign direct investment in the European transition economies[END_REF]. EDB is positively associated to FDI in a set of 166 countries in the period 2009-2018 [START_REF] Anggraini | The impact of the ease of doing business on foreign direct investment[END_REF].

EDB and Governance. Finally, the issues related to governance are also very relevant for the development of EDB. In particular, the presence of corruption or terrorism do not facilitate the increase of EDB at country level. It follows that if a nation wants to improve its value in terms of EDB, it must necessarily try to modify its own governance. To improve public governance, it is necessary to eliminate corruption, to focus on political stability, to assert the rule of law, to increase the regulatory quality, to increase the degree of government effectiveness. It is also very important that the countries intervene on the structure of recognition and protection of private property rights and on the methods to solve disputes between creditors and debtors. In fact, either the possibility of attracting FDI, either the ability to help the population to take charge of the business risk, also depends on regulations that are in favour of risk takers and that do not get the debtors excessively if they are entrepreneurs. Corruption, inflation, and imports are negatively associated to EDB in a set of countries in the period 2014-2017 for West African Countries [START_REF] Nageri | Corruption and ease of doing business: Evidence from ECOWAS[END_REF]. The regulatory policy is an essential tool to promote EDB in India [START_REF] Natarajan | An analytical investigation on ease of doing business in India[END_REF] and Oman [START_REF] Bhandari | Entrepreneurship Ecosystem: An Appraisal for Sultanate of Oman Using the Ease of Doing Business Index[END_REF]. There is a positive relationship between EDB and governance indicators for 188 countries [START_REF] Handoyo | An exploratory study on the relationship of public governance and ease of doing business[END_REF]. E-governance has a positive impact on EDB in India [START_REF] Yadav | E-GOVERNANCE IMPACT ON EASE OF DOING BUSINESS IN INDIA[END_REF]. A reform of the legal protection of property rights, bankruptcy and civil disputes can help Indonesia to improve its EDB ranking [START_REF] Asmara | Ease of Doing Business: Gagasan Pembaruan Hukum Penyelesaian Sengketa Investasi di Indonesia[END_REF], [START_REF] Rumadan | Enforcement of Court Decision Regarding Payment of a Sum of Money in Civil Disputes to Support the Ease of Doing Business in Indonesia[END_REF], [START_REF] Kawung | Ease of Doing Business in East Indonesian Region: Starting a Business Study in North Sulawesi Province SMEs[END_REF]. A better governance can improve the level of EDB in Pakistan [START_REF] Lakhan | Ease of Doing Business in Pakistan[END_REF].

3) The Econometric Model for the Estimation of the EDB

In the following part we present the results of the econometric estimate. The econometric model made estimates EDB's value based on a set of variables belonging to the ESG database of the World Bank. The data refer to the period between 2011 and 2020 for 193 countries. The econometric techniques used are: Panel Data with Fixed Effects, Panel Data with Random Effects, Weighted Least Squares-WLS and Poled Ordinary Least Squares-OLS. The choice to use panel models is almost obligatory. In fact, having available a set of data capable of giving a representation both in the sense of the historical series and in the sense of individual observations then it is advisable to use the panel data model. The WLS and Poled OLS models have been used with greater proof of the results obtained, that is, as "a fortiori" condition. In the analysis of the individual variables of the model and their relationships with EDB we did not highlight the presence of causal relationships. On the contrary, we only analysed associative relationships. In fact, having not applied any type of cause-effect analysis, we limited ourselves to verifying the presence of associations among the variables by evaluating them according to the fact that they are positive or negative and based on their statistical significance. The ESG database of the World Bank is made up of 67 variables. Among these, about 25 appeared to have a high statistical significance compared to EDB. However, by simplification we decided to use a model with a maximum of 10 variables, and effectively we ended with 9 variables, in order not to incur the problems of overfitting, endogeneity and excess value of the R-Squared. Specifically, we have estimated the following formula:

= + + + + + + + + + = = [ ! -! !]
The value of EDB is positively associated to the following variables:

• PO: is a variable that considers the percentage of adults aged 18 or over whose body mass index (BMI) is greater than 25 kg/m2. Body mass index (BMI) is a simple index of weight times height, i.e. weight in kilograms divided by height in meters squared. There is a positive relationship between the EDB value and the PO value. Countries that have a high EDB value tend to have a positive amount of PO. Among the countries with a high percentage of overweight people in adulthood are the United States with a value of 67.9%, followed by New Zealand with 65.6%, Australia with 64.5%. Israel with 64.3%, Canada with 64.1% and the United Kingdom with 63.7%. The relationship can be understood considering that the countries that have a high level of EDB are also the countries that have a high per capita income. In countries with high per capita income, the population tends to develop forms of overweight, also creating significant problems for the financial sustainability of health care expenditure. • EI: is the ratio between the energy supply and the gross domestic product measured at purchasing power parity. Energy intensity is an indication of how much energy is used to produce an economic unit of production. A lower ratio indicates that less energy is used to produce one unit of output. There is a relationship between EI and EDB. Countries that have a high level of EDB also have highly developed industrial systems and a high level of energy intensity. However, the same countries are trying to reduce energy intensity through investment in environmental sustainability and through the increase of alternative forms of energy. The business creation activity turns out to be very expensive in terms of energy and in order to be attractive towards the industrial and entrepreneurial system, countries often tend to consume and waste a lot of energy, also increasing the value of CO2 emissions. A very serious condition that requires new economic policies based on sustainability and new renewable technologies.

• IUI: are individuals who have used the Internet (from anywhere) in the past 3 months. The Internet can be used through a computer, mobile phone, personal digital assistant, game console, digital TV, etc. There is a positive relationship between EDB and IUI value. The countries that have the highest level of EDB are also the countries that have the greatest diffusion of information technologies. The affirmation of the fourth industrial revolution has led to the development of technologies applied to business that require massive doses of digitization. Furthermore, the development of technologies is also necessary to increase the ability of companies to offer services to users and develop new business opportunities. The diffusion of internet users is therefore, on the one hand, a preliminary element to the development of startups and newcos and, on the other hand, a multiplier of the private sector to generate earnings.

• GE: captures perceptions of the quality of public services, the quality of the civil service and the degree of its independence from political pressures, the quality of policy formulation and implementation, and the credibility of government engagement against these policies. The estimate gives the country's score on the aggregate indicator, in units of a standard normal distribution, i.e. ranging from approximately -2.5 to 2.5. There is a positive relationship between EDB and GE. Countries that offer the best public services to the population are also the countries that have the greatest capacity to attract businesses and create a favourable economic climate for entrepreneurship. This positive relationship between the value of GE and EDB is also because in order to set up companies at the country level it is also necessary to offer a political and institutional framework favourably directed towards the protection of rights and freedoms. Indeed EDB is a variable that can also be considered as a representation of the high level of defence of private property rights and economic freedoms.

• CDD: is a measurement designed to track energy use. It is the number of degrees in which the average temperature of a day is above 18°C (65°F). The degree-days are accumulated to obtain the annual values. There is a positive relationship between CDD and EDB. CDD is a measurement of the advancement of global warming. The positive relationship between CDD and EDB shows that global warming has increased in countries that have high levels of EDB and which are generally northern hemisphere countries.

The value of EDB is negatively associated to the following variables:

• AFF: calculates the value added of agriculture, forestry and fishing. There is a negative relationship between AFF and EDB. Countries that have a high level of EDB also have a low AFF value. Countries that have high levels of AFF as a percentage of GDP are in fact low per capita income countries with low EDB levels. These countries have an economy that has not yet developed. Countries that have a developed economic system tend to have a breakdown of GDP by sector of economic activity centred on the service sector and in particular on advanced services. In these countries, the value of AFF is reduced in a range between 2 and 3%. Countries that have high levels of EDB are therefore countries that tend to develop the service sector with a reduced role of manufacturing, construction and AFF.

• FA: is land under natural woodland or planted trees of at least 5 meters in situ, whether productive or not, and excludes woodland in agricultural production systems (for example, fruit plantations and agroforestry systems) and trees in urban parks and gardens. There is a negative relationship between the FA and EDB. Countries that have high levels of AF also have low levels of EDB. In the top ten countries by FA value in 2020 we find Suriname with 97.41%, Guyana with 93.55%, Micronesia Fed Sts with 92.02%, Gabon with 91.32%, Solomon Islands with 90.13%, Palau with 90.02%, Equatorial Guinea with 87.28%, American Samoa with 85.65%, Papua New Guinea with 79.17%, and Liberia with 79.08%. These countries have low performance in terms of EDB.

• SLRI: measures the degree in which the guaranteed and bankruptcy laws protect the rights of mutuals and financiers and therefore facilitate loans. The index varies from 0 to 12, with higher scores indicating that these laws are better designed to expand access to credit. There is a negative relationship between the EDB value and the value of SLRI. This relationship is since to increase the ability of people to do business, legislation is needed that does not only facilitate the creditor and that it is in some way also in favour of the debtor. In fact, if we look at the SLRI ranking in 2020 we can see that the countries that have the maximum score, or 12, are Azerbaijan, Brunei Darussalam, Montenegro, New Zealand, and Puerto Rico. Except for New Zealand who has good values in terms of EDB, the other countries in the top SLRI have reduced EDB values. For example, Singapore, which is one of the leading countries in terms of EDB, has a value of slides of eight.

Finally, we can observe that the relationship between EDB and PD is weakly positive but close to zero. The population density is a mid -year population divided by the earth's surface into square kilometres. The population is based on the factual definition, which has all residents regardless of legal status or citizenship, except for refugees not permanently established in the country of asylum, which are generally considered part of the population of their country of origin. The weak positive relationship between PD and EDB is since many of the countries that have a high level of EDB are small countries with a significant population density. In fact, there are countries that have high levels of EDB and high levels of PD such as: Macao, Monaco, Singapore, Hong Kong and Gibraltar. However, many countries that have a medium-high level of EDB have reduced PD values. For example, the USA are among the last countries in the world in terms of PD also having very high EDB values.

4) Clusterization with k-Means Algorithm

A clustering with k-Means algorithm optimized with the Elbow method is presented below. The clustering algorithm is applied to verify the presence of a series of clusters within the analyzed dataset.

In this case we analyzed 191 countries. Since we are dealing with a very large set of countries, it is necessary to identify characteristics that can highlight the presence of heterogeneity in the data. Furthermore, clustering also serves to verify the presence of geographical connections in the area that can in some way determine the presence of common geo-political factors. Finally, through clustering we also want to highlight whether the countries within the same cluster also share common institutional elements such as, for example, the presence of a democratic system or an orientation towards the market society. The clustering process can be accomplished through a set of methodologies. Since the k-Means algorithm is an unsupervised algorithm, it is necessary to identify a criterion that can allow to identify the optimal number of k. We have tried using the Silhouette coefficient method with poor results. In fact, the Silhouette coefficient is a number that varies from -1 to 1 which is assigned to each k. The value of k that has the highest Silhouette coefficient value is the optimal k. However, in the case analysed, the optimal value of k with the Silhouette coefficient is equal to 2. It follows that the 191 countries analyzed would have become part of only two clusters with a very low level of representation of heterogeneity between countries. For this reason, i.e. in order not to lose the ability to give a correct representation of the heterogeneity present among the countries analysed, we have chosen to use the alternative method to the Silouette coefficient or the Elbow method. Elbow's method is a graphical method for determining the number of optimal clusters of a given sample. Through the use of Elbow's method, the number of k=4 was chosen. The value of k=4 was considered sufficiently valid to give a representation of the heterogeneity present within the analyzed dataset. From a strictly quantitative point of view and with reference to the median of the clusters, it is possible to identify the following ordering: $2 = 21 > $4 = 72 > $1 = 128,5 > $3 = 164,5.

• C1= Gambia, Mozambique, Tanzania, Nigeria, Malawi, Micronesia, Kenya, Uzbekistan, Sri Lanka, Iran, Libya, South Sudan, Bangladesh, Palestine, Barbados, Dominican Republic, Myanmar, Maldives, Belize, Yemen, Saint Kittis and Nevis, Somalia , Cape Verde, Bosnia and Herzegovina, Philippines, India, Ukraine, Ecuador, Egypt, Jordan, Bhutan, Ethiopia, Paraguay, Indonesia, Granada, Nepal, Papua New Guinea, Lesotho, Brazil, Honduras, Pakistan, Palau, Eswatini, Kiribati, Uganda, Guyana, Lebanon, Marshall Islands, Nicaragua, Argentina. C1 countries are among the bottom countries in terms of EDB. C1 is in fact the penultimate cluster before C3. These are African countries in South and Southeast Asia, Latin America and Eastern Europe. The reasons that push these countries to have a low performance in terms of EDB refer to the socio-economic, political and institutional dimension. In fact, these are countries that have fragile democracies, models of economic growth based on the fight against poverty and inequality, and a set of educational institutions and in the health sector that are quite fragile. However, among these countries we have to focus on India. Indeed, India will become one of the top economies in the world in terms of absolute gross domestic product. However, given the size of the population, per capita income will in any case remain low and will probably converge on the low-medium level per capita income. However, India's ability to develop depends on its ability to improve the EDB variable. India, unlike China, is a democracy, based on the principles of equality and with recognition of private property rights and economic freedoms. It follows that, also thanks to the growth of Foreign Direct Investments-FDI, India should be able to increase its positioning in terms of EDB by creating the conditions to grow the private economy and therefore promote economic growth. Similar considerations are also valid for Indonesia and Brazil. Indeed, Indonesia and Brazil will certainly be two leading economies in future economic growth with very high levels of absolute gross domestic product and average levels of per capita gross domestic product. In fact, the analysis of C1 shows that India is improving its position from the point of view of EDB, together with Indonesia and could probably move into the next cluster by value of EDB or C4. However, the same considerations cannot be made for Brazil, which still presents difficulties in terms of EDB. Furthermore, the condition of Thailand is also of particular interest, a country that could grow a lot especially as a manufacturing and production hub, and which together with Indonesia and India could become a medium-high level country in terms of EDB. Finally, some consideration is also necessary with reference to Egypt, a country that should become part of the Next Eleven-N11, i.e. a group of countries, for which significant growth is expected in terms of percentage contribution to GDP at global level. • C2: South Africa, Saudi Arabia, Slovenia, North Macedonia, Puerto Rico, United Arab Emirates, Chile, Armenia, Spain, Slovakia, Israel, Georgia, Taiwan, Portugal, Belgium, France, Thailand, Mauritius, Netherlands, Singapore, Austria, Japan, New Zealand, Switzerland, Hong Kong, South Korea, Denmark, United States, Lithuania, Latvia, United Kingdom, Norway, Canada, Malaysia, Estonia, Germany, Ireland, Australia, Sweden, Iceland, Finland. C2 is the best cluster in the sense of EDB. It is a cluster made up of countries from North America, Central-Northern Europe, South-East Asia, the Far East and Oceania. C2 represents a set of countries that refer to the Western world. The countries that have the best performances in terms of EDB value are countries of North America, Northern Europe, Oceania, the Far East with the addition of Malaysia and the United Arab Emirates. The countries that could instead leave the cluster are Chile, Saudi Arabia, South Africa and Puerto Rico. The value of EDB represents in some way the degree of diffusion of Western capitalism.

Italy is one of the few European countries to be excluded from the leading cluster by EDB. Some separate considerations deserve South Africa. In fact, South Africa stands as the most westernized country in Africa and could lead an action of convergence towards South African levels in other countries of the continent. In fact, South Africa is a dynamic economy that is part of the BRICS. Saudi Arabia is a country that has a high level of EDB and that attracts FDI in an attempt to reduce the impact of the oil economy as a percentage of GDP. Chile is an economy that has suffered a lot from the charm of US liberalism-libertarianism and which has also been much oriented towards the market economy. Indeed, Chile has surpassed both Argentina and Brazil in terms of per capita income. In fact, Chile's GDP per capita was $16,265.10, while Argentina's GDP per capita was $10,636.12 and Brazil's GDP per capita was $7,507.16 in 2021. A particularly interesting area in terms of EDB is that of South-East Asia and the Far East. These are countries such as Singapore, Hong Kong, Taiwan, Thailand, Japan, and South Korea, which have very high levels of development of socio-economic institutions capable of supporting the business sector. However, these economies are also at risk. The tension between USA and China is a threat towards the diffusion of FDI and the development of EDB in the area. Certainly, the situation in Hong Kong has changed following the Chinese aggression, and a similar fate appears to befall Taiwan. Japan and South Korea could also have negative effects from the growing tension between the US and China. Southeast Asia and the Far East represent the Western avant-garde in the Eastern world. The economic, human and social development of the countries of South East Asia and the Far East, and therefore the ability to attract companies to do business, depend on the presence of international relations of mutual interest between the USA and China. However, if China wants to establish itself as a local hegemonic power, then even the economies most connected to the Western world could experience a growth in systemic risks and a reduction in EBD. • C3: Tajikistan, Cambodia, Liberia, Algeria, Djibouti, Suriname, Gabon, Comoros, Syria, Madagascar, Sierra Leone, Cote d'Ivoire, Mali, Bolivia, Burkina Faso, Equatorial Guinea, Sudan, Senegal, Laos, Togo, Iraq, Burundi, Haiti, Benin, Niger, Central African Republic, Eritrea, Democratic Republic of Congo, Chad, Venezuela, Mauritania, Zimbabwe, Afghanistan, Congo, Sao Tome and Principe, Guinea, Timor Leste, Angola, Cameroon. C3 is the last cluster in terms of EDB. It is a set of countries belonging mainly to the African and Latin America. There are also certain countries of the Middle-Orient and Asian. The countries that have the greatest difficulty in terms of EDB are the countries of Sub-Saharan Africa. The countries of sub-Saharan Africa among African countries are those that have the largest level of underdevelopment from an economic, political, and institutional point of view. They are also countries that live difficult conditions from the point of view of war and violence between ethnic and tribal groups. In addition, there are also other countries characterized by very high political instability which therefore also have very low levels in terms of EDB or Syria, Venezuela, Afghanistan, Iraq. Furthermore, it must be considered that many of the C3 countries suffer from the curse of raw materials, or these are countries that have a high endowment of raw materials and which unfortunately are unable to access either economic growth paths or social development path. • C4: Mexico, Hungary, Bulgaria, Salomon Islands, Poland, Colombia, Peru, Czech Republic, Saint Vincent and the Grenadines, Bahrain, Guatemala, Uruguay, Bahamas, Costa Rica, Zambia, El Salvador, Romania, Malta, Cyprus, Seychelles , Kazakhstan, Morocco, San Marino, Ghana, Botswana, Luxembourg, Saint Lucia, Oman, Kosovo, Russia, Montenegro, Vietnam, Dominica, Albania, Fiji, Rwanda, Antigua and Barbuda, Tonga, Trinidad and Tobago, Kuwait, Namibia, Azerbaijan , Brunei, Belarus, China, Samoa, Greece, Italy, Croatia, Mongolia, Turkey, Tunisia, Serbia, Jamaica, Vanuatu, Panama, Kyrgyzstan, Moldova. The C4 is the second cluster in the sense of EDB. From a geographical point of view we can see four macro-areas present in the C4 or: Asian countries, Eastern Europe countries, Central and Southern American countries and African countries. The group of leading countries is made up of China, Russia and Eastern Europe, Mexico and Colombia. On the contrary, Mongolia, some Balkan countries and the southern Africa countries are less efficient in terms of EDB. It is necessary to carry out some considerations as regards China and Russia. The data analysed refer to 2020 and therefore do not take into consideration the events that occurred in connections with the Russian-Ukraine war. In fact, at present, most likely, Russia is no longer considered as a nation in which the level of EDB is medium-high. And it is very likely that the economic sanctions against Russia that have been imposed by the international community further reduce the value of EDB in the country also in the future. Therefore, the map is not currently representative of what is the level of EDB in Russia above all considering that many western companies have decided to leave the country and to reduce the level of FDI following the military attack against Ukraine. However, the degree of EDB of China could also be reduced. In fact, on the one hand, the election of XI Jinping at the helm of the country and on the other hand the military tension and, on the other hand, the technological rivalry between China and the USA can have a negative impact in terms of EDB. If China is perceived in the future as a corrupt country, in which it is the communist party or political leadership that decides the value and methods of the FDI, then the value of EDB in the country will certainly to be reduced.

Machine Learning and Predictions for the Estimation of the Future value of EDB

To predict the future value of the EDB variable, we analysed a set of machine learning algorithms compared to each other in terms of R-squared maximization and statistical error minimization. The statistical errors we used are Mean Absolute Error-MAE, Mean Squared Error-MSE, and Root Mean Squared Error-RMSE. The algorithms were trained with 70% of the available data while the remaining 30% was used for the actual prediction. Below is the classification of the best performing algorithms, namely:

• Linear regression with a payoff value equal to 4;

• Polynomial regression with a payoff value equal to 8;

• PNN-Probabilistic Neural Network with a payoff value of 12;

• ANN-Artificial Neural Network with a payoff value of 16;

• Gradient Boosted Trees with a payoff value of 20;

• Random Forest Regression with a payoff value of 24;

• Tree Ensemble Regression with a payoff value of 28;

• Simple regression tree with a payoff value of 32. It follows that the best performing algorithm in terms of predictive capacity is the Linear Regression algorithm. By applying the Linear Regression algorithm, it is possible to verify that there are winners' countries, i.e. countries for which the EDB value is expected to decrease and losers' countries, i.e. countries for which the EDB value is expected to increase. Obviously, if the EDB value decreases, it means that there is an improvement. On the contrary, if the value of EDB increases, it means that there is a worsening of the country condition. Among the countries for the losers countries we find the following: Singapore with +87.5%, United States with +63.22%, Mauritius with +52.45%, Japan with +41.09%, Israel with +39.58%, Thailand with 33.2%, Tajikistan with +20.84%, Germany with 14.05%, Switzerland with +9.99%, Zimbabwe with 8.46%, Niger with 6.78%, Guinea-Bissau with 3, 39%, Saint Lucia with 1.65%, Canada with 1.48%, Qatar with 0.29%. From a strictly geographical point of view, it appears that the EDB value is predicted to grow for almost all the countries for which the prediction was made. Conversely, there are only three countries for which the value of EDB is predicted to decrease and they are the USA, Japan and Thailand. As regards the countries for which a growth in the value of EDB is predicted, i.e. African countries, southern and Eastern Europe and the American continent, these are countries that have a low average level of EDB in the historical series and for which therefore a positive marginal change is predicted. Instead, with reference to the countries that have pejorative values, these are countries that start from very good positions in the EDB ranking and that undergo a downgrading for political-economic reasons. Among the winner countries, i.e. those countries for which the EDB value is expected to decrease, there are: Grenada with a value of -0.44%, Malawi with a value of -0.54%, Sao Tome and Principe with a value of -0.91%, Democratic Republic of Congo with a value of -1.03%, Marshall Islands with a value of -2.59%, Montenegro with a value of -3.04%, Cape Verde with a value of by -3.06%, Angola with -3.82%, Ecuador with -5.43%, Argentina with -5.94%, Costa Rica with -6.53%, Chile with -7.05%, Palau with -7.16%, Bahamas with -9.7%, Dominican Republic with -10.2%, Honduras with -10.23%, Panama with -10.31%, Poland with -10.64%, Italy with -13.64%, Mexico with -15.56%, Solomon Islands with -16.28%, Brunei with -17.18%, Taiwan with -21.81%.

Conclusions

The originality of the article consists in the analysis of the EDB in the context of ESG. We have analysed the ESG dataset of the World Bank using different econometric techniques i.e. Panel Data with Fixed Effects, Panel Data with Random Effects, WLS and Pooled OLS. Results shows that EDB tends to be coherent in terms of ESG criteria. Furthermore we have applied a cluster analysis with the implementation of the k-Means algorithm optimized with the Elbow method. We have found the presence of four clusters. We found that the first cluster in terms of median value of EDB is made by western and pro-market society countries. But we also find that new countries are increasing their levels of EDB especially in the Asian continent i.e. China, Mongolia, Kyrgyzstan. Finally, we have made a confrontation among eight different machine learning algorithms to predict the future value of EDB and we found that the variable is linear with an expected increase of 1.66% on average for the analysed countries. Under a political point of view, we must note that all countries accept the idea that the maximization of EDB is a necessity to achieve higher levels of economic growth and development. There is not any kind of contraposition between market-based societies and nonmarket-based societies. In effect, even China, that is a State governed by a communist party, tries to improve EDB to attract FDI.

Variable Description

Ease of Doing Business

The ease of doing business score is the simple average of the scores for each of the Doing Business topics: starting a business, dealing with construction permits, getting electricity, registering property, getting credit, protecting minority investors, paying taxes, trading across borders, enforcing contracts and resolving insolvency. The score is computed based on the methodology in the DB15 studies for topics that underwent methodology updates. Agriculture, forestry, and fishing, value added Agriculture, forestry, and fishing corresponds to ISIC divisions 1-3 and includes forestry, hunting, and fishing, as well as cultivation of crops and livestock production. Value added is the net output of a sector after adding up all outputs and subtracting intermediate inputs. It is calculated without making deductions for depreciation of fabricated assets or depletion and degradation of natural resources. The origin of value added is determined by the International Standard Industrial Classification (ISIC), revision 4. Note: For VAB countries, gross value added at factor cost is used as the denominator.

Forest area

Forest area is land under natural or planted stands of trees of at least 5 meters in situ, whether productive or not, and excludes tree stands in agricultural production systems (for example, in fruit plantations and agroforestry systems) and trees in urban parks and gardens.

Strength of legal rights index

Strength of legal rights index measures the degree to which collateral and bankruptcy laws protect the rights of borrowers and lenders and thus facilitate lending. The index ranges from 0 to 12, with higher scores indicating that these laws are better designed to expand access to credit.

Population density

Population density is midyear population divided by land area in square kilometers. Population is based on the de facto definition of population, which counts all residents regardless of legal status or citizenship-except for refugees not permanently settled in the country of asylum, who are generally considered part of the population of their country of origin. Land area is a country's total area, excluding area under inland water bodies, national claims to continental shelf, and exclusive economic zones. In most cases the definition of inland water bodies includes major rivers and lakes.

Prevalence of overweight

Prevalence of overweight children is the percentage of children under age 5 whose weight for height is more than two standard deviations above the median for the international reference population of the corresponding age as established by the WHO's new child growth standards released in 2006.

Energy intensity level of primary energy

Energy intensity level of primary energy is the ratio between energy supply and gross domestic product measured at purchasing power parity. Energy intensity is an indication of how much energy is used to produce one unit of economic output. Lower ratio indicates that less energy is used to produce one unit of output.

Individuals using the Internet

Internet users are individuals who have used the Internet (from any location) in the last 3 months. The Internet can be used via a computer, mobile phone, personal digital assistant, games machine, digital TV etc.

Government Effectiveness: Estimated

Government Effectiveness captures perceptions of the quality of public services, the quality of the civil service and the degree of its independence from political pressures, the quality of policy formulation and implementation, and the credibility of the government's commitment to such policies. Estimate gives the country's score on the aggregate indicator, in units of a standard normal distribution, i.e. ranging from approximately -2.5 to 2.5.

Cooling Degree Days

Figure 1 .

 1 Figure 1. Countries in C1.

Figure 2 .

 2 Figure 2. Countries in C2.

Figure 3 .

 3 Figure 3. Countries in C3.

Figure 4 .

 4 Figure 4. Countries in C4.

Figure 5 .

 5 Figure 5. Statistical Errors of the Predictions.

Figure 6 .

 6 Figure 6. Countries in which the level of EDB is expected to improve-in green-and to worsen-in red.

Figure 7 .

 7 Figure 7. Losers in the prediction i.e. countries for which the level of EDB is expected to decrease.

Figure 9 .

 9 Figure 9. Ranking of algorithms based on predictive performance.

The Econometric Model for the Estimation of the Value of EDB VAR Acronomyn

			Definition	Average Adjustment
				*(-1)
	A15	EDB	Ease of Doing Business
	A6	AFF	Agriculture, forestry, and fishing, value added (% of GDP)	0,84	-0,84
	A22	FA	Forest area (% of land area)	0,50	-0,50
	A63	SLRI	Strength of legal rights index (0=weak to 12=strong)	0,04	-0,04
	A49	PD	Population density (people per sq. km of land area)	0,00	0,00
	A51	PO	Prevalence of overweight (% of adults)	-0,08	0,08
	A18	EI	Energy intensity level of primary energy (MJ/$2011 PPP GDP)	-0,14	0,14
	A32	IUI	Individuals using the Internet (% of population)	-0,30	0,30
	A27	GE	Government Effectiveness: Estimated	-12,53	12,53
	A13	CDD	Cooling Degree Days (projected change in number of degree	-114,33	114,33
			Celsius)

  A cooling degree day (CDD) is a measurement designed to track energy use. It is the number of degrees that a day's average temperature is above 18°C (65°F). Daily degree days are accumulated to obtain annual values.

	Statistics based on the original data: Asymptotic test statistic: Chi-square(9) = 237.189
	Mean dependent var with p-value = 5.02975e-46		88.84301	S.D. dependent var	57.81021
			Sum squared resid		3213799 Actual and fitted A15 S.E. of regression	40.91275
		200	actual					Actual and fitted A15
		200	fitted actual fitted			Included 193 cross-sectional units Random-effects (GLS), using 1930 observations
		150 150							Time-series length = 10
									Dependent variable: A15
		100
		100						Coefficient	Std. Error	z	p-value
		50	const				81.4398	4.44011	18.34	<0.0001 ***
			A6					0.888507	0.128628	6.908	<0.0001 ***
	A15	0 50	A13				-60.9412	15.6515	-3.894	<0.0001 ***
	A15		A18				-0.0643409 0.0270483	-2.379	0.0174	**
		-50	A22				0.297813	0.0983410	3.028	0.0025	***
		0	A27				-7.05642	0.798682	-8.835	<0.0001 ***
		-100	A32				-0.182317	0.0275976	-6.606	<0.0001 ***
			A49				-0.00380288 0.00164715	-2.309	0.0210	**
		-150 -50	A51				-0.0856738 0.0197291	-4.343	<0.0001 ***
			A63				WLS, using 1930 observations 0.0156848 0.00263523 5.952	<0.0001 ***
		-200						Included 193 cross-sectional units
		-100	1	12	23	34	45	56	Dependent variable: A15 67 78 89 100 111 122 133 144 155 166 177
		-250	1	12	23	34	45	Weights based on per-unit error variances Coefficient Std. Error t-ratio time series by group 56 67 78 89 100 111 122 133 144 155 166 177 p-value time series by group
			const				93.8495 Pooled OLS, using 1930 observations 1.73704 54.03	<0.0001 ***
			A6					1.27051 Included 193 cross-sectional units 0.0436139 29.13	<0.0001 ***
			A13				-126.155 Time-series length = 10 16.8859 -7.471	<0.0001 ***
			A18				-0.147226 Fixed-effects, using 1930 observations 0.0436140 -3.376 Dependent variable: A15	0.0008	***
			A22				0.0666024 Included 193 cross-sectional units 0.0200188 3.327	0.0009	***
			A27				-20.2828 Time-series length = 10 0.693563 -29.24 Coefficient Std. Error t-ratio	<0.0001 *** p-value
			A32 const				-0.436715 Dependent variable: A15 0.0220305 -19.82 94.1149 2.77221 33.95	<0.0001 *** <0.0001 ***
			A49 A51 A63 Sum squared resid R-squared F(9, 1920) Log-likelihood Schwarz criterion A6 const A13 A6 A18 A13 A22 A18 A27 A22 A32 A27 A49 A32 A51 A49 A63	-0.00194548 0.000181193 -0.0702779 0.0171416 0.0695871 0.00477184 Statistics based on the weighted data: -10.74 -4.100 14.58 1820.429 S.E. of regression 0.920564 Adjusted R-squared 2472.272 P-value(F) -2682.149 Akaike criterion 5439.951 Hannan-Quinn Coefficient Std. Error t-ratio 1.46146 0.0935132 15.63 43.7113 14.7130 2.971 -95.2782 11.8701 -8.027 -0.266825 0.158542 -1.683 -0.162689 0.0378980 -4.293 -174.941 54.7783 -3.194 0.148025 0.0381570 3.879 -0.183035 0.0576512 -3.175 -14.3865 0.676500 -21.27 1.50570 0.446617 3.371 -0.498864 0.0352414 -14.16 -8.37984 1.95705 -4.282 -0.00313150 0.000633893 -4.940 -0.0786434 0.0274679 -2.863 -0.132272 0.0350359 -3.775 0.0186287 0.00995697 1.871 0.0473880 0.00395482 11.98	<0.0001 *** <0.0001 *** <0.0001 *** 0.973725 0.920192 0.000000 5384.298 5404.770 <0.0001 *** p-value 0.0030 <0.0001 *** *** 0.0926 <0.0001 *** * 0.0014 0.0001 *** *** 0.0015 <0.0001 *** *** 0.0008 <0.0001 *** *** <0.0001 *** <0.0001 *** 0.0042 0.0002 *** *** 0.0615 * <0.0001 ***
			A51 Mean dependent var	-0.0416181 0.0193733 88.84301 S.D. dependent var -2.148	0.0318 57.81021 **

Acknowledgements. We are grateful to the teaching staff of the LUM University "Giuseppe Degennaro" and to the management of the LUM Enterprise s.r.l. for the constant inspiration to continue our scientific research work undeterred.

List of Abbreviations

Declarations

Data Availability Statement. The data presented in this study are available on request from the corresponding author.

Funding. The authors received no financial support for the research, authorship, and/or publication of this article.

Declaration of Competing Interest. The authors declare that there is no conflict of interests regarding the publication of this manuscript. In addition, the ethical issues, including plagiarism, informed consent, misconduct, data fabrication and/or falsification, double publication.

Software. The authors have used the following software: Gretl for the econometric models, Orange for clusterization and network analysis, and KNIME for machine learning and predictions.


Eric Rivals
email: rivals@lirmm.fr

Leena Salmela
email: lsalmela@cs.hut.fi

Petteri Kiiskinen

Petri Kalsi

Jorma Tarhio
email: tarhio@cs.hut.fi

MPSCAN: fast localisation of multiple reads in genomes

With Next Generation Sequencers, sequence based transcriptomic or epigenomic assays yield millions of short sequence reads that need to be mapped back on a reference genome. The upcoming versions of these sequencers promise even higher sequencing capacities; this may turn the read mapping task into a bottleneck for which alternative pattern matching approaches must be experimented. We present an algorithm and its implementation, called MPSCAN, which uses a sophisticated filtration scheme to match a set patterns/reads exactly on a sequence. MPSCAN can search for millions of reads in a single pass through the genome without indexing its sequence. Moreover, we show that MPSCAN offers an optimal average time complexity, which is sublinear in the text length, meaning that it does not need to examine all sequence positions. Comparisons with BLAT-like tools and with six specialised read mapping programs (like BOWTIE or ZOOM) demonstrate that MPSCAN also is the fastest algorithm in practice for exact matching. Our accuracy and scalability comparisons reveal that some tools are inappropriate for read mapping. Moreover, we provide evidence suggesting that exact matching may be a valuable solution in some read mapping applications. As most read mapping programs somehow rely on exact matching procedures to perform approximate pattern mapping, the filtration scheme we experimented may reveal useful in the design of future algorithms. The absence of genome index gives MPSCAN its low memory requirement and flexibility that let it run on a desktop computer and avoids a time-consuming genome preprocessing.

Introduction

Next-generation sequencers (NGS), able to yield millions of sequences in a single run, are presently being applied in a variety of innovative ways to assess crucial biological questions: to interrogate the transcriptome with high sensitivity [START_REF] Kim | Polony Multiplex Analysis of Gene Expression (PMAGE) in Mouse Hypertrophic Cardiomyopathy[END_REF], to assay protein-DNA interactions at a genome wide scale [START_REF] Johnson | Genome-Wide Mapping of in Vivo Protein-DNA Interactions[END_REF], or to investigate the open chromatine structure of human cells [START_REF] Boyle | High-Resolution Mapping and Characterization of Open Chromatin across the Genome[END_REF][START_REF] Schones | Genome-wide approaches to studying chromatin modifications[END_REF]. Due to their wide applicability, cost effectiveness, and small demand in biological material, these techniques become widespread and generate massive data sets [START_REF] Mardis | ChIP-seq : welcome to the new frontier[END_REF]. These experiments yield small sequence reads, also called tags, which need to be positioned on the genome. For instance, one transcriptomics experiment delivered ≃ 8 million different 27 bp tags, which were then mapped back to the genome. Only the tags mapping to a unique genomic location served to predict novel transcribed regions and alternative transcripts [START_REF] Sultan | A Global View of Gene Activity and Alternative Splicing by Deep Sequencing of the Human Transcriptome[END_REF]. Generally, further analyses concentrate on those tags mapped to a unique genomic location [START_REF] Barski | High-Resolution Profiling of Histone Methylations in the Human Genome[END_REF]. 1

D R A F T

The goal of tag mapping is to find for each tag the best matching genomic position. The ELAND program, which belongs to the bioinformatic pipeline delivered with the Solexa/Illumina R 1G sequencer, reports first an exact matching location if one is found, and otherwise seeks for locations that differ by 1 or 2 mismatches.

In the vast pattern matching literature, numerous guaranteed algorithms have been described to match exactly or approximately a pattern in a text (i.e. a read in a sequence), but only a few have been implemented to process efficiently tens of thousands of patterns [START_REF] Navarro | Flexible Pattern Matching in Strings -Practical on-line search algorithms for texts and biological sequences[END_REF]. In the context of read mapping, tools must be able to process millions of reads and thus, programs that exploit a precomputed genome index often prove more efficient [START_REF] Li | Mapping short DNA sequencing reads and calling variants using mapping quality scores[END_REF][START_REF] Li | SOAP: short oligonucleotide alignment program[END_REF][START_REF] Smith | Using quality scores and longer reads improves accuracy of solexa read mapping[END_REF][START_REF] Langmead | Ultrafast and memory-efficient alignment of short dna sequences to the human genome[END_REF]. Read mapping tools offer possibilities of approximate matching up to a limited number of differences (generally a few mismatches). However, they usually trade off a guaranteed accuracy for efficiency [START_REF] Jiang | Seqmap : mapping massive amount of oligonucleotides to the genome[END_REF][START_REF] Li | SOAP: short oligonucleotide alignment program[END_REF][START_REF] Smith | Using quality scores and longer reads improves accuracy of solexa read mapping[END_REF][START_REF] Langmead | Ultrafast and memory-efficient alignment of short dna sequences to the human genome[END_REF].

Another specificity of read mapping applications is that further processing considers only reads mapping to a unique position in the genome [START_REF] Barski | High-Resolution Profiling of Histone Methylations in the Human Genome[END_REF]. From a statistical viewpoint, exact matching of a 20 bp read is sufficient to identify a unique position in the human genome [START_REF] Saha | Using the transcriptome to annotate the genome[END_REF][START_REF] Philippe | Using reads to annotate the genome: influence of length, background distribution, and sequence errors on prediction capacity[END_REF]. This implies that, instead of approximately matching full length reads, it may be as adequate to match, i.e. read prefixes, exactly. This would allow to keep the 100% accuracy, while still being efficient. Thus, it is desirable to further investigate whether exact set pattern matching algorithms can be adapted to meet the requirements of read mapping. For instance, it remains open whether an efficient pattern matching algorithm able to process huge read sets without indexing the genome exists.

To perform the mapping task, the user chooses either fast BLAST-like similarity search programs (BLAT [START_REF] Kent | BLAT-The BLAST-Like Alignment Tool[END_REF], MEGABLAST [START_REF] Zhang | A greedy algorithm for aligning DNA sequences[END_REF], or SSAHA [START_REF] Ning | SSAHA: A Fast Search Method for large DNA Databases[END_REF]), or specialised mapping tools (ELAND, TAGGER [START_REF] Iseli | Indexing Strategies for Rapid Searches of Short Words in Genome Sequences[END_REF], RMAP [START_REF] Smith | Using quality scores and longer reads improves accuracy of solexa read mapping[END_REF], SEQMAP [START_REF] Jiang | Seqmap : mapping massive amount of oligonucleotides to the genome[END_REF], SOAP [START_REF] Li | SOAP: short oligonucleotide alignment program[END_REF], MAQ [START_REF] Li | Mapping short DNA sequencing reads and calling variants using mapping quality scores[END_REF], BOWTIE [START_REF] Langmead | Ultrafast and memory-efficient alignment of short dna sequences to the human genome[END_REF], and ZOOM [START_REF] Lin | ZOOM! Zillions of oligos mapped[END_REF]). ELAND is probably the most used one [START_REF] Sultan | A Global View of Gene Activity and Alternative Splicing by Deep Sequencing of the Human Transcriptome[END_REF][START_REF] Boyle | High-Resolution Mapping and Characterization of Open Chromatin across the Genome[END_REF][START_REF] Johnson | Genome-Wide Mapping of in Vivo Protein-DNA Interactions[END_REF]. While mappers were designed to process the huge tag sets output by NGS and allow only a few of substitutions and/or indels, similarity search tools were intended to find local alignments for longer query sequences, but can be twisted to map tags [START_REF] Boyle | High-Resolution Mapping and Characterization of Open Chromatin across the Genome[END_REF][START_REF] Kharchenko | Design and analysis of ChIP-seq experiments for DNA-binding proteins[END_REF]. To speed up the search, both categories of tools follow a filtration strategy that eliminates quickly non-matching regions. The filtration usually requires to match exactly or approximately a short piece of the sequence (e.g., BLAT or SEQMAP). All mappers but one [START_REF] Lin | ZOOM! Zillions of oligos mapped[END_REF] use variants of the PEX filter (as called in [START_REF] Navarro | Flexible Pattern Matching in Strings -Practical on-line search algorithms for texts and biological sequences[END_REF]), which consists in splitting the tag in k + 1 adjacent pieces, knowing that at least one will match exactly when a maximum of k errors are allowed. Logically to accelerate the filtration step, several of these tools exploit an index of the genome's words of length q (or q-mers) [START_REF] Kent | BLAT-The BLAST-Like Alignment Tool[END_REF][START_REF] Ning | SSAHA: A Fast Search Method for large DNA Databases[END_REF][START_REF] Iseli | Indexing Strategies for Rapid Searches of Short Words in Genome Sequences[END_REF][START_REF] Langmead | Ultrafast and memory-efficient alignment of short dna sequences to the human genome[END_REF] 1 , which is stored on disk, loaded in memory once before all searches, and requires a computer intensive preprocessing of the genome [START_REF] Langmead | Ultrafast and memory-efficient alignment of short dna sequences to the human genome[END_REF]. The construction of a human genome index lasts several hours even on powerful servers [START_REF] Langmead | Ultrafast and memory-efficient alignment of short dna sequences to the human genome[END_REF]. Among mapping tools, ZOOM distinguishes itself with a filtration relying on spaced seeds, i.e. matching subsequences instead of pieces [START_REF] Lin | ZOOM! Zillions of oligos mapped[END_REF].

Here we present a computer program MPSCAN 2 , short for Multi-Pattern Scan, that is able to locate multiple reads in a single pass through the searched sequence and study its average time complexity (Section 2). In Section 3, we compare MPSCAN with the fastest of BLAST-like tools and mapping programs in terms of speed and scalability on large tag sets, and also evaluate the accuracy of similarity search tools for this task. We conclude by discussing the practical and algorithmical implications of our findings.

MPSCAN algorithm

MPSCAN, short for Multi-Pattern Scan, is a program for set pattern matching: it searches si-D R A F T multaneously in a text for a set of words (i.e. tags) on a single computer (no parallelisation, no special hardware). To enable fast matching of large tag sets, we combine a filtration/verification approach with a search procedure based on bitwise comparisons, and a compact representation of the tag set. The tags are loaded in memory at the start and indexed in a trie-like structure, while the text is scanned on-the-fly by pieces.

The filtration strategy, which was explored for sets of up to 100, 000 patterns in [START_REF] Salmela | Multipattern string matching with q-grams[END_REF], is the clue of MPSCAN efficiency. Filtration aims at eliminating most positions that cannot match any tag with an easy criterion. Then, verification checks whether the remaining positions truly match a tag. MPSCAN can handle a tag set in which tags differ in length. However, the filtration strategy works with tags of identical length; thus, it creates internally a set in which all tags are cut to the size of the smallest one (call this size l). The verification tests whether a complete tag matches. Filtration has been extensively applied to speed up similarity search algorithms, as in BLAST or BLAT [START_REF] Kent | BLAT-The BLAST-Like Alignment Tool[END_REF]. MPSCAN's criterion relies on the fact that a matching window must share subwords of length q with the tags. Subwords of length q are called q-mers.

For verification purposes we index the tag set with a trie [START_REF] Navarro | Flexible Pattern Matching in Strings -Practical on-line search algorithms for texts and biological sequences[END_REF]. To save space, we prune the trie at nodes where the remaining suffixes can be stored in approximately 512 bytes. The suffixes are sorted for easier access during the verification phase. The pruned trie allows for efficient lookup speed and memory usage with patterns sharing common prefixes, and the remaining suffixes are efficiently packed, without compromising efficiency. Without pruning, the trie alone would result in unacceptably huge memory usage, as a single trie node takes up dozens of bytes in the form of pointers alone.

Filtration strategy

Let us explain the filtration scheme with an example. Assume a set of 3 tags of length l = 8: {P 1 , P 2 , P 3 } = {accttggc, gtcttggc, accttcca}, and set q to 5. The overlapping 5-mers of each pattern are given in Figure 2. For a text window W of length 8 to match P 1 , we need that the subword starting at position i in W matches the i th q-mer of P 1 for all possible i, and conversely. Now, we want to filter out windows that do not match any tag. If the subword starting at position i in W does not match the i th q-mer of neither P 1 , P 2 , nor P 3 , then we are sure W cannot match any of the tags. Thus, our filtration criterion to surely eliminate any non-matching window W is to find if there exists a position i such that the previous condition is true.

From a set of tags, MPSCAN builds a single q-mer generalised pattern (Fig. 2). A generalised pattern allows several symbols to match at a position (like in a PROSITE pattern where a position e.g. [DENQ] matches symbols D, E, N, or Q). However, here each q-mer is processed as a single symbol. Then, MPSCAN searches for this generalised pattern in the text with the Backward Nondeterministic DAWG Matching (BNDM) algorithm [START_REF] Navarro | Flexible Pattern Matching in Strings -Practical on-line search algorithms for texts and biological sequences[END_REF], which efficiently uses bitparallelism. The basic idea of the algorithm is to recognize reversed factors (or substrings) of the pattern when scanning a window backward. When the scanned suffix of a window matches a prefix of the pattern, we store this position as a potential start of the next window. When we reach a point in the backward sscanning where the suffix of the window is not a factor of the pattern, we shift the window forward based on the longest recognized prefix of the pattern except for the whole pattern. If no prefix was recognized, the length of the shift is lq + 1. To achieve this efficiently, we initialize during preprocessing a bit vector B[s] for each q-mer s, where the i th bit in the bit vector is one if the q-mer appears in the reversed pattern in position i. During searching the algorithm maintains a state vector E, where the i th bit is one if the scanned q-mers match the pattern starting at position i. When we read a new q-mer s, the state vector is updated as follows:

E = (E ≪ 1) & B[s] ,
where ≪ shifts the bits to the left and & performs a bitwise and of the two bit vectors. If the first bit in E is one, we have read a prefix of the pattern, and if all the bits in E are zero, the scanned

D R A F T 1: i ← l -q + 1 2: while i ≤ n -q + 1 do 3: j = 1; last ← l -q + 1 4: E = B[s i ] {s i is the i th q-mer of the scanned sequence} 5:
while true do

6: if first bit in E is one then 7:
{the scanned window is a prefix of the pattern} 8:

if j = l -q + 1 then 9:
verify an occurrence; break 10:

end if 11: last ← l -q + 1 -j 12:
end if [START_REF] Jiang | Seqmap : mapping massive amount of oligonucleotides to the genome[END_REF]:

if E = 0 then 14:
break {the scanned window is not a factor of the pattern} 15:

end if

16:

E ← (E ≪ 1) & B[s i-j ] {s i-j
is the (ij) th q-mer of the scanned sequence} 17:

j ← j + 1 18:
end while

19:
i ← i + last 20: end while suffix of the window does not match any factor of the pattern. Figure 1 gives the pseudo code for the filtration phase.

Optimal average complexity of MPSCAN

For a single pattern, BNDM has a sublinear average complexity with respect to the text length n; in other words, it does not examine all characters of the text. The combination of the BNDM algorithm with q-mers was first studied in [START_REF] Salmela | Multipattern string matching with q-grams[END_REF], where it was shown sublinear. Here we prove that, if one sets the value of q relatively to the total number of tags r, MPSCAN average time complexity is not only sublinear with respect to n, but optimal. Indeed, the average complexity of the set pattern matching problem is Ω(n log c (rl)/l) (cf. [START_REF] Navarro | Average complexity of exact and approximate multiple string matching[END_REF]) and we prove:

Theorem 1 The average time complexity of MPSCAN for searching r patterns of size l in a text

of length n over an alphabet of size c is O(n log c (rl)/l) if q = Θ(log c (rl)).

Proof:

We want to prove that the average time complexity of MPSCAN for searching r patterns of size l in a text of length n over an alphabet of size c is O(n log c (rl)/l) if q = Θ(log c (rl)).

Practically, c equals 4 for DNA sequences.

Remember that MPSCAN processes the text in windows and it always reads the windows from right to left. We will call a window good if the last q-mer of the window does not match any pattern in any position. All other windows are called bad. In a good window, MPSCAN reads only the last q-mer and then shifts the window by lq + 1 characters. In a bad window MPSCAN reads up to l characters and then shifts the window by at least one position (but often more than that).

For the purposes of the proof, the filtering phase of MPSCAN is divided into subphases that we define as follows. Let W i , i = 1, 2, . . . be the windows scanned by MPSCAN. The first subphase starts with W 1 . Let W s be the first window of a subphase. Only a good window can end a subphase, but not all of them do. Indeed, the first good window in the series of windows indexed with i := s + qk, i.e. W s+qk , with k = 0, 1, . . . is the last window of that subphase. The next D R A F T window starts a new subphase. It follows that each subphase consists of X groups of q windows and one good window, with X ≥ 0 being a random variable. Each of the X groups of q windows starts with a bad window and the rest q -1 windows may be of any type. Figure 3 shows an example of dividing the windows into subphases. The type of a window following a group of q windows is independent of the first window of the group, because the pattern has been shifted by at least q positions between them and the type of a window is determined solely by the last q-mer of the window. If q ≤ lq + 1, the type of a window after a good window is also independent of the good window, i.e. the q-mer determining the type of the next window contains only characters that have not been previously read. Because each subphase contains at least one good window, the text of length n will surely be covered after O(n/(lq + 1)) subphases.

The probability that a random q-mer matches any of the patterns in any position is at most rl/c q , because there are c q different q-mers and at most rl of these can occur in the patterns (r patterns each of length l). This is also the probability that a window is bad. In a bad window MPSCAN reads the q-mers from right to left. It surely stops when it encounters a q-mer that does not match any q-mer in any of the patterns. In the worst case, MPSCAN reads the whole window and compares it against all the patterns taking O(rl) time. Note that this a very pessimistic estimate. In practise, verification is not triggered in all bad windows and even then MPSCAN compares the window against only a few patterns.

In a good window, MPSCAN reads q characters. Therefore in one subphase of filtering, the number of characters read by MPSCAN is less than

O(q) • P(X = 0) + ∞ ∑ i=1 (O(q) + i • q • O (rl)) • P(X = i) D R A F T = O(q) + ∞ ∑ i=1 i • q • O (rl) • P(X = i) ≤ O(q) + q • O (rl) ∞ ∑ i=1 i rl c q i .
This sum will converge if rl/c q < 1 or equally if q > log c (rl) and then

O(q) + q • O (rl) ∞ ∑ i=1 i rl c q i = O(q) + q • O (rl) rl c q 1 -rl c q 2 = O(q) + q • O (rl) rl • c q (c q -rl) 2
If we choose q ≥ a log c (rl), where a > 1 is a constant, then c q ≥ r a l a . Because a > 1, c qrl = Ω(c q ) and therefore

1 c q -rl = O 1 c q .
Now, the work done by the algorithm in one subphase takes less than

O(q) + q • O (rl) rl • c q (c q -rl) 2 = O(q) 1 + O r 2 l 2 c q c 2q = O q • r 2 l 2 c q = O(q)
if a ≥ 2. There are O(n/(lq + 1)) = O(n/l) subphases and the average complexity of one subphase is O(q). Overall the average case complexity of filtering in MPSCAN is thus

O n l • q = O(n log c (rl)/m)
if q = a log c (rl) ≤ lq + 1 for a constant a ≥ 2. The condition q ≤ lq + 1 is equivalent to q ≤ (l + 1)/2. Such a q can be found if 2 log c (rl) < (l + 1)/2 or equally if r < c 1 4 (l+1) /l. The above proof predicts that a good choice for q would be 2 log c (rl), but in practice a good choice for q seems to be roughly log c (rl). If we analysed the complexity of bad windows and verification more carefully, we could bring the theoretical result closer to the practical one.

Comparison

The MPSCAN algorithm offers a good theoretical average complexity, but how does it behave in practice and compare to other solutions? We perform search tests to investigate MPSCAN behavior and to compare it to either ultra-fast similarity search tools used for this task (BLAT, MEGABLAST, and SSAHA) or to mapping tools. For each tool, we set its parameters to let it search only for exact matches (which is for instance impossible with MAQ). ELAND could not be included in the comparison for we do not have a copy of the program.

Let us first recall some distinguishing features of those similarity search programs. They were designed to search for highly similar sequences faster than BLAST and exploit this high level of similarity to speed up the search. All are heuristic, but are by design better and faster than BLAST for searching exact occurrences of reads in a genome. MEGABLAST proceeds like BLAST: it scans the genome with the query read, which takes time proportional to the genome size. BLAT and SSAHA both use an index of the genome that records the occurrence positions of q-mers in the genome for some length q. Then, they search for all q-mers of the query in the index to determine which regions of the genome likely contain occurrences. This requires a time proportional to the read size. Note that q is the key parameter to balance between sensitivity and speed. Hence, BLAT and SSAHA avoid scanning repeatedly the whole genome, but require to precompute an index.

D R A F T

Speed and memory with respect to text length

First, we compared the running times of MPSCAN and of all similarity search programs with a set of 200 K-tags and texts of increasing length (Fig. 6, time in log scale). For all programs except BLAT, the running time increases less than linearly with the text length (but BLAT follows the same trend above 50 Mbps). For instance, MPSCAN takes 1.1 sec to search in 10 Mbps of Human chromosome 1, but only 5.6 sec in 247 Mbps: a 5-fold increase of the running time for a 25fold increase in length. This illustrates well the sublinear time complexity of MPSCAN (Th. 1), which proves to be faster than the reference methods. The behavior is logical: MEGABLAST and MPSCAN first build their search engine, and then scan the text by pieces. The time spent for initialisation of the engine is better amortised with longer texts. This also explains why the memory used by MPSCAN is independent of the text length.

Second, we measured the time and memory footprint needed by MPSCAN and mapping tools to search the complete human genome with one million 27 bp tags. ZOOM requires 17 minutes and 0.9 Gigabytes, RMAP takes 30 min and 0.6 Gb, SEQMAP performs the task in 14 min with 9 Gb, BOWTIE runs in > 6 min with 1.4 Gb and MPSCAN needs < 5 min using 0.3 Gb. MPSCAN runs faster than BOWTIE although the latter uses a precomputed index, and it is three times faster than SEQMAP, the third most efficient tool.

Scalability with respect to number of patterns

The central issue is the scalability in terms of number of tags. To investigate this issue, we plot their running times when searching for increasing tag sets (Fig 4). The comparison with similarity search tools is shown in Figure 4a. BLAT is by far the slowest tool, while MEGABLAST's time increases sharply due an internal limitation on the maximal number of tags searched at once, which forces it to perform several scans. SSAHA takes full advantage of its index with large pattern sets, and becomes 10 times faster than MEGABLAST. However, MPSCAN runs always faster than BLAT, MEGABLAST, and SSAHA. Especially for more than 400 K-tags, it outperforms other programs by almost an order of magnitude (9.8 s for 700 K-tags instead of 78 for SSAHA, 670 for MEGABLAST and 4, 234 s for BLAT). Importantly, the times needed by other programs increase more sharply with the number of tags than that of MPSCAN, especially after 100K, auguring ill for their scalability beyond a million tags.

Beyond that, we consider specialised mapping tools whose behavior is illustrated in Fig- ure 4b. For this, we used 6.5M 27 bp RNA Polymerase II ChIP-seq tags sequenced in an erythroleukemia cell line (HK652, GEO GSM325934) and took increasing subsets every million tags. All tools exhibit a running time that increases linearly with the number of tags: a much better scalability than similarity search tools. Compared to similarity search tools, all mappers behave similarly, probably due to the resemblance of their filtration algorithm.

Both BOWTIE and SOAP-V2 use a Burrows-Wheeler-Transform index with a similar exact matching algorithm, but it benefits more BOWTIE than SOAP-V2, making BOWTIE the faster of mapping tools. This emphasises how much implementation issues influence efficiency. Among non-index based programs, ZOOM exhibits a behavior close to that of BOWTIE above 3M tags, showing that ultrafast running times are not bound to an index. For moderate tag sets (< 4M tags) MPSCAN is two to four times faster than ZOOM, its fastest competitor in this category. Even if MPSCAN's running time increases from 4 to 5M tags due to a multiplication by 5 of the number of matches, it remains the fastest of all tools for exact matching. This shows that exact set pattern matching can be highly efficient even without a genome index and answers the question asked in the introduction. MPSCAN's filtration strategy is logically sensitive to the ratio #reads/4 q , which suggests that using longer computer-words (on 64-bit processors) will improve its efficiency and scalability. D R A F T

Accuracy

The MPSCAN algorithm is guaranteed 100% accurate (and extensive tests have shown that the MPSCAN program also is): it reports all patterns' occurrences (100% sensitive) and only these (100% selective) [START_REF] Salmela | Multipattern string matching with q-grams[END_REF][START_REF] Navarro | Flexible Pattern Matching in Strings -Practical on-line search algorithms for texts and biological sequences[END_REF].

Despite the availability of specialised mapping tools, popular heuristic similarity search program like BLAT are still used for read mapping [START_REF] Kharchenko | Design and analysis of ChIP-seq experiments for DNA-binding proteins[END_REF], for they can find distant alignments. However to our knowledge, their accuracy has never been assessed in this context. We performed a thorough comparison of their exact matching capacity, since it should be the easiest part of the task. Our results show it is a complex matter: especially their sensitivity is influenced by the numbers of occurrences, the relative length of seeds compared to matches, the parameters set for both building the index and searching.

While all tools (SSAHA, BLAT, and MEGABLAST) achieve their best accuracy for long patterns (for ≥ 60 bp, i.e. when the seed is guaranteed to fall in each occurrence), all encounter problems finding short patterns (≤ 30 bp). Index and parameters must be adapted to gain sensitivity at the expense of time and flexibility (one cannot exploit the same index for different tag lengths), which is an issue for digital transcriptomic and ChIP-seq data (≤ 25 bp in [START_REF] Kim | Polony Multiplex Analysis of Gene Expression (PMAGE) in Mouse Hypertrophic Cardiomyopathy[END_REF][START_REF] Boyle | High-Resolution Mapping and Characterization of Open Chromatin across the Genome[END_REF][START_REF] Johnson | Genome-Wide Mapping of in Vivo Protein-DNA Interactions[END_REF]). For instance, with 30 bp patterns, all are less than 50% sensitive with pattern sets ≥ 10, 000 (Fig. 4). For both parameter sets used with BLAT, its sensitivity remains below 0.6 whatever the tag length. The number of tags also has a negative influence on the sensitivity of similarity search tools (data not shown). However, it is logical that similarity search tools have limited accuracy, since they were not designed for exact pattern matching.

The accuracy of mapping tools that allow both exact and approximate matching should be evaluated globally and their dependence to several parameters (tag length, error types, tag number, genome length) should be investigated. Indeed, the underlying definitions of a read best match, the strategies for finding it, as well as the notion of approximation differ among tools, hampering this comparison. This is beyond the scope of this paper. Nevertheless, we have analysed the accuracy of ELAND. Although, we do not have access to the program, some of ELAND's raw results can be downloaded from public repositories like GEO. ELAND searches for exact and approximate matches with ≤ 2 mismatches. We analysed the subset of mapped tags in the ELAND output of the NRSF ChIP-seq data set [START_REF] Johnson | Genome-Wide Mapping of in Vivo Protein-DNA Interactions[END_REF]. ELAND finds only approximate matches for 442, 766 tags, while MPSCAN locates an exact match for 59, 571 of these tags (13% of them).

Such an inaccuracy may impact the final positioning of protein binding or DNA modification sites. This comparison illustrates the difficulty of searching for large tag sets in sequences and the benefit of using a guaranteed pattern matching algorithm for this task.

Relevance of exact vs approximate mapping

Currently, new sequencers yield short tags (i.e. < 30 bp) in Digital Gene Expression, RNA-Seq, and ChIP-seq experiments (14, 20, and 27 bp in [START_REF] Kim | Polony Multiplex Analysis of Gene Expression (PMAGE) in Mouse Hypertrophic Cardiomyopathy[END_REF][START_REF] Boyle | High-Resolution Mapping and Characterization of Open Chromatin across the Genome[END_REF][START_REF] Sultan | A Global View of Gene Activity and Alternative Splicing by Deep Sequencing of the Human Transcriptome[END_REF] respectively). Technological developments aim at increasing the tag length to improve the probability of a read to match a unique genomic location. However, the error probability also increases with tag length [START_REF] Kharchenko | Design and analysis of ChIP-seq experiments for DNA-binding proteins[END_REF][START_REF] Philippe | Using reads to annotate the genome: influence of length, background distribution, and sequence errors on prediction capacity[END_REF]. Altogether, the tag length has an opposite influence on the probabilities of a tag to be mapped and to be mapped at a unique location.

To evaluate the relevance of exact versus approximate matching, we did the following experiment with a Pol-II ChIP-seq set of 34 bp tags (GEO GSM325934). If one maps with MPSCAN the full length tags, 86% remain unmapped and 11% are uniquely mapped. With at most two mismatches, ELAND finds 14% of additional uniquely mapped tags (categories U1 and U2), while mapping the 20 bp prefix of each tag with MPSCAN allows to map 25% of all tags at unique positions (14% more sites than with full length tags).

This result suggests that optimising the final output of a sequence census assay in terms D R A F T of number of uniquely mapped locations is a complex issue. Approximate mapping is seen as a solution to detect more genomic sites, but it often maps tags at multiple locations [START_REF] Faulkner | A rescue strategy for multimapping short sequence tags refines surveys of transcriptional activity by CAGE[END_REF]. In fine, exact matching may turn out to be a relevant alternative strategy compared to approximate matching. Thus, the proposed filtration algorithm may be useful in read mapping applications, especially if one considered mapping a substring of the original reads. A more in-depth investigation of this issue is exposed in [START_REF] Philippe | Using reads to annotate the genome: influence of length, background distribution, and sequence errors on prediction capacity[END_REF].

Discussion

Key biological questions can be investigated at genome scale with new sequencing technologies. Whether in genomic, transcriptomic or epigenomic assays, millions of short sequence reads need first to be mapped on a reference genome. This is a compulsory step in the bioinformatic analysis. We presented an efficient program, MPSCAN, for mapping tags exactly on a genome, evaluated its relevance for read mapping, and compared it to two classes of alternative solutions: i) ultrafast similarity search tools and ii) specifically designed mapping tools. We summarise below some valuable evidence and take-home messages brought by this study. Similarity search tools are inappropriate for mapping exactly short patterns ≤ 40 bp, since their sensitivity remains too low (< .5 for 30 bp long tags). Whatever the number of seeds required to examine a hit, BLAT is the least sensitive among the tested similarity search tools. Its sensitivity never reaches 0.6, even with patterns up to 100 bp. In other words, similarity search tools miss many exact matching locations, which are considered to be the most secure locations in many applications [START_REF] Boyle | High-Resolution Mapping and Characterization of Open Chromatin across the Genome[END_REF][START_REF] Johnson | Genome-Wide Mapping of in Vivo Protein-DNA Interactions[END_REF]. In general, the scalability of similarity search tools is not satisfactory for tag mapping: both the speed of processing and the sensitivity suffer when the number of tags becomes large.

Mapping tools are adequate for this task. They enable the user to map up to millions of tags fast on the human genome, and scale up well. Nevertheless, differences in speed can be important: e.g., an order of magnitude for mapping 2M tags between MPSCAN and SOAP-V2. If most algorithms are similar, from the user viewpoint the programs are not equivalent: neither in flexibility, ease of use, speed, options, nor in accuracy.

From the algorithmic viewpoint, our results suggest that indexing is not required to perform exact mapping of tags on long sequences. In the class of similarity search tools, the superiority in speed of SSAHA compared to BLAT and MEGABLAST is due to its index, but also to its lack of verification, which induces a poor specificity. In our comparison of seven programs (the largest we are aware of), BOWTIE seems the fastest among mapping tools, but never beats the performance of MPSCAN for exact mapping.

ZOOM, which exploits spaced seeds in its filtration scheme, compares favorably in speed to tools using the splitting strategy or PEX filter, such as SEQMAP, RMAP, SOAP. This suggests the superiority of spaced seeds. However, this superiority has a price in terms of flexibility: sets of spaced seeds are specifically designed for a certain tag length and maximum number of mismatches, and different sets corresponding to different parameter combinations are hard coded in ZOOM. For instance, a set of 4 spaced seeds of weight 13 was manually designed to search for 33 bp tags [START_REF] Lin | ZOOM! Zillions of oligos mapped[END_REF]. Hence, adaptation of ZOOM to a new setup requires the design of specific seeds, which is a theoretically hard and practically difficult problem [START_REF] Kucherov | Multiseed Lossless Filtration[END_REF][START_REF] Ma | On the complexity of the spaced seeds[END_REF][START_REF] Nicolas | Hardness of optimal spaced seed design[END_REF]. The present limitation of ZOOM to patterns up to 64 bp is certainly due to this bottleneck.

In conclusion, we presented an exact set pattern matching program, MPSCAN, which is based on a filtration scheme that had never been applied to read mapping. Our current implementation has pushed the limit on the number of tags by two orders of magnitude compared to previous pattern matching algorithms [START_REF] Navarro | Flexible Pattern Matching in Strings -Practical on-line search algorithms for texts and biological sequences[END_REF][START_REF] Salmela | Multipattern string matching with q-grams[END_REF]. We conducted thorough comparisons with similarity search algorithms and mapping tools in term of speed and scalability. Our experiments revealed that BLAT-like tools are inadequate for short read mapping both in terms of scalability and of sensitivity, which, to our knowledge, has never been reported before. From the algorithmic D R A F T viewpoint, we demonstrated the average running time optimality of MPSCAN, which turns out to be very efficient in practice. Compared to mapping tools for exact mapping, MPSCAN runs faster and scales well: it can even compete in efficiency with programs using a sophisticated genome index, like BOWTIE. Since it uses no index, MPSCAN combines flexibility, low memory footprint, and high efficiency, while avoiding a time consuming index precomputation (cf. building times in [START_REF] Langmead | Ultrafast and memory-efficient alignment of short dna sequences to the human genome[END_REF]). Finally, we provide evidence that exact matching approaches can be relevant for read mapping applications, especially in the perspective of longer reads. It remains open to find filtration strategies that achieve efficient "near exact" mapping.

With future generation of sequencers, which promise further increases in sequencing capacity, read mapping may become a bottleneck. Further research in theoretical and practical pattern matching will be needed to tackle this challenging question. D R A F T Influence of tag length on sensitivity (with r = 10, 000 tags). BLAT-m1 and BLAT-m2 gives BLAT's sensitivity when the filtration criterion asks for one or two seed matches, respectively; BLAT-m1 found necessarily more matches than BLAT-m2. However, here their curves are superimposed. The sensitivity of similarity search tools is low (< 0.5) for tags ≤ 30 bp and reaches a maximum for MEGABLAST and SSAHA at ≥ 60 bp.

Figure 1 :

 1 Figure 1: Pseudo code for the filtration phase of MPSCAN.

Figure 2 :

 2 Figure 2: Filtration scheme of MPSCAN. (a) A set of 3 tags of length l = 8. (b) The overlapping 5-mers starting at position 1 to 4 (resp. in light, dark, normal, very dark gray) of each tag. (c) The generalised 5-mers pattern for the set of tags.

Figure 3 :

 3 Figure 3: Dividing the search phase into subphases when q = 2. The windows, whose type influences the division, are shown in boldface.

Figure 4 :Figure 5 :

 45 Figure 4: Evaluation of scalability. Search times on chromosome 1 (247 Mbp) for increasing tag sets. (a) Comparison with similarity search tools. Search times of BLAT, MEGABLAST, SSAHA, MPSCAN in seconds for 21 bp LongSAGE tags, for sets of 10, 50, 100, 200, 300, 400, and up to 700 Kilo-tags (K-tags). Both axes have logarithmic scales. The curve of MPSCAN running time is almost flat: for instance doubling the tag set from 200 to 400 K-tags yields a small increase from 5.6 to 6.4 s Its time increases in a sublinear fashion with the number of tags. For all other tools, the increase of the tag set gives rise to a proportional growth of the running time. E.g., SSAHA needs 23 s for 200 K-tags and 54 s for 400 K-tags. (b) Comparison with mapping tools: Search times of RMAP, SEQMAP, SOAP (v1 & v2), ZOOM, BOWTIE and MPSCAN in seconds (log scale) for increasing subsets of 27 bp ChIP-seq tags. All tools behave similarly and offer acceptable scalability. MPSCAN remains the most efficient of all and can be 10 times faster than tools like SEQMAP or RMAP. Times do not include the index construction time.

Figure 6 :

 6 Figure 6: Search times of BLAT, MEGABLAST, SSAHA, MPSCAN in seconds for 200 Kilotags (LongSAGE tags of 21 bp), on increasing pieces of length 5, 10, 50, 100, and 247 Mbp of Human chromosome 1. Both axes have logarithmic scales. These curves illustrate the sublinear increase of time with respect to text length for all tools except BLAT, and the superiority of MPSCAN in running time. 12

  {P 1 , P 2 , P 3 } = {accttggc, gtcttggc, accttcca}

		(a)
	1 2 3 4 5 6 7 8	1 2 3 4 5 6 7 8	1 2 3 4 5 6 7 8
	P 1 a c c t t g g c	P 2 g t c t t g g c	P 3 a c c t t c c a
	a c c t t	g t c t t	a c c t t
	c c t t g	t c t t g	c c t t c
	c t t g g	c t t g g	c t t c c
	t t g g c	t t g g c	t t c c a
		(b)
	[acctt, gtctt][ccttg,tcttg, ccttc][cttgg, cttcc][ttggc,ttcca]

As well as the version

2.0 of SOAP 2 MPSCAN is freely available for academic users and can be downloaded at http://www.atgc-montpellier.fr/ mpscan.

Acknowledgments: This work was supported by Université Montpellier II [grant BIO-MIPS], Academy of Finland [grant 111060]. We gratefully thank L. Duret, A. Boureux, T. Commes, L. Bréhèlin for helpful comments.