Marta Severo
email: msevero@parisnanterre.fr

Robin Lamarche-Perrin
email: robin.lamarcheperrin@lip6.fr

Mining Political Opinion on Twitter Challenges and Opportunities of Multiscale Approaches

Social research on public opinion has been affected by the recent deluge of new digital data on the Web, from blogs and forums to Facebook pages and Twitter accounts. This fresh type of information useful for mining opinions is emerging as an alternative to traditional techniques, such as opinion polls. Firstly, by building the state of the art of studies of political opinion based on Twitter data, this paper aims at identifying the relationship between the chosen data analysis method and the definition of political opinion implied in these studies. Secondly, it aims at investigating the feasibility of performing multiscale analysis in digital social research on political opinion by addressing the merits of several methodological techniques, from content-based to interaction-based methods, from statistical to semantic analysis, from supervised to unsupervised approaches. The end result of such an approach is to identify future trends in social science research on political opinion.

Introduction

The study of political opinion is a traditional field in social sciences. Researches related to elections, political parties and representatives have been filling the pages of social sciences journals for the last century. They often rely on empirical analysis based on traditional methods such as opinion polls, surveys, focus groups, or interviews. More recently, the development of the World Wide Web has been responsible for important changes in this field by offering new arenas for expression for both politicians and citizens. From the exemplary case of Barack Obama until the more recent use of big data in the Trump-Clinton competition, the Internet has become a key tool to convince voters, organise supporters and spread political messages. If ten years ago, websites, blogs and forums were the main spaces of political exchanges, today Facebook, Twitter and YouTube seem to be the strategic places for expressing and disseminating political opinions and also for debating with candidates, among friends or with strangers about political topics. All these online interactions between politicians and citizens, but also between journalists, party representatives and other kinds of influencers, generate a large amount of digital data 1 , commonly called big data 2 , that have been recently introduced in social research in order to studying political opinions of individuals and groups. According to numerous scholars, techniques for mining opinions on social media can be used as an alternative to traditional methods.

Facing such situation, this paper aims at studying the impact of the use of social media data on the social research on political opinion, by considering the specific case of studies based on Twitter data. When compared to other social media, Twitter has received a lot of attention from scientists both because of how easier it seems to make the collection of data 3 , and because of the wide scope of topics covered by online exchanges. Those studies vary according to the size of corpora, from small to big data, to the type of data, from content-to interaction-based approaches, and of methods. As regards to methods, it is generally assumed that research in this 1 If Web data are surely an important novelty for social research, their use is not so straightforward and calls for a critical approach [START_REF] Hogan | From invisible algorithms to interactive affordances: Data after the ideology of Machine Learning[END_REF]. In particular, the technical and commercial issues related to data access, the legal issues related to privacy and copyright and, last but not least, the issues of veracity and representativeness of these data don't have to be overlooked [START_REF] Severo | Soft Data and Public Policy: Can Social Media Offer Alternatives to Official Statistics in Urban Policymaking?[END_REF]. 2 In this paper, big data generally refers to "datasets that are large in both size and complexity, with which new algorithmic techniques are required in order to extract useful information from them" (Holmes, 2017, p. 7). This is why we later refer to the challenge of multiscale analyses of big data, which is the ability in computer science to apply classical algorithms to larger problems. Hence, we are not interested here in limitations regarding databases management, that relate more to storage constraints than to analysis constraints.

3 Twitter provides APIs for collecting tweets. These APIs have several limitations about the size, the duration and the type of corpora that can be collected. Nevertheless, they, being freely available, have drawn a lot of attention of scholars. field needs to go beyond the opposition between quantitative and qualitative techniques 4 and find new solutions for the "redistribution of methods" [START_REF] Marres | The redistribution of methods: on intervention in digital social research[END_REF]. While big data analyses have encountered several difficulties in the assessment of their validity, evidence based on small data 5 has appeared hard to be applied to larger scales. This is why scientists are currently assessing new mixed methodological solutions in order to develop "quali-quantitative" approaches [START_REF] Venturini | The social fabric: Digital traces and qualiquantitative methods[END_REF].

Considering the variety of these studies, our first goal is to outline the state of the art in the research concerned with this field. The merits of completing a state of the art of such recent and vast literature not only lie in the possibility to compare case studies and methodological solutions but foremost in the exploration of the different definitions of political opinion used in these studies. Eventually, it will be interesting to see whether the use of new data coming from social media, and especially the exploitation of large corpora considered by the authors of the studied papers as big data, makes possible to build a genuine new approach for studying political opinions able to investigate new dimensions of this object or whether the approach to political opinion of these studies have nothing different from researches obtained with traditional techniques. So, our ultimate goal is not to monitor a comparative study of empirical solutions but to disclose the (implicit or explicit) theory that these studies entail.

Then, based on the state of the art, our second goal is to verify if a new approach in social research on political opinion could be based on multiscale techniques. Indeed, in the analysed corpus, multiscale approaches have emerged as the main novelty compared to traditional statistical techniques. Differently from statisticians, some data scientists 6 promise to social 4 This opposition has been defined in several ways. A very simple definition can be that: "quantitative research is empirical research where the data are in the form of numbers… qualitative research is empirical research where the data are not in the form of numbers" (Punch, 1998, p. 4). Here, with these terms, we try to identify to two different approaches to social research. Quantitative methods are used to quantify the research object by way of generating numerical data or data that can be transformed into usable statistics. Qualitative methods, that are generally based on unstructured or semi-structured techniques (focus groups, interviews, observation, etc.), are mainly exploratory and are meant to study reasons, opinions or motivations. 5 With small data, we refer to data that is "small" enough for human comprehension. It is data in a volume and format that makes it accessible, informative and actionable. This kind of data has proved to be very useful for empirical research. Yet, several methodological issues are raised when trying to apply methods and verify evidence obtained on small data through the analysis of big data corpora. 6 Data science is used as a "concept to unify statistics, data analysis, machine learning and their related methods" in order to "understand and analyse actual phenomena" with data [START_REF] Hayashi | What is Data Science? Fundamental Concepts and a Heuristic Example[END_REF]. However, several scholars observed that there is no difference between data scientists and statisticians. Here, we use the term in order to identify a more interdisciplinary approach to data scientists to be able to reproduce similar analyses at different scales, from small to big and vice versa, without loosing in quality. Considering that, our purpose it to investigate the feasibility of performing multiscale digital social research on political opinion, in order to apply qualitative approaches to larger corpora or, even more challenging, to exploit big data approaches while simultaneously meeting the epistemological requirements of qualitative analysis. At the individuals' level, the automatic measurement and quantification of political opinion from social media data are challenged by the limited content of micro-blogging exchanges, by its often ambiguous, ironic, or paradoxical nature, and by the multimedia nature of a message that can include images, URLs, and emoticons. At the system's level, the analysis of activity traces of several million individuals requires algorithmic breakthroughs so that traditional methods are efficient at larger scales. This paper thus proposes to address the merits of general methodological options for the multi-scale analysis of political opinions on Twitter, from content-based to interaction-based methods, from statistical to semantic analysis, from supervised to unsupervised 7 approaches. Regarding the latter opposition, we will discuss in detail the possible statuses of qualitative knowledge within quantitative analysis, whether they are responsible for a priori formalising the problem (supervised approaches) or a posteriori interpreting the results (unsupervised approaches), thus constituting a practical instance of the classical epistemological opposition between deduction and induction. More generally, current challenges of machine learning, that is the use of artificial intelligence to get computer to "learn" from data, to infer new models, and to act without being explicitly programmed, will be addressed in this paper as practical re-actualisations of classical issues within the realm of digital data. If these questions are not new, big data makes them actual.

As a final result, we intend to identify future trends in social sciences research on political opinion and to support the adoption of a solid sociological methodology, which will preserve empirical sociology from the "oncoming crisis" [START_REF] Savage | The coming crisis of empirical sociology[END_REF].

Political opinion on Twitter: a state of the art

Political Opinion and Opinion Polls

Before moving on to Twitter, it may be useful to ponder the various literature on opinion polls since this approach could prove relevant in several studies involving Twitter. If the use of polls dates back to the end of the 19 th century [START_REF] Cayrol R | Opinion, sondages et démocratie[END_REF], their popularity really kicked off in 1936 including statistics but also mathematics, information science, and computer science and using automated algorithms. 7 Supervised approaches are based on the a priori formalisation of expert knowledge, for example through the manual annotation of data, while unsupervised approaches focus on the a posteriori interpretation of statistical results, typically performed on unlabelled data.

when George Gallup was able to predict Roosevelt's victory. In France, Jean Stoetzel established the first opinion polls in 1938 when he founded the Institut francais d'opinion publique. Ever since polls were created, measuring public opinion has gone hand in hand with organizing opinion polls. Polls are based on the principle that the opinion of a sample chosen among carefully selected likely voters can be representative of the opinion of the greater crowd. As noted by Loïc [START_REF] Blondiaux | La fabrique de l'opinion. Une histoire sociale des sondages[END_REF], for many years, the success of polls has been responsible for overlooking the value of opinions from a theoretical point of view.

In the last fifty years, scholars have developed controversial positions about the validity of polls. Particularly famous is the essay written by Pierre [START_REF] Bourdieu | L'opinion publique n'existe pas[END_REF] in which he challenges views on opinions by stating that opinions do not exist so as to underline that actual opinions differ from what is measured by opinion polls. Bourdieu claims that opinion, as measured in polls, is an artefact created by researchers, who therefore input their own questions, and possibly their own answers. Conversely, [START_REF] Page | The Rational Public: fifty years of Trends of Americans' Policy Preferences[END_REF] consider opinions as real, measurable, and rational.

In their view, it is possible to rely solely on survey data as referents for public opinion. Roland Cayrol (2011) underlines that the purpose of polls is not to know the opinions of individuals but the aggregate public opinion. Loïc [START_REF] Blondiaux | La fabrique de l'opinion. Une histoire sociale des sondages[END_REF] proposes an intermediary position. According to him, even if polls are useful for studying public opinion, it does not mean that opinion and polls are the same thing. Similarly, [START_REF] Ginsberg | The Captive Public: How Mass Opinion Promotes State Power[END_REF] underlines that polls' answers are the result of the interaction between an opinion and a query tool: therefore polls do change opinions.

This condensed review of different positions on opinion polls is instrumental in highlighting two decisive points that will be useful for our subsequent analysis. First, there is confusion between the concept of aggregate public opinion (where "opinion" is always singular) and the one of individual opinions (in the plural). Taking one approach or the other has important consequences on the empirical techniques that come useful for analysing political opinion. Therefore, if we look at it from the viewpoint of social statistics [START_REF] Reynié | Le nombre dans la politique moderne[END_REF]) and consider that one opinion equals another and that, consequently, public opinion is an aggregate phenomenon, it means that opinion polls are to be considered as an effective technique of measurement. Conversely, in the case where we consider opinions as consistently related to the individual, we will need methods that are able to measure the contribution of each person and the interaction between each other. Yet, if there is almost general agreement that opinion polls only allow for investigating the aggregate dimension of the opinion, literature on the subject is not so straightforward in proposing alternatives to polls when investigating individual opinions. This brings us to our second point: the importance played by the researcher's choices and the adopted method. It appears quite clear that studying the definition of political opinion should start precisely from the analysis of empirical choices, that is to say which data are selected and how they are treated in order to understand how the researcher is framing public opinion. This is precisely our purpose in the next subsection.

A Classification of Public Opinion

Our research calls for the identification of theoretical views on political opinion in the literature based on Twitter data. Yet, this is not an easy task, especially because scholars focus on empirical investigation and rarely explicitly define how they proceeded when framing the concept. For such a reason, as a preliminary step, it is useful to summarise the classification proposed by Robert Entman and Susan Herbst (2001) that identify four forms of framing public opinion based on methods used by scholars in the analysis of public opinion.

The first form is "mass opinion". According to this form, undoubtedly the most popular, public opinion can be defined as "the aggregation or summation of individual preferences as tabulated through opinion polls, referenda or elections". Within this form, opinions are not "reflective of thoughtful, informed citizens". They are rather artefacts of the tool used to collect them. The second form of public opinion is the "latent public opinion", which "underlies more fleeting and superficial opinions we find when conducting polls of the mass public". This deeper preference depends on individual considerations and political predispositions, that is to say "stable, individual-level traits that regulate the acceptance or non-acceptance of the political communications that people receive" (John R. Zaller, 1992, p. 22). The third form, called the "activated public opinion", refers to opinion "of engaged, informed, and organized citizensthose who are mobilizable during campaign periods and between elections as well". Within this form, we can clearly include all studies that insist on the role of opinion leaders and "influentials" [START_REF] Katz | Personal influence: The part played by people in the flow of mass communication[END_REF][START_REF] Lazarsfeld | The peoples choice: how the voter makes up his mind in a presidential campaign[END_REF][START_REF] Merton | Patterns of Influence: Local and Cosmopolitan Influentials[END_REF], but also of the media [START_REF] Watts | Influentials, networks, and public opinion formation[END_REF] in the formation of political opinions. The fourth form of public opinion, called "perceived majorities"8 , refers to the situations where the term opinion indicates "the perceptions held by most observers, including journalists, politicians, and members of the public themselves, of where the majority of the public stands on an issue". As opposed to previous forms, opinions here do not correspond to the preferences of people whether considered aggregately or individually, but rather to the representations of opinion produced by the media. They are not the actual sentiment but what the media reports. Consequently, in this case, studies do not try to evaluate people's opinion through polls or other techniques, but focus on the analysis of mediated opinion. This form of public opinion mainly includes studies focusing on agenda-setting.

Mining Political Opinion on Twitter

In hundreds of papers 9 that try to analyse political opinion on Twitter, most of them focus on the use of Twitter for predicting voting result and that consider tweets as an alternative to traditional polls. It may be worthwhile to establish whether studies with similar research questions also share a similar theoretical view on political opinion.

As a first observation, we note that papers can be divided into two groups. The first group is constituted by scholars who offer a positive vision by validating the use of Twitter as a vote predictor. This is the case in the famous paper by [START_REF] Tumasjan | Predicting elections with Twitter: What 140 characters reveal about political sentiment[END_REF]Tumasjan et al. ( , cited 1487 times according to Google Scholar, but absent in Scopus), which demonstrates that with the help of a sentiment analysis 10 of tweets, it would have been possible to predict the result of German federal elections in 2009 (based on ca. 100,000 tweets). The authors state that "the mere number of tweets mentioning a political party can be considered a plausible reflection of the vote share and its predictive power even comes close to traditional election polls". It has to be noted that the authors define political opinions as political sentiments, yet, even if they use sentiment analysis, sentiment is reduced to a very basic computation of mentions and conclusions are based on the numerical equivalence between votes and tweets. Similarly, [START_REF] Livne | The Party is Over Here: Structure and Content in the 2010 Election[END_REF] elaborate a proof of concept for predicting election results with an accuracy of 88% (based on 460,000 tweets). Their prediction method is based on the evaluation of several indicators derived not only from text mining but foremost from structural data based on network analysis. The position defended by O'Connor et al. ( 2010) seems more cautious, since they argue that Twitter can be used for pulsing real-time opinion but that such a tool cannot have a prediction power comparable to that of traditional polls. In their paper, we find -for the first time in this field -the use of sentiment analysis techniques, even if they remain basic at that point since they simply relay on lexicons to determine the polarity of tweets (based on 1 billion of tweets).

The second group is constituted by scholars that reject or relativise the use of Twitter as a vote predictor. Some of them concentrate their efforts on rejecting previous studies. The authors' criticism generally focuses on the demographic difference between Twitter users and likely voters, and therefore on the consequent non-representativeness of samples induced by Twitter data. [START_REF] Metaxas | How (not) to predict elections[END_REF] propose the formula "predicting the present" by underlying that researchers who predict election results are doing so after the elections, when they already know the result (based on ca. 235,000 tweets). Daniel Gayo-Avello (2013) draws a state of the art of the question by highlighting weaknesses in previous studies (especially those related to the reproducibility of results). [START_REF] Jungherr | Why the Pirate Party Won the German Election of 2009 or the Trouble With Predictions: A Response to Tumasjan[END_REF] invalidate the study by [START_REF] Tumasjan | Predicting elections with Twitter: What 140 characters reveal about political sentiment[END_REF] by showing that the selection of parties and the chosen particular timeframe have a strong influence on such empirical 9 The state of the art is based on the analysis of the 70 most cited papers according to Scopus and Google Scholar corresponding to the query "political opinion AND twitter" (Annexe 2). 10 The term « sentiment analysis » is used to identify a group of varied techniques aiming at extracting and analysing affective states in texts. results. [START_REF] Skoric | Tweets and Votes: A Study of the 2011 Singapore General Election[END_REF] show that there is certain correlation between Twitter chatter and votes, but not enough to make accurate predictions. A slightly different critique can be found in [START_REF] Boyadjian | Analyser les opinions politiques sur Internet: Enjeux théoriques et défis méthodologiques[END_REF] who does not focus on the limit of empirical analysis but rather investigates the more general question of the representativeness of Twitter compared to traditional polls. Some other scholars focus on the limits of the chosen methods by offering more advanced solutions. Some papers suggest the use of machine learning for performing sentiment analysis. Investigating the 2011 Irish General Election (32,578 tweets), [START_REF] Bermingham | On Using Twitter to Monitor Political Sentiment and Predict Election Results[END_REF] demonstrate the validity of using Twitter as a predictor through an approach combining sentiment analysis based on supervised learning and volume-based measures. Regarding supervised learning, the authors declare: « We instructed annotators not to consider reporting of positive or negative fact as sentiment but that sentiment be one of emotion, opinion, evaluation or speculation towards the target topic » (p. 5).

When considering this whole range of papers, we observe that no one investigates the equivalence between tweets and opinions. The fact that these short messages allow us to know people's opinions is somehow legitimate. Even scholars in political science, who are very critical about the predictive power of the platform, focus on choices made for empirical analysis without questioning the relation between the data and the studied object. Yet, by focusing on the selected data and methods, it is possible to distinguish four conceptual models of political opinion, which are not exclusive and can also be combined in the same study (Table 1).

Opinion as a Preference

In the first group of studies (preference), political opinion is considered as an aggregate preference in relation to a determined object selected by the researcher. Researchers adopting this model are building corpora of tweets containing specific keywords or hashtags, such as the name of a candidate or a political party. They are interested in the tweet as a unit, as a whole (without considering co-occurrences inside it or the context of usage) and they are observing mainly the variation of volume of tweets according to different parameters (time, space, user, topic, etc.). Some of them use very basic sentiment analysis techniques (manually built lexicons) that produce a simple word count. In this group, we mainly find studies trying to predict election results [START_REF] Tumasjan | Predicting elections with Twitter: What 140 characters reveal about political sentiment[END_REF][START_REF] Livne | The Party is Over Here: Structure and Content in the 2010 Election[END_REF][START_REF] Skoric | Tweets and Votes: A Study of the 2011 Singapore General Election[END_REF]. Using different kinds of quantitative techniques, their aim is to verify whether there is a correlation between the number of tweets mentioning a candidate and the number of votes he or she receives. In this type of study, political opinion is clearly framed as mass opinion. Opinion is treated as quantifiable, measurable and countable. Tweets are used to study it as an aggregate phenomenon. Similarities to traditional polls can be easily identified. The researcher is forcing a question onto a pre-existing sample of data, assuming that this sample contains the answer.

Opinion as a Sentiment

Taking into account the limits of an approach simply based on the count of preferences, more recent studies have focused on individual attitudes. Researchers who adopted this definition may be also building corpora of tweets containing specific words or hashtags, yet they are interested in the tweet as content rather than as a mere countable unit. They may study co-occurrences of words or more advanced textual structures while trying to interpret the sentiment expressed in the text. The final goal is to obtain a complex view that takes into account the individual positions related to the object of study in accordance with the "latent opinion" form.

A tricky issue is how to define sentiment. In the last few years, the so-called sentiment analysis has become very popular. According to the definition of [START_REF] Wilson | Recognizing Contextual Polarity in Phrase-Level Sentiment Analysis[END_REF], sentiment is a question of contextual polarity: "Sentiment analysis is the task of identifying positive and negative opinions, emotions, and evaluations". The authors offer a sentiment lexicon enriched through supervised learning. Within our corpus, O'Connor et al. ( 2010), cited 635 times according to Scopus and 1487 times according to Google Scholar, base their analysis of sentiments on the lexicon in OpinionFinder. Their approach has been reproduced dozen of times in the following years. For example, Conover et al. (2011, the third more cited paper in Scopus) develop a content-based method on manual annotation (labelled data) for analysis of 355 millions tweets. More recently, scholars [START_REF] Bermingham | On Using Twitter to Monitor Political Sentiment and Predict Election Results[END_REF] have proposed supervised approaches for building sentiment classifiers. This particular approach also includes studies that qualify sentiments in a more qualitative way based on small corpora of data.

Opinion as an Interaction

Some researchers have broaden the scope of their study, shifting their attention from the tweet to its context in order to identify the network of interactions related to the formation and circulation of opinions. According to this conceptual model, opinions are individual sentiments generated not only by the predispositions of a person, but also and foremost influenced by his or her role in the society. Most of the studies in this field focus on the role of influentials coherently with the form of the "activated opinion". Here we can mention quantitative studies trying to identify opinion leaders based on network metrics. Thanks to the analysis of a corpus related to the political hashtags #FreeIran, #FreeVenezuela and #Jan25, [START_REF] Bastos | Gatekeeping Twitter: message diffusion in political hashtags[END_REF] studied the structure of gatekeeping in Twitter by analysing retweet, mention and followers-following networks for each hashtag. They rejected the idea of the existence of hubs acting as gatekeepers by underlining the importance of committed minorities. Slightly different is the view developed by [START_REF] Park | Does Twitter motivate involvement in politics? Tweeting, opinion leadership, and political engagement[END_REF] in his paper, in which he carried out a survey highlighting the difference between traditional opinion leadership based on the two-step flow theory [START_REF] Katz | Personal influence: The part played by people in the flow of mass communication[END_REF] and opinion leadership on Twitter.

Some researchers combine content analysis with network analysis. Xu et al. (2012), focusing on activism networks, explored both opinion leadership through network statistics measures and political involvement through the analysis of the information profile and the content of tweets.

Their results were the opposite of those obtained by [START_REF] Bastos | Gatekeeping Twitter: message diffusion in political hashtags[END_REF], showing the connection between centrality and leadership. In order to predict political affiliation of Twitter users, [START_REF] Conover | Predicting the Political Alignment of Twitter Users[END_REF] combined content-based methods with structure analysis of political information in diffusion networks (retweet and mention networks), and actually validated network analysis as a more efficient solution for identifying political alignments of users. Similarly, Stieglitz and Dang-Xuan (2012) combined sentiment analysis (using Linguistic Inquiry and Word Count LIWC software 11 ) with network analysis on a corpus of 64,000 tweets. Their purpose is to study whether articulated sentiment in political tweets has an effect on their retweetability. More qualitative studies analysed tweets of specific classes of users considered as influential, such as journalists [START_REF] Molyneux | What journalists retweet: Opinion, humor, and brand development on Twitter[END_REF].

Opinion as an Agenda

Other studies focus on the role of Twitter as a medium responsible for setting the opinion's agenda. In this case, the relation between the tweet and its author becomes irrelevant. Tweets are not equivalent to aggregate or individual opinions of people, yet they convey, to the people, social representations directly generated by the platform.

As an example, the study by Papacharissi and de Fatima Oliveira (2012, the second more cited in Scopus) traced the rhythm of news storytelling on Twitter via the #Egypt hashtag. The authors 11 With built-in dictionaries.

intended to identify the evolution of news values that determine the selection of news on Twitter. Methods here are content computer-mediated text analysis combined with discourse analysis. The attention is not really focused on opinion-making but on Twitter as a medium for sharing news.

This last approach is profoundly different from the others because research in this field rarely uses tweets as data but rather investigate Twitter as a social actor. Moreover, it raises the subjacent but essential issue of the validity of tweets as bottom-up data representative of people's opinions. Indeed, according to this model, tweets are the product of the platform rather than the product of the people [START_REF] Marres | Digital Sociology. The Reinvention of Social Research[END_REF].

The Methodological Challenges of Political Opinion

With categories now defined, it is interesting to match up conceptual views of political opinion with the question of methods. In particular, this paper intends to observe cases where studies have been able to scale up from small to big data or, even better, to combine different scales of analysis in order to fill the gap between qualitative and quantitative research.

In order to embrace this question, it is however important to dedicate a few lines to the scientific context. If they sometimes disagree on the best position to adopt, many researchers do agree on the fact that digital data, and in particular the advent of big data, is currently disrupting many fields in social sciences and should hence be cautiously considered as a genuine paradigmatic shift. Regarding the development of digital platforms such as Twitter, T. Venturini and B. Latour (2010) claimed that "[they] offer much more than just another field to apply existing methods: they offer the possibility of restructuring the study of social existence". The impact of such scientific revolution is likely to not only affect social sciences from within by invalidating traditional methods and promulgating new ones, but also from the outside by modifying institutions, practices, and even some of the epistemic objectives of the field. Among the external effects of big data on the practice of social sciences, the most frequent are: ethical challenges regarding access and privacy, political challenges regarding the dependence of scientific research on the production and the access conditions of this data [START_REF] Driscoll | Working Within a Black Box: Transparency in the Collection and Production of Big Twitter Data[END_REF], and even institutional challenges that require a complete reworking of research and education communities in this particular area [START_REF] Lazer | Computational Social Science[END_REF].

However, besides raising the numerous issues about the practices of social sciences, we would rather focus on the impact that such paradigmatic shift has on methods, that is on the actual change from within. In order to do this, our analysis will be articulated around three main methodological oppositions related to the use of computational research in social sciences: onlymicro and only-macro vs. multiscale approaches; exploratory vs. predictive approaches; supervised vs. unsupervised approaches.

About Multiscale vs. Macro or Micro Approaches

According to [START_REF] Venturini | The social fabric: Digital traces and qualiquantitative methods[END_REF], one of the major epistemological challenges that social sciences must face because of big data concerns the reconsideration of a deeply-grounded dualistic vision of data. The classical use of statistical tools -such as aggregative methods -to unravel macroscopic social structures introduces "a fictive distinction between micro-interactions and macro-structures". As a loose analogy, statistical physics early developed inter-level models to distinguish classical macro-measurements from micro-measurements and thereby filled the causal gap between individuals and aggregates. Social sciences are currently working on analogous bottom-up models of social phenomena. Even though we can ascribe it to the tremendous complexity of social objects, this dualistic stance nevertheless leads traditional approaches to the mere "juxtaposition of statistical analysis with ethnographic observation". Following this disturbing statement, Venturini and Latour hence advocate in favour of a genuine "quali-quantitative" approach, building on digital traces to combine the precision of ethnographic surveys and the large-scale scope of statistical analysis in an integrative and unified framework. This epistemological position was already advocated by complexity sciences in the 1970s, as in The Macroscope imagined by J. de Rosnay (1975), to observe societies in all their complexity through computer simulation, thus anticipating the growing field of Computational Social Sciences through some tentative essays of using agent models in order to grasp the causal structure of emergent phenomena [START_REF] Lazer | Computational Social Science[END_REF][START_REF] Cioffi-Revilla C | Bigger Computational Social Science: Data, Theories, Models, and Simulations-Not Just Big Data[END_REF][START_REF] Casini | Agent-based models and causality: a methodological appraisal[END_REF].

In our corpus, many studies are only interested in the question of aggregates. This is the case in most of the articles dealing with the prediction of election results as their research objective is per se driven by a collective framing of political opinion. This objective is enough justification for using methods that generate erroneous measurements when it comes to the analysis of individual opinions. For example, O'Connor et al. ( 2010) first stated that they were "only interested in aggregate sentiment". Hence, "a high error rate [at the individual level] merely implies [that] the sentiment detector is a noisy measurement instrument. With a fairly large number of measurements, these errors will cancel out relative to the quantity we are interested in estimating, aggregate public opinion." With this line of thinking, the only criterion for method validation is the ability to predict aggregate values, without any guarantee for their potential coupling with individual-oriented researches.

Yet, according to other scholars, the impact of some highly influential individuals is crucial to the explanation of global dynamics. Stieglitz and Dang-Xuan (2012) stressed that "political discussion on Twitter is led by a few highly active users only representing about one percent of all users". They hence performed a detailed analysis of this "one percent" and proposed consistent measurements to simultaneously deal with individuals and aggregates. Similarly, [START_REF] Bermingham | On Using Twitter to Monitor Political Sentiment and Predict Election Results[END_REF], after having performed a large-scale sentiment analysis of 32,578 tweets, tried to "identify terms that provide a path to qualitatively exploring the dataset". They went from a macroscopic observation of opinion to a microscopic explanation by investigating the individual factors that most significantly impact the aggregate results. The work of J. [START_REF] Boyadjian | Analyser les opinions politiques sur Internet: Enjeux théoriques et défis méthodologiques[END_REF] can also be considered as a multiscale approach -as regards the building of a corpus -mixing precise data collection through traditional survey with large-scale aggregative collection through computational methods.

About Explanatory vs. Predictive Approaches

The fast development of big data and its combination with classical algorithmic tools from machine learning have led to another epistemological crisis. As expressed by "neo-positivist" researchers, the paradigmatic shift could equally lead to a practice of social research where social scientists are no longer required. This is the provocative yet sincere claim made ten years ago by [START_REF] Anderson | The End of Theory: The Data Deluge Makes the Scientific Method Obsolete[END_REF] when he wrote that "correlation [now] supersedes causation, and [that] science can advance even without coherent models, unified theories, or really any mechanistic explanation at all." While the epistemological opposition between correlation and causation is neither new nor solved, the tremendous amount of information made available by digital data on the Web seems to have strongly favoured the application of purely-statistical methods during the last decade. As can be observed in many papers from our corpus, one major objective of today's research is rather the prediction of social phenomena than their explanation. Yet, [START_REF] Metaxas | How (not) to predict elections[END_REF] state that "in the past, some research efforts have treated social media as a black box: it may give you the right answer, though you may not know why. We believe that there is an opportunity for intellectual contribution if research methods are accompanied with at least a basic reasonable model on why they would predict correctly."

Against the idea that sufficiently big data, along with machine learning techniques, can lead to the automatic discovery of significant correlations, some researchers argue, using informationtheoretical arguments, that approaches exclusively based on decontextualised statistical analysis are doomed to fail [START_REF] Calude | The Deluge of Spurious Correlations in Big Data[END_REF], while others point out that, even if computerdiscovered correlation is achievable, it does not fulfil the basic objectives of social sciences. As stated by [START_REF] Pigliucci | The end of theory in science?[END_REF], science "is not about finding patterns-although that is certainly part of the process-it is about finding explanations for those patterns." The difference between a statistical law, which can be efficient for prediction, and a model, which is able to provide an additional mechanistic explanation, is nicely illustrated by [START_REF] Masad | Computational social science, data, and complexity[END_REF] in a rather simple experiment on Schelling's model of spatial segregation.

This lively distinction between black-boxed learning algorithms and explanatory approaches is another crucial issue for the field we are considering. As a first example, Stieglitz and Dang-Xuan (2012) tried to correlate sentiment expressions in political tweets with their retweetability. They built to do so a "predictive retweet model" using sentiment categories as informative features.

While mentioning theoretical background in communication science about "the role of sentiment in the communication in newsgroups, discussion forums or in other contexts", the authors never make explicit the possibility of psychological behaviours underlying the correlation revealed by their findings. So, it is possible that sentiment expressions are in fact not the cause of retweetability, but only correlated to it through some hidden variable (such as the presence of a URL in the tweet). Similarly, Ceron et al. (2014) made "quite speculative" (sic) interpretations about the correlations they find between surveys and Twitter data regarding political leaders' popularity, by discussing the dynamics of the elections in the study. However, a deeper qualitative analysis of these elections would be necessary to go beyond mere statistical correlations, to better understand the causal relations that might exist between online and offline popularity, that is to say how one could explain the other.

Conversely, according to [START_REF] Bermingham | On Using Twitter to Monitor Political Sentiment and Predict Election Results[END_REF], "in opinion measurement and social media analytics it is limiting to simply measure without providing means to explain measurements". In this sense, in order to transfer statistically-discovered correlations into mechanistic models that genuinely integrate a qualitative sociological understanding, [START_REF] Colleoni | Echo Chamber or Public Sphere? Predicting Political Orientation and Measuring Political Homophily in Twitter using Big Data[END_REF] proposed an informed interpretation of the discovered correlations between structural features of the retweet network and political leaning found in the Twitter accounts. Exploiting the classical model of political homophily in online and offline discussion, they built their argumentation on typologies developed by political sociology (e.g., "political thinkers", "political activists", "general public") and by communication science (e.g., the distinct modalities of political communication in digital networks, seeing Twitter as a "social medium" or as a "news medium"). This pairing allows qualitative models to provide existent correlations with an adequate sociological explanation. In [START_REF] Jürgens | Small Worlds with a Difference: New Gatekeepers and the Filtering of Political Information on Twitter[END_REF], such pairing is even performed at the formal level. Key concepts inherited from mass communication research (such as "news gatekeepers") are expressed in the framework of graph theory, building on the "Key Player Problem" of [START_REF] Borgatti | Identifying sets of key players in a network[END_REF]. Here, the mathematical formalisation of qualitative sociological models are then used for hypothesis testing in order to detect "users who had the strongest possibility to block or disrupt the flow of information".

About Supervised vs. Unsupervised Approaches

The opposition between predictive and explanatory approaches lies, as we claimed, in the way sociological knowledge is integrated into the quantitative analysis process: either as a way to a posteriori interpret correlation results based on qualitative typologies, or as an a priori model that needs to be first formalised for hypothesis testing. This distinction hence appears to be a practical instance of the classical epistemological opposition between inductive approaches, where qualitative interpretation comes after statistical analysis, and hypothetico-deductive approaches.

In particular, in machine learning methods, the distinction between supervised and unsupervised learning constitutes such a practical case of the opposition. Supervised learning indeed consists in the deduction of categories from a priori annotated data, while unsupervised learning proceeds from unlabelled data to infer a classification which receives an a posteriori interpretation. In the literature about the use of sentiment analysis in Twitter data for predicting the political orientation of individuals, three coarse categories of approaches can be distinguished: opinion lexicons, unsupervised learning, and supervised learning.

First, traditional methods for sentiment analysis are based on opinion lexicons such as those provided by OpinionFinder [START_REF] Balasubramanyan R | From Tweets to Polls: Linking Text Sentiment to Public Opinion Time Series[END_REF], by an opinion corpus [START_REF] He | Quantising Opinions for Political Tweets Analysis[END_REF], or by a linguistic software using a "psychometrically validated internal dictionary" [START_REF] Stieglitz | Political Communication and Influence through Microblogging -An Empirical Analysis of Sentiment in Twitter Messages and Retweet Behavior[END_REF]. Such methods are often called "unsupervised methods" [START_REF] Bermingham | On Using Twitter to Monitor Political Sentiment and Predict Election Results[END_REF] in the sense that, once the lexicon is set, the classification of tweets is automatic: no further human interaction is required. We however find this name misleading since, on the contrary, much supervision is actually required beforehand: expert knowledge is requested at the very beginning of the classification task. For this reason, O'Connor et al. ( 2010) claim that opinion lexicons are more "transparent" than other approaches in the sense that the result of classification can easily be explained by the linguistic models that were used to build the lexicon. However, we also note that these so-called "unsupervised methods" are not "learning methods" since the sentiment categories are not learned from the data, but provided a priori. As a result, the process is quite rigid, not adaptive to a particular context or to a particular corpus.

To the extreme opposite, unsupervised learning aims at organising the tweets according to their content without requesting any linguistic knowledge. Such approaches therefore build consistent groups of tweets by finding statistically-significant similarities between them, using very generic features such as the words they contain. The resulting categories can then be a posteriori labelled by looking at the tweets within, and then used to classify new tweets. Since no prior knowledge is required, such approaches are very cheap in terms of implementation and might result in quite efficient predictions within the discovered categories. However, it might be very difficult to actually make sense of these categories with respect to a particular psychological or sociological framework since they have been built in a purely inductive fashion. Few studies in our corpus rely on this second kind of approach, but we can at least cite the use of topic models [START_REF] Ling | Topic Sentiment Mixture: Modeling Facets and Opinions in Weblogs[END_REF][START_REF] He | Quantising Opinions for Political Tweets Analysis[END_REF] and more generally of latent space models [START_REF] Barberá | Tweeting From Left to Right: Is Online Political Communication More Than an Echo Chamber?[END_REF].

A third category of highly used approaches lies in between the two categories mentioned above, and that is supervised learning. In this case, a set of sentiment categories is first defined, either a quite simple unidimensional typology ("positive", "negative", "neutral") or a more complex one related to classical human emotions (e.g., "happiness", "excitation", "sadness", "fear"). Then, a set of features extracted from the tweets' content is defined as potentially informative. It can simply consist in counting sequences of words [START_REF] Bermingham | On Using Twitter to Monitor Political Sentiment and Predict Election Results[END_REF], in term frequencies [START_REF] Colleoni | Echo Chamber or Public Sphere? Predicting Political Orientation and Measuring Political Homophily in Twitter using Big Data[END_REF], or in more complex grammatical decompositions into part-ofspeech elements [START_REF] Pak | Twitter as a Corpus for Sentiment Analysis and Opinion Mining[END_REF]. The objective of machine learning is then to build a "classifier", that is a function using the content-based features of tweets to identify the sentiment category they belong to. To do so, a list of examples obtained by hand annotating a significant corpus of tweets (the training set) is used to initialise the classifier. This is where, for the most part, human knowledge is convoked. Then, a statistical technique is applied to find correlations between the features and the provided annotations. Many such techniques are exploited in the literature, such as Support Vector Machines (SVM) as in [START_REF] Conover | Predicting the Political Alignment of Twitter Users[END_REF], iterative learning [START_REF] Bermingham | On Using Twitter to Monitor Political Sentiment and Predict Election Results[END_REF], passive-aggressive classification [START_REF] Colleoni | Echo Chamber or Public Sphere? Predicting Political Orientation and Measuring Political Homophily in Twitter using Big Data[END_REF], or naïve Bayes classifier [START_REF] Pak | Twitter as a Corpus for Sentiment Analysis and Opinion Mining[END_REF]. Lastly, correlations that have been found are tested and validated by comparing them to another corpus in order to measure its sensitivity (number of true positives) and its precision (number of false positives).

The value of opinion lexicons and supervised learning, compared to unsupervised learning, is that sentiment categories are defined beforehand by the experts, building for example on successful psychological models of human communication. However, in the case of opinion lexicons, the links between features and categories are expressed a priori by linguistic expertise whereas, in the case of supervised learning, these links are inductively discovered by learned correlations.

According to Ceron et al. (2014), "human coders are, of course, more effective and careful than ontological dictionaries," suggesting the best solution is a more flexible supervised classifier built on real practical examples. Yet, it is important to note that when the selected features are very generic (e.g., any word can be a feature), it might be difficult to disentangle indirect correlations (a word is correlated with a sentiment through a third hidden variable that explains both) from causal relations (a word is actually a direct expression of the sentiment). The resulting classifier, though quite predictive, does not allow an explanation for the prediction result in a clear linguistic manner. Thus, researchers have to choose between explanatory-but-rigid approaches, hence not suitable for the diverse and highly ambiguous use of language in Twitter, and flexible-but-onlypredictive approaches that might not fit in with a causal explicative model.

Future Trends with the Advent of Big Data

After examining the current state of the art and identifying the main theoretical and methodological approaches developed by digital research about political opinion, it is time to move forward and reach our second objective, that is to propose some guidelines for future trends in the field. In practice, we are interested in computational methods that would allow for a multiscale description of the data, that is methods able to simultaneously describe long-terms dynamics, macroscopic community structures as well as crucial details and micro-events that slip through the control of aggregative methods. If we try to cross conceptual approaches of political opinion with the above mentioned methodological oppositions, a number of interesting insights emerge. In each cell of Concerning the first conceptual model, where opinion is considered as a collective preference, macro-structures are alone sufficient for the analysis. Studies in this field propose statistical techniques suitable for aggregates and almost exclusively result in predictive analyses. However, the merit of such research group is to raise the question of the representativeness of activity traces obtained through digital media, and notably that of the comparability between Twitter data and traditional opinion polls. Although it has been shown that there is no bijection between Twitter accounts and individuals [START_REF] Boyd | Critical questions for big data: Provocations for a cultural, technological, and scholarly phenomenon[END_REF] and that strong socio-economical biases in the current use of digital media might invalidate their representativeness, many scholars still have "some doubts about whether such bias could affect the predictive skills of social media analysis compared to traditional offline surveys" (Ceron et al., 2014).

Papers exclusively based on the preference conceptual model are however very rare. This model is often mixed with the sentiment model. Yet, in both cases, when opinion is considered either as a sentiment or as a preference, methods for the prediction of election results or political polls could improve their efficiency by also focusing on crucial users with the strongest activity (or the strongest influence) on the platform, as suggested by [START_REF] Stieglitz | Political Communication and Influence through Microblogging -An Empirical Analysis of Sentiment in Twitter Messages and Retweet Behavior[END_REF]. Such individuals could indeed constitute quite powerful predictors of global trends at a micro-level. The combination of such qualitative analysis with quantitative prediction would however require the use of network-based approaches in order to automatically identify such crucial individuals. Accordingly, going from the mere prediction of election results to their explanation requires a better understanding of causal interactions between online and offline opinion making (and not only of their statistical correlations). As expressed in Ceron et al. (2014), one has to address "the question of the direction of causality", that is: "is the social media opinion becoming more similar to the general public opinion, or, on the contrary, are social media driving (or anticipating) the general public opinion?" In order to do so, the development of relevant sentiment categories is crucial, yet difficult in the context of ambiguous communication on Twitter. Developing more flexible sentiment categories that can be partially induced by data, yet supported by linguistic and psychological models, might help bridge the gap between the too-rigid opinion lexicons and the weakly-supervised approaches of machine learning.

Mixing analysis scales is especially relevant for scholars that investigate the network structure of political opinion. Indeed, interaction-based approaches often imply the combination of microand macro-measurements. In general, these approaches propose many formal tools to help measure structural properties of interactions on Twitter at different levels, from micro-structure, such as hubs and bridges, to macro-structures such as communities and other connectivity patterns. What is currently missing is a clear theoretical and empirical understanding of interconnections between such micro-and macro-measurements. For example, how is the presence of bridges and hubs in the network, corresponding to potential influencers from the perspective of communication sciences, correlated with the global connectivity or polarisation of opinions in the network? Consequently, mechanistic agent-based models of opinion diffusion, in particular the ones developed by Computational Social Sciences (see Section 4.1), constitute a promising line of research to explain how such network structures (both micro and macro) are responsible for the observed opinions (both individual and collective). To do so, the chosen structural measures need to be genuinely motivated by communication models, as described in [START_REF] Jürgens | Small Worlds with a Difference: New Gatekeepers and the Filtering of Political Information on Twitter[END_REF]. They also need to remain sufficiently generic to discover new modes of interaction, thus achieving a trade-off between purely hypothetico-deductive approaches, formalising and testing communication models with graph-theoretic tools, and inductive approaches, able to adapt such structural analysis to the very diverse uses of digital media.

Studies that focus on tweet-generated agenda are rarely interested in mixing analysis scales. They either focus on the macro-level scale by identifying general factors capable to influence an agenda (such as studies on news value) or, conversely, on specific individuals, such as journalists or politicians, in order to study how the representations they produce can influence citizen or media agendas. These approaches do not currently study the two levels simultaneously, for example by providing a clear model of how the micro-agendas followed by journalists and politicians impact the collective macro-agendas and, conversely, how the macro-agendas might also produce topdown feedback on these micro-agendas. Yet, it is worthwhile to note that multiscaling is technically possible. Indeed, studies in this field might benefit from a better understanding of informational interactions between mass media (expressing a top-down political agenda) and digital media (building a bottom-up political agenda), thus showing how individual and collective agendas are tangled through the interaction of structurally-different areas of discussion. In order to do so, it is necessary to develop methods able to consistently address political opinion in their different production and consumption contexts, and to interpret them as different levels of opinion making.

Conclusion

This paper took up the considerably hard task of verifying the possibility of performing multiscale analysis of political opinions based on digital data, more precisely on Twitter data. As a first step, we adopted a conceptual viewpoint that allowed us to identify four major approaches in considering political opinions, that is as a preference, a sentiment, an interaction and as an agenda. We then explored methods that have been proposed in the past to fill the gap between the qualitative and quantitative approaches.

First, whether relative to data collection (from individual self-reported surveys to large-scale collection of digital traces) or to data treatment (from the contextualised analysis of particular individuals or events, to the interpretation of macroscopic trends or long-term dynamics), we argued that the concept of "multiscale analysis" can be of great benefit in thinking this methodological challenge by encouraging the simultaneous consideration of crucial details and significant aggregates. We saw that adopting the "sentiment" or the "interaction" conceptual approaches calls for multiscale techniques.

Second, we tried to alleviate one of the main criticisms of the current computational methods when it comes to big data, that is the lack of explanatory power of unsupervised machine learning and other purely-statistical methods. It is indeed essential that the result of data treatment is not limited to the automatic discovery of correlations between explored variables, but that it also provides a causal model allowing to accurately interpret such correlations within the realms of social sciences. We saw that this was all the more made possible when interdisciplinary teams, constituted by social scientists and computer scientists12 , were able to relate their empirical results with pre-existing models in communication studies and/or political sciences.

Third, these methodological issues are related to the role given to expert knowledge within computational approaches. In this regard, we focused our analysis on the specialised field of sentiment analysis where several proposals have been made to integrate (or to discount) linguistic knowledge within the algorithmic analysis of tweets, leading to different advantages and drawbacks when it comes to the qualitative interpretation of the results.

Needless to say, the good practices here identified are time-and resource-consuming. This implies a long-term project and long delays in the production of scientific publications. Moreover, as previously mentioned, these studies are bound to face important ethical issues. All this explains why, even when hundreds of papers investigate political opinions through tweets, very few offer multiscale methods that can be valid both for computer science and social science standards. Yet, our hope is that this study will help to make progress in this particular field by highlighting the importance of the connection between conceptual and methodological choices, and its consequences.

Table 1 .

 1 The four conceptual models of political opinion.

	Conceptual model	Eldam and Herbst's form	Data	Methods
				-Statistics
	Preference	Mass opinion	Tweet as a unit	-Basic sentiment
				analysis (lexicon)
				-Advanced sentiment
	Sentiment	Latent opinion	Tweet as a content	analysis (unsupervised and supervised
				learning)
	Interaction	Activated opinion	Tweet as an interaction	-Network analysis
	Agenda	Perceived majorities	Tweet as a medium (agenda setter)	-Discourse analysis -Text-mining

Opinion as an agenda

  Table2, we describe the present situation and future perspectives in research that embraces the different opinion definitions in relation to the three methodological challenges. This table may be a simple abstract representation, since most papers mix more than one conceptual model, yet this abstraction aims at showing the connection between conceptual choices and methodological solutions.

		Multiscale	Explanatory	Supervised
	Opinion as a preference	No multiscale: interest Research for focuses only on aggregate analysis	No explanatory interest methods: for Research focuses only on prediction (no need for a model)	No supervised interest learning: for Basic lexicons are satisfying
	Opinion as a sentiment	Toward Looking at aggregates, multiscale: but also at crucial users that have the strongest activity (or the strongest influence) on the platform	Toward Studying the causal explanatory: interactions between online and offline opinions (and not only their correlations)	Toward Developing flexible categories that can be supervised: more sentiment partially induced by data, yet supported by psychological models
	Opinion as an interaction	Toward Using network as a multiscale: formal tool to measure multiscale structural properties of interactions and their formal inter-level relations (how micro influences macro, and vice-versa)	Toward Developing mechanistic explanatory: models of opinion diffusion to explain how the network structure is responsible for the observed (individual and collective) opinions	Toward Using measures of networks supervised: structural motivated by communication models, yet sufficiently general to discover new patterns of interaction
		Toward multiscale: Studying contribution of social the media's specific users in setting mass media agenda	Limited agendas explanatory Research focuses mainly interest in methods: on the analysis of the existent agenda and on the prediction of future	No supervised interest learning: for Traditional techniques of text mining suffice

Table 2 .

 2 Intersection between conceptual approaches of political opinion and methodological oppositions related to big data challenges.

If we apply the distinction between 'opinion' and 'opinions' to the four forms, we can easily see that the "mass opinion" and "predictive majorities" correspond to a collective view of the opinion, while the "latent opinion" and the "activated opinion" are based on the idea of multiple individual opinions.

Indeed, big data and data science do not change methods of social science, statistics and computer science. The main change concerns the awareness of the necessity and interest of working in interdisciplinary frameworks without neglecting one of these disciplines.

This work has been partially funded by the European Commission H2020 FETPROACT 2016-2017 program under grant 732942 (ODYCCEUS).


Jarno N Alanko
email: jarno.alanko@helsinki.fi

Hideo Bannai
email: bannai@inf.kyushu-u.ac.jp

Bastien Cazaux
email: bastien.cazaux@helsinki.fi

Pierre Peterlongo
email: pierre.peterlongo@inria.fr

Jens Stoye
email: jens.stoye@uni-bielefeld.de

Adam Auton

Lisa D Brooks

Richard M Durbin

Erik P Garrison

Hyun Min Kang

Jan O Korbel

Jonathan L Marchini

Shane Mccarthy

Gil A Wa

Annalisa Buniello

Jacqueline A L Macarthur

Maria Cerezo

Laura W Harris

James Hayhurst

Cinzia Malangone

Aoife Mcmahon

Joannella Morales

Edward Mountjoy

Elliot Sollis

Daniel Suveges

Olga Vrousgou

Patricia L Whetzel

Ridwan Amode

Jose A Guillen

Harpreet S Riat

Stephen J Trevanion

Peggy Hall

Heather Junkins

John H Gillespie

Daniel F Gudbjartsson

Hannes Helgason

Sigurjon A Gudjonsson

Florian Zink

Asmundur Oddson

Arnaldur Gylfason

Søren Besenbacher

Gisli Magnusson

Bjarni V Halldorsson

Gunnar Eirikur Hjartarson

Th Sigurdsson

Simon N Stacey

Michael L Frigge

Hilma Holm

Jona Saemundsdottir

Th Hafdis

Hrefna Helgadottir

Gunnlaugur Johannsdottir

Gudmundur Sigfusson

Jon Th Thorgeirsson

Solveig Sverrisson

Gretarsdottir

Bragi Walters

Thorunn Rafnar

Bjarni Thjodleifsson

Einar S Bjornsson

Sigurdur Olafsson

Hildur Thorarinsdottir

Thora Steingrimsdottir

Thora S Gudmundsdottir

Asgeir Theodors

Jon G Jonasson

Asgeir Sigurdsson

Gyda Bjornsdottir

Jon J Jonsson

Olafur Thorarensen

Petur Ludvigsson

Hakon Gudbjartsson

Gudmundur I Eyjolfsson

Olof Sigurdardottir

Isleifur Olafsson

Olafur David O Arnar

Jayne Y Hehir-Kwa

Tobias Marschall

Wigard P Kloosterman

Laurent C Francioli

Jasmijn A Baaijens

Louis J Dijkstra

Abdel Abdellaoui

Djie Vyacheslav Koval

Tjwan Thung

René Wardenaar

Ivo Renkens

Bradley P Coe

Patrick Deelen

Joep De Ligt

Eric-Wubbo Lameijer

Freerk Van Dijk

The Genome of the Fereydoun Hormozdiari

Netherlands Consortium

Jasper A Bovenberg

Anton J M De Craen

Marian Beekman

Albert Hofman

Gonneke Willemsen

Bruce Wolffenbuttel

Mathieu Platteel

Yuanping Du

Ruoyan Chen

Hongzhi Cao

Rui Cao

Yushen Sun

Jeremy Sujie Cao

Pieter B T Neerincx

Martijn Dijkstra

George Byelas

Alexandros Kanterakis

Jan Bot

Martijn Vermaat

Jeroen F J Laros

Johan T Den Dunnen

Peter De Knijff

C Lennart

Elisa M Karssen

Najaf Van Leeuwen

Fernando Amin

Karol Rivadeneira

Jouke-Jan Estrada

Hottenga

Mathijs Kattenberg

David Van Enckevort

Hailiang Mei

Mark Santcroos

Barbera D C Van Schaik

Robert E Handsaker

Steven A Mccarroll

Arthur Ko

Peter H Sudmant

Isaac J Nijman

André G Uitterlinden

Cornelia M Van Duijn

Evan E Eichler

Tobias Rausch

Eugene J Gardner

Alexej Abyzov

John Huddleston

Yan Zhang

Kai Ye

Goo Jun

Markus Hsi-Yang Fritz

Miriam K Konkel

Ankit Malhotra

Adrian M Stütz

Xinghua Shi

Francesco Paolo Casale

Jieming Chen

Gargi Dayama

Ken Chen

Maika Malig

Mark J P Chaisson

Klaudia Walter

Sascha Meiers

Seva Kashin

Xinmeng Hugo Y K Lam

Jasmine Mu

Can Alkan

Danny Antaki

Taejeong Bae

Eliza Cerveira

Peter Chines

Zechen Chong

Laura Clarke

Elif Dal

Li Ding

Sarah Emery

Xian Fan

Madhusudan Gujral

Fatma Kahveci

Jeffrey M Kidd

Yu Kong

Paul Flicek

Richard A Gibbs

Gabor Marth

Christopher E Mason

Androniki Menelaou

Donna M Muzny

Bradley J Nelson

Amina Noor

Nicholas F Parrish

Matthew Pendleton

Andrew Quitadamo

Benjamin Raeder

Eric E Schadt

Mallory Romanovitch

Andreas Schlattl

Robert Sebra

Andrey A Shabalin

Andreas Untergasser

Jerilyn A Walker

Min Wang

Fuli Yu

Chengsheng Zhang

Jing Zhang

Xiangqun Zheng-Bradley

Wanding Zhou

Thomas Zichner

Jonathan Sebat

Mark A Batzer

Clare Turnbull

Richard H Scott

Ellen Thomas

Louise Jones

Nirupa Murugaesu

Freya Board- Man Pretty

Dina Halai

Emma Baple

Clare Craig

Angela Hamblin

Shirley Henderson

Christine Patch

Amanda O'neill

Andrew Devereau

Katherine Smith

Antonio Rueda Martin

Alona Sosinsky

Ellen M Mcdonagh

Razvan Sultana

Michael Mueller

Damian Smedley

Adam Toms

Lisa Dinh

Tom Fowler

Finding all maximal perfect haplotype blocks in linear time

Keywords: 2012 ACM Subject Classification Theory of computation → Pattern matching, Applied computing → Bioinformatics, Mathematics of computing → Combinatorial algorithms, Applied computing → Computational genomics Population genomics, selection coefficient, haplotype block, positional Burrows-Wheeler Transform Digital Object Identifier 10.4230/LIPIcs.WABI.2019.8

Recent large-scale community sequencing efforts allow at an unprecedented level of detail the identification of genomic regions that show signatures of natural selection. Traditional methods for identifying such regions from individuals' haplotype data, however, require excessive computing times and therefore are not applicable to current datasets. In 2019, Cunha et al. (Proceedings of BSB 2019) suggested the maximal perfect haplotype block as a very simple combinatorial pattern, forming the basis of a new method to perform rapid genome-wide selection scans. The algorithm they presented for identifying these blocks, however, had a worst-case running time quadratic in the genome length. It was posed as an open problem whether an optimal, linear-time algorithm exists. In this paper we give two algorithms that achieve this time bound, one conceptually very simple one using suffix trees and a second one using the positional Burrows-Wheeler Transform, that is very efficient also in practice.

Introduction and Background

As a result of the technological advances that went hand in hand with the genomics efforts of the last decades, today it is possible to experimentally obtain and study the genomes of large numbers of individuals, or even multiple samples from an individual. For instance, the National Human Genome Research Institute and the European Bioinformatics Institute have collected more than 3500 genome-wide association study publications in their GWAS Catalog [3]. Probably the most prominent example of large-scale sequencing projects is the 1000 Genomes Project (now International Genome Sample Resource, IGSR), initiated with the goal of sequencing the genomes of more than one thousand human individuals to identify 95% of all genomic variants in the population with allele frequency of at least 1% (down toward 0.1% in coding regions). The final publications from phase 3 of the project report about genetic variations from more than 2,500 genomes [1,12].

Recently, several countries announced large-scale national research programs to capture the diversity of their populations, while some of these efforts started already more than 20 years ago. Since 1996 Iceland's deCODE company is mining Icelanders' genetic and medical data for disease genes. In 2015, deCODE published insights gained from sequencing the whole genomes of 2,636 Icelanders [8]. Genome of the Netherlands (GoNL) is a whole genome sequencing project aiming to characterize DNA sequence variation in the Dutch population using a representative sample consisting of 250 trio families from all provinces in the Netherlands. In 2016, GoNL analysed whole genome sequencing data of 769 individuals and published a haplotype-resolved map of 1.9 million genome variants [10]. Similar projects have been established in larger scale in the UK: Following the UK10K project for identifying rare genetic variants in health and disease (2010-2013), Genomics England was set up in late 2012 to deliver the 100,000 Genomes Project [13]. This flagship project has by now sequenced 100,000 whole genomes from patients and their families, focusing on rare diseases, some common types of cancer, and infectious diseases. The scale of these projects is culminating in the US federal Precision Medicine Initiative, where the NIH is funding the All of Us research program1 to analyze genetic information from more than 1 million American volunteers. Even more extreme suggestions go as far as to propose "to sequence the DNA of all life on Earth"2 .

The main motivation for the collection of these large and comprehensive data sets is the hope for a better understanding of genomic variation and how variants relate to health and disease, but basic research in evolution, population genetics, functional genomics and studies on demographic history can also profit enormously.

One important approach connecting evolution and functional genomics is the search for genomic regions under natural selection based on population data. The selection coefficient [7] is an established parameter quantifying the relative fitness of two genetic variants. Unfortunately, haplotype-based methods for estimating selection coefficients have not been designed with the massive genome data sets available today in mind, and may therefore take prohibitively long when applied to large-scale population data. In view of the large population sequencing efforts described above, methods are needed that -at similar sensitivity -scale to much higher dimensions.

Only recently a method for the fast computation of a genome-wide selection scan has been proposed that can be computed quickly even for large datasets [4]. The method is based on a very simple combinatorial string pattern, maximal perfect haplotype blocks. Although considerably faster than previous methods, the running time of the algorithm presented in that paper is not optimal, as it takes O(kn 2 ) time in order to find all maximal perfect haplotype blocks in k genomes of length n each. This is sufficient to analyse individual human chromosomes on a laptop computer, for datasets of the size of the 1000 Genomes Project (1,000s of genomes and 1,000,000s of variations). However, with the larger datasets currently underway and with higher resolution it will not scale favourably. More efficient methods are therefore necessary and it was phrased as an open question whether there exists a linear-time algorithm to find all maximal perfect haplotype blocks.

In this paper we settle this open problem affirmatively. More specifically, after some basic definitions in Section 2 we present in Sections 3 and 4 two new algorithms for finding all maximal perfect haplotype blocks in optimal time. The latter of these two algorithms is then experimentally compared to the one from [4] in Section 5, proving its superiority in running time by a factor of about 5 and memory usage by up to two orders of magnitude for larger data sets. Section 6 concludes the paper.

Basic Definitions

The typical input to genome-wide selection studies is a set of haplotype-resolved genomes, or haplotypes for short. Clearly, for a given set of haplotypes only those sites are of interest where there is variation in the genomes. Therefore, formally, we consider as input to our methods a k × n haplotype matrix where each of the k rows corresponds to one haplotype and each of the n columns corresponds to one variable genetic site. Most methods distinguish only between ancestral and derived allele, a consequence of the popular infinite sites assumption [11]. Therefore the entries in a haplotype matrix are often considered binary where the ancestral allele is encoded by 0 and the derived allele is encoded by 1. However, the computational problem and its solutions considered in this paper do not depend on this restriction and instead are applicable to any type of sequence over a constant-size alphabet Σ.

The concept of a maximal perfect haplotype block as defined in [4] is the following, where S| K denotes the elements of an ordered set S restricted to index set K:

Definition 1. Given k sequences S = (s 1 , . . . , s k ) of same length n (representing the rows of a haplotype matrix), a maximal perfect haplotype block is a triple (K, i, j) with K ⊆ {1, . . . , k}, |K| ≥ 2 and 1 ≤ i ≤ j ≤ n such that 1. s[i, j] = t[i, j] for all s, t ∈ S| K (equality), 2. i = 1 or s[i -1] = t[i -1] for some s, t ∈ S| K (left-maximality), 3. j = n or s[j + 1] = t[j + 1] for some s, t ∈ S| K (right-maximality), and 4. K ⊆ {1, . . . , k} with K ⊂ K such that s[i, j] = t[i, j] for all s, t ∈ S| K (row- maximality).
Definition 1 is illustrated in Figure 1. In [4] it was shown that the number of maximal perfect haplotype blocks is in O(kn), while the algorithm presented there takes O(kn 2 ) time to find all blocks. It is based on the observation that branching vertices in the trie T p of the suffixes of the input sequences starting at position p correspond to right-maximal and row-maximal blocks, while left-maximality can be tested by comparing T p and T p-1 . In the next two sections we show how this running time can be improved.

WA B I 2 0 1 9 8:4

Finding all maximal perfect haplotype blocks in linear time 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 1 1 1 0 0 Figure 1 Illustration of Definition 1: a binary 3 × 8 haplotype matrix with three maximal perfect haplotype blocks ({1, 3}, 1, 4), ({2, 3}, 4, 7) and ({1, 2, 3}, 6, 7) highlighted. (The example contains additional maximal perfect haplotype blocks that are not shown.)

Linear-Time Method I: Based on Suffix Trees

In this section, we present our first algorithm to find all maximal perfect haplotype blocks in linear time. This solution is purely theoretical, it would likely require large amounts of memory while being slow in practice. However, it demonstrates the connection to the concept of maximal repeats in strings. We recall from [9, Section 7.12] that a maximal repeat is a substring occurring at least twice in a string or a set of strings and such that it cannot be extended to the left or to the right without losing occurrences.

Let S = s 1 $ 1 s 2 $ 2 . . . s k $ k
, with the $ i being k different characters absent from the original alphabet Σ. The key point is that any maximal perfect haplotype block in S is a maximal repeat in S. The opposite is not true: In a maximal perfect haplotype block, all occurrences of the repeat are located at the same position of each sequence of S (equality condition in Definition 1), while this constraint does not exist for maximal repeats in S.

Nevertheless, finding all maximal perfect haplotype blocks in S can be performed by computing all maximal repeats in S, while keeping only those whose occurrences are located at the same positions over all s i in which they occur. This can be done by performing the following procedure:

1. "Decorate" each sequence s i ∈ S to create s + i = α 0 s i [1]α 1 s i [2]α 2 . . . s i [n]α n ,
where the index characters α 0 , α 1 , . . . , α n are n + 1 symbols from an alphabet Σ , disjoint from the original alphabet Σ.

Find in

S + = s + 1 $ 1 s + 2 $ 2 . . . s + k $ k all maximal repeats.
3. Any maximal repeat r = α p r 1 α p+1 r 2 α p+2 . . . r α p+ in S + with ≥ 1 corresponds to a maximal perfect haplotype block of length , starting at position p + 1 in the input sequences from S.

The key idea here is that the index characters impose that each maximal repeat occurrence starts at the same position in all sequences and, as a consequence, ensure that all occurrences occur in distinct sequences from S.

Hence any maximal repeat r = α p r 1 α p+1 . . . r α p+ defines a unique maximal perfect haplotype block (K, p + 1, p + ). The value |K| is the number of occurrences of r. Also the set K can be derived from occurrence positions of r in S + , as any position in r corresponds to a unique position in S. We prefer to omit useless technical details here.

The maximal repeat occurrences in S + may be found using a suffix tree, constructed in time linear with respect to the size of the input data O(kn), even for large integer alphabets [6], as we have here. The maximal repeat detection is also linear with the size of the input data [9, Section 7.12.1]. Therefore the overall time complexity is O(kn). 1 2 3 4 5 6 a 6 a -1 6 1 0 0 1 0 0 2 3 1 0 0 0 0 0 4 1 0 0 0 1 1 0 1 5 0 1 0 0 0 0 5 2 0 0 1 1 0 0 3 4 1 2 3 4 5 6 d 6 1 0 0 0 0 0 7 0 1 0 0 0 0 3 1 0 0 1 0 0 5 0 0 1 1 0 0 4 0 0 0 1 1 0 the inverse permutation of a l . For readers familiar with string processing terminology, the arrays a l and a -1 l are analogous to the suffix array and the inverse suffix array, respectively, while the arrays d l are analogous to the LCP array. We note that the term pBWT is somewhat misleading, since there is no array analogous to the BWT.

Conditions 1, 2 and 4 (equality, left-maximality and row-maximality) of Definition 1 can be stated in terms of the arrays a l and d l as follows. Suppose we have a block (K, i, j). If the block is a maximal perfect haplotype block, then the set {a -1 j [r] | r ∈ K} must be a contiguous range [x, y] of indices such that the following holds:

d j [r] ≤ i for all r ∈ [x + 1, y] (equality), there exists at least one r ∈ [x + 1, y] such that d j [r] = i (left-maximality), and (x = 1 or d j [x] > i) and (y = k or d j [y + 1] > i) (row-maximality).
We call a block satisfying these conditions an available block and [x, y] the colexicographic range of the block. Let us consider the set B l of available blocks ending at column l. We have that |B l | ≤ k because each available block corresponds to a distinct branching node in the trie of the reverses of {S[1][1..l], . . . , S[k][1..l]}, and the number of branching nodes in the trie is bounded from above by the number of leaves k. The branching nodes of the trie can be enumerated in O(k) time by using a standard algorithm [2] for enumerating LCP intervals of the LCP array of the trie, LCP l [r] = l -d l [r] + 1. This gives us the colexicographic ranges [x, y] of all available blocks in B l . An example is shown in Figure 2.

The only thing left is to show how to check the right-maximality property of an available WA B I 2 0 1 9

8:6

Finding all maximal perfect haplotype blocks in linear time block, i.e., whether

j = n or |{S[a[r]][j + 1] : r ∈ [x, y]}| ≥ 2.
To check the condition in constant time for j = n, we build a bit vector

V j such that V j [1] = 1 and V j [r] = 1 if and only if S[a j [r]][j + 1] = S[a j [r -1]][j + 1]
. Now the block is right-maximal if and only if V j [x + 1..y] contains at least one 1-bit. We can build a vector of prefix sums of V j to answer this question in constant time.

Time and space complexity

We assume the column stream model, where we can stream the haplotype matrix column by column. We can thus build the arrays d l , a l and a -1 l on the fly column by column [5], and also easily build the required prefix sums of arrays V l from these. The time is O(nk), since each of the n columns takes O(k) time to process. The algorithm needs to keep in memory only the data for two adjacent columns at a time, so in space O(k) we can report the colexicographic ranges of all maximal blocks ending in each column l ∈ [1, n]. If the colexicographic range of a block at column l is [x, y], then the rows in the original haplotype matrix are a l [x], a l [x + 1], . . . , a l [y]. There are O(nk) blocks and O(k) rows per block, so the time to report all rows explicitly is O(nk 2 ). Alternatively, we can store a complete representation of the answer taking O(nk) space by storing all the a l arrays and the colexicographic ranges of the maximal perfect blocks for each column, from which we can readily report all rows in any maximal perfect block in constant time per row.

Empirical Evaluation

Since the algorithm of Section 3 is mostly of theoretical interest, we evaluate only the pBWTbased algorithm presented in Section 4. The source code is available from https://gitlab. com/bacazaux/haploblocks. As a baseline for comparison we use the implementation of the trie-based algorithm by Cunha et al. [4], available from the same gitlab site. The experiments were run on a machine with an Intel Xeon E5-2680 v4 2.4GHz CPU, which has a 35 MB Intel SmartCache. The machine has 256 gigabytes of memory at a speed of 2400MT/s. The code was compiled with g++ using the -Ofast optimization flag.

Our test data consists of chromosomes 2, 6 and 22 from phase three of the 1000 Genomes Project [1], which provides whole-genome sequences of 2,504 individuals from multiple populations worldwide. We preprocessed the data by extracting all biallelic SNPs from the provided VCF files3 and converting them to a binary haplotype matrix using our own program vcf2bm, also available from https://gitlab.com/bacazaux/haploblocks.

Our implementation has a user-defined parameter allowing to adjust the minimum size of a reported maximal perfect haplotype block (K, i, j), where size is defined as the width (j -i + 1) times the number of rows (|K|) in the block. Table 1 shows the running times and memory usage of our implementation on the different chromosomes and for different settings of the minimum block size parameter. The larger the minimum block size, the faster the algorithm is, because there are less blocks to report. In general, it takes only a few minutes to process a complete human chromosome. Locating all 323,163,970 blocks of minimum size 10 6 in all 22 human autosomes (non-sex chromosomes) took in total 4 hours and 26 minutes with a memory peak of 12.8 MB (data not shown).

Table 2 consumption is up to 93 times smaller.

Using the method for estimating a local selection coefficient from the size of maximal perfect haplotype blocks covering a certain genomic region presented in [4], it is now possible to generate chromosome-wide selection scans indicating the loci of maximum selection, as shown in Figure 3 for the complete human chromosome 2 (size parameter 10 6 ), in less than half an hour.

Conclusion

In this paper we presented two algorithms that are able to find all maximal perfect haplotype blocks in a haplotype matrix of size k × n in linear time O(kn). In particular the second method, based on the positional Burrows-Wheeler Transform, performs also extremely well in practice, as it allows for a streaming implementation with extremely low memory footprint. While an initial implementation of the method is available from https://gitlab.com/ bacazaux/haploblocks, a user-friendly software combining the algorithm presented here with the computation of the selection coefficient suggested in [4] remains to be developed.

Figure 2

 2 Figure2Available blocks. Left: an example of a haplotype matrix up to column 6 with the two arrays a6 and a -1 6 on the right. Center: the colexicographically sorted rows and the array d6 listed on the right. Right: the trie of the reverses of the rows of the matrix. For example, the block ({1, 2, 4, 5}, 5, 6) is available because a-1 6 (1) = 3, a -1 6 (2) = 1, a -1 6 (4) = 2, a -1 6 (5) = 4 is the consecutive range [x, y] = [1, 4], we have d6[r] ≤ 5 for all r ∈ [1 + 1, 4] with d6[3] = 5, and we have x = 1 and d6[4 + 1] = 6 > 5. The repeat in the block is 00, and we see it is a branching node in the trie on the right.

Table 1

 1 Running times and memory usage of our pBWT-based implementation. Note that in our streaming implementation the memory usage is dominated by the number of haplotypes times the buffer size, and therefore is essentially constant in this study.

	shows a comparison of our implementation to the trie-based implementation
	from [4]. Our implementation is about 5 times faster on all datasets, and the memory

Table 2

 2 Comparison of the trie-based implementation from [4] and our pBWT-based implementation with minimum block size 10 6 .

allofus.nih.gov

Biologists propose to sequence the DNA of all life on Earth, by Elizabeth Pennisi. Science News, Feb. 24, 2017. https://doi.org/10.1126/science.aal0824.

ftp://ftp.1000genomes.ebi.ac.uk/vol1/ftp/release/20130502/

Acknowledgements

We thank the organizers of DSB 2019 (dsb2019.gitlab.io) for giving us the opportunity to present earlier work in this area and start a discussion from which the present results originated. We would also like to thank Michel T. Henrichs for providing a script to convert VCF files to haplotype matrices and for assisting with the production of Figure 3.

JSPS KAKENHI Grant Number JP16H02783

Pierre Peterlongo: ANR Hydrogen ANR-14-CE23-0001