The Dang Huynh

Fabien Mathieu

Laurent Viennot

LiveRank: How to Refresh Old Crawls

This paper considers the problem of refreshing a crawl. More precisely, given a collection of Web pages (with hyperlinks) gathered at some time, we want to identify a significant fraction of these pages that still exist at present time. The liveness of an old page can be tested through an online query at present time. We call LiveRank a ranking of the old pages so that active nodes are more likely to appear first. The quality of a LiveRank is measured by the number of queries necessary to identify a given fraction of the alive pages when using the LiveRank order. We study different scenarios from a static setting where the Liv-eRank is computed before any query is made, to dynamic settings where the LiveRank can be updated as queries are processed. Our results show that building on the PageRank can lead to efficient LiveRanks for Web graphs.

Introduction

One of the main challenges for large networks data mining is to deal with the high dynamics of huge datasets: not only are these datasets difficult to gather, but they tend to become obsolete very quickly.

In this paper, we are interested in the evolution of large Web graphs at large time scale. We focus on batch crawling, where starting from a completely outdated snapshot of a large Web crawl, we want to identify a significant fraction of the pages that are still alive now.

Our motivation is that many old large snapshots of the Web are available today. Reconstructing roughly what remains from such archives could result in interesting studies of the long term evolution of these graphs. For large archives where one is interested in a fraction of the dataset, recrawling the full set of pages can be prohibitive. We propose to identify as quickly as possible a significant fraction of the pages that are still alive. Further selection can then be made to identify a set of pages suitable for the study and then to crawl them. Such techniques would be especially interesting when testing the liveness of an item is much lighter than downloading it completely. This is for instance the case for the Web with HEAD queries compared to GET queries. If a large amount of work has been devoted to maintaining fresh a set of crawled pages, little attention has been paid to the coverage obtained by partial recrawling a fairly old snapshot.

Problem formulation: Given an old snapshot, our goal is to identify a significant fraction of the pages that are still alive or active now. The cost we incur is the number of fetches that are necessary to attain this goal. A typical cost measure will be the average number of fetches per active item identified. The strategy for achieving this goal consists in producing an ordering for fetching the pages. We call LiveRank an ordering such that the pages that are still alive tend to appear first. We consider the problem of finding an efficient LiveRank in three settings: static when it is computed solely from the snapshot and the link relations recorded at that time; sampling-based when a sampling is performed in a first phase allowing to adjust the ordering according to the liveness of sampled items; dynamic when it is incrementally computed as pages are fetched.

Contribution: We propose various LiveRank algorithms based on the graph structure of the snapshot. We evaluate them on two Web snapshots (from 10 to 20 million nodes). We show that a rather simple combination of a small sampling phase and PageRank-like propagation in the remaining of the snapshot allows to gather from 15% to 75% of the active nodes with a cost that remains within a factor of 2 from the optimal ideal solution.

Related work:

The process of crawling the Web has been extensively studied. A survey is given by Olston and Najork [START_REF] Olston | Web crawling[END_REF]. The issue we investigate here is close to a problem introduced by Cho and Ntoulas [START_REF] Cho | Effective change detection using sampling[END_REF]: they use sampling to estimate the frequency of change per site and then to fetch a set of pages such that the overall change ratio of the set is maximized. Their technique consists in estimating the frequency of page change per site and to crawl first sites with high frequency change. Tan et al. [START_REF] Tan | A clustering-based sampling approach for refreshing search engine's database[END_REF] improve slightly over this technique by clusterizing the pages according to several features: not only their site (and other features read from the URL) but also content based features and linkage features (including pagerank and incoming degree). A change ratio per cluster is then estimated through sampling and clusters are downloaded in descending order of the estimated values. More recently, Radinsky and Bennett [START_REF] Radinsky | Predicting content change on the web[END_REF] investigate a similar approach using learning techniques and avoiding the use of sampling. Note that these approaches mainly focus on highly dynamic pages and use various information about pages whereas we are interested in stable pages and we use only the graph structure, which is lighter. With a slightly different objective, Dasgupta et al. [START_REF] Dasgupta | The discoverability of the web[END_REF] investigate how to discover new pages while minimizing the average number of fetches per new page found. Their work advocates for: a greedy cover heuristic when a small fraction of the new pages has to be discovered quickly: an out-degree-based heuristic gathering a large fraction of the new pages. Their framework is close to ours and inspired the cost function used in this paper. A related problem consist in estimating which pages are really valid among the "dangling" pages on the frontier of the crawled web (those that are pointed by crawled pages but that were not crawled themselves). Eiron et al. propose to take this into account in the PageRank computation [START_REF] Eiron | Ranking the web frontier[END_REF]. In a similar trend, Bar-Yossef et al. [START_REF] Bar-Yossef | Sic transit gloria telae: Towards an understanding of the web's decay[END_REF] propose to compute a "decay" score for each page by refining on the proportion of dead links in a page. Their goal is to identify poorly updated pages. This score could be an interesting measure for computing a LiveRank, however its computation requires to identify dead links. It is thus not clear how to both estimate it and at the same time try to avoid to test dead pages.

Roadmap: In the next Section, we propose a simple cost function to evaluate the quality of a LiveRank and we introduce several classes of possible LiveRanks. For evaluating the proposals, we use two datasets from the .uk Web, for which we derived some ground truth of page liveness. This is described in Section 3. Lastly, in Section 4, we benchmark our LiveRanks against the datasets and discuss the results.

Model

Let G = (V, E) be a directed graph obtained from a past Web snapshot, where V represents the crawled pages and E the hyperlinks: For i, j in V , (i, j) is in E if, and only if, there is a hyperlink to j in i.

Let n denote the size of V . At present time, only a subset of G are still alive (the exact meaning of liveness will be detailed in the next Section). We call a the function that tells if pages are alive or not: a(X) denotes the alive pages from X ⊂ V , while ā(X) stands for X \ a(X). Let n a be |a(V )|.

The problem we need to solve can be expressed as: how to crawl a maximum number of pages from a(V ) with a minimal crawling cost. In particular, one would like to avoid crawling too many pages from ā(V ). If a was known, the task would be easy, but testing the activity of a node obviously requires to crawl it. This is the rationale for the notion of LiveRank.

Performance metric

Formally, any ordering on V can be seen as a LiveRank, so we need some performance metrics to measure the efficiency in ranking the pages from a(V ) first. Following [START_REF] Dasgupta | The discoverability of the web[END_REF], we define the LiveRank cost as the average number of page retrievals necessary to obtain one alive page, after a fraction 0 < α ≤ 1 of the alive pages has been retrieved.

In details, let L i represent the i first pages returned by a LiveRank L, and let i(L, α) be the smallest integer such that |a(Li)| na ≥ α. The cost function of L (which depends on α) is then defined by: cost(L, α) = i(L, α) αn a . A few remarks on the cost function:

-It is always at greater than or equal to 1. An ideal LiveRank would perfectly separate a(V ) from rest of the nodes, so its cost function would be 1. Without some oracle, this requires to test all pages, which is exactly what we would like to avoid. The cost function allows to capture this dilemma. -Keeping a low cost becomes hard as α gets close to 1: without some clairvoyant knowledge, capturing almost all active nodes is almost as difficult as capturing all actives nodes. For that reason, one expects that when α gets close to 1, the set of nodes any real LiveRank will need to crawl will tend to V , leading to an asymptotical cost n na . This will be verified in Section 4.

-Lastly, one may have noticed that the cost function uses n a = |a(V )|, for which an exact value requires a full knowledge of liveness. This is not an issue here as we will perform our evaluation on datasets where a is known. For use on datasets without ground truth, one could either use an estimation of n a based on a sampling or use a non-normalized cost function (for instance the fraction of alive pages obtained after i retrievals).

PageRank

Some of the proposed LiveRanks are based on PageRank. In order to be selfcontained, we provide a brief reminder. PageRank is a link analysis algorithm that has been initially introduced in [START_REF] Page | The PageRank Citation Ranking: Bringing Order to the Web[END_REF] and used by the Google Internet search engine. It assigns a numerical importance to each page of a Web graph. The principle of PageRank [START_REF] Page | The PageRank Citation Ranking: Bringing Order to the Web[END_REF] is to use the structural information from G to attribute importance according to the following (informal) recursive definition: a page is important if it is referenced by important pages. Concretely, to compute PageRank value, denoted by the row vector Y , one needs to find the solution of the following equation:

Y = dY A + (1 -d)X, (1)
where A is a substochastic matrix derived from the adjacency matrix of G, d < 1 a so-called damping factor (often set empirically to d = 0.85), and X 0 is a teleportation vector. X represents a kind of importance by default that is propagated from pages to pages according to A with a damping d.

Computation of PageRank vectors has being widely studied. Several specific solutions were proposed and analysed [START_REF] Langville | Deeper inside pagerank[END_REF][START_REF] Bianchini | Inside pagerank[END_REF] including power method [START_REF] Page | The PageRank Citation Ranking: Bringing Order to the Web[END_REF], extrapolation [START_REF] Haveliwala | Computing pagerank using power extrapolation[END_REF][START_REF] Kamvar | Extrapolation methods for accelerating pagerank computations[END_REF], adaptive on-line method [START_REF] Abiteboul | Adaptive on-line page importance computation[END_REF], etc.

We now present the different LiveRanks that we will consider in this paper. We broadly classify them in three classes: static, sample-based and dynamic.

Static LiveRanks

Static LiveRanks are computed offline using uniquely the information from G. That makes them very basic, but also very easy to be used in a distributed way: given p crawlers of similar capacities, if L = (l 1 , . . . , l n ), simply assign the task of testing node l i to crawler i mod p.

We propose the following three static LiveRanks.

Random permutation (R) will serve both as a reference and as a building block for more advanced LiveRanks. R ignores any information from G, so its cost should be in average n na , with a variance that tends to 0 as α tends to 1. We expect good LiveRanks to have a cost function significantly lower than cost(R).

Decreasing Indegree ordering (I) is a simple LiveRank that we expect to behave better than a random permutation. Intuitively, a high Indegree can mean some importance, and important pages may be more robust. Also, older pages should have more incoming edges (in terms of correlation), so high degree pages can correspond to pages that were already old at the time G was crawled, and old pages may last longer than younger ones. Sorting by degree is the easiest way to exploit these correlations.

PageRank ordering (P ) pushes forward the indegree idea. The intuition is that pages that are still alive are likely to point toward pages that are still alive also, even considering only old links. This suggests to use a PageRank-like importance ranking. In absence of further knowledge, we propose to use the solution of (1) using d = .85 (typical value for Web graphs) and X uniform on V .

Note that it is very subjective to evaluate PageRank as an importance ranking, as importance should be ultimately validated by humans. On the other hand, the quality of PageRank as a static LiveRank is straightforward to verify, for instance using our cost metric.

The possible existence of correlation between Indegree (or PageRank) and liveness will be verified in Section 3.3.

Sample-based LiveRanks

Using a LiveRank consists in crawling V in the prescribed order. During the crawl, the activity function a becomes partly available, and it is natural to reinject the obtained information to enhance the retrieval, producing a new LiveRank. Following that idea, we consider here a two-steps sample-based approach: we first fix a testing threshold z and test z items following a static LiveRank (like R, I or P ). For the set Z of nodes tested, which we call indifferently sample set or training set, we thus obtain the knowledge of a(Z) and ā(Z), which allows us to recompute the LiveRank of the remaining untested pages.

Because the sampling uses a static LiveRank, and the adjusted new LiveRank is static as well, sample-based LiveRanks are still easy to use in a distributed way as the crawlers only need to receive crawl instructions on two occasions.

Notice that in the case where the sampling LiveRank is a random permutation, |a(Z)| n z can be used as an estimate for n a . This can for instance be used to decide when to stop crawling if we desire to identify αn a active nodes in a(V ).

Simple adaptive LiveRank (P a ) When a page is alive, we can assume it increases the chance that pages it points to in G are also alive, and that life is transmitted somehow through hyperlinks. Following this idea, a possible adaptive LiveRank consists in taking for X in (1) the uniform distribution on a(Z). This diffusion from such an initial set can be seen as a kind of breadth-first traversal starting from a(Z), but with a PageRank flavour.

Double adaptive LiveRank (P +/a

) The simple adaptive LiveRank does not use the information given by ā(Z). One way to do this is to calculate an "anti"-PageRank based on ā(Z) instead of a(Z). This ranking would represents a kind of diffusion of death, the underlying hypothesis being that dead pages may point to pages that tend to be dead. As a result, we obtain a new LiveRank by combining these two PageRanks. After having tested several possible combinations not discussed in this paper, we empirically chose to weight each node by the ratio of the two sample-based PageRank, after having set all null entries of the anti-PageRank equal to the minimal non-null entry.

Active-site first LiveRank (ASF) To compare with previous work, we propose the following variant inspired by the Dasgupta et al. [START_REF] Dasgupta | The discoverability of the web[END_REF] strategy for finding pages that have changed in a recrawl. Their algorithm is based on sampling for estimating page change rate for each website and then to crawl sites by decreasing change rate. In details, Active-site first (ASF) consists in partitioning Z into websites determined by inspecting the URLs. We thus obtain a collection Z 1 , . . . , Z p of sets. For each set Z i corresponding to some site i, we obtain an estimation |a(Z i )|/|Z i | of its activity (i.e. the fraction of active pages in the site). We then sort the remaining URLs by decreasing site activity.

Dynamic LiveRanks

Instead of using the acquired information just one time after the sampling, Dynamic LiveRanks are continuously computed and updated on the fly along the entire crawling process. On the one hand, this gives them real-time knowledge of a, but on the other hand, as the dynamic LiveRank may evolve all the time, they can create synchronization issues when used by distributed crawlers.

Like for sample-based LiveRanks, dynamic LiveRanks use a training set Z of z pages from a static LiveRank. This allows to bootstrap the adjustment by giving a non-empty knowledge of a, and prevents the LiveRank from focusing on only a small subset of V .

Breadth-First Search (BFS) With BFS, we aim at taking direct advantage of the possible propagation of liveness. The BFS queue is initialized with the (uncrawled) training set Z. The next page to be crawled is popped from the queue following First-In-First-Out (FIFO) rule. If the selected page appears to be alive, all of its uncrawled outgoing neighbors are pushed into the end of the queue. When the queue is empty, we pick the unvisited page with highest PageRank3 .

Alive indegree (AI) BFS uses a simple FIFO queuing to determine the processing order. We now propose AI which provides a more advanced page selection scheme. For AI, each page in the graph is associated with a live score value indicating how many reported alive pages point to it. These values are set to zeros at the beginning and always kept up-to-date. AI is initialized by testing Z: each node in a(Z) will increment the associated values of its out-going neighbors by one. After Z is tested, the next node to be crawled is simply the one with highest live score (in case of equality, to keep things consistent, we pick the node with highest PageRank). Whenever a new alive node is found, we update the live scores of its untested neighbors.

With Dynamic LiveRank, it is natural to think of a dynamic PageRank-based strategy where PageRank vector is recursively computed. Starting from a uniform distribution on a(Z), we obtain X in [START_REF] Abiteboul | Adaptive on-line page importance computation[END_REF]. Then a new teleportation vector is constructed as a uniform distribution on largest value entries of X, i.e., those which are considered probably alive after the first diffusion of a(Z). The process continues and X is updated iteratively. However, this method is not efficient since it can not escape from the locality of a(Z).

We chose to evaluate the proposed LiveRanks on datasets of the British domain .uk available on the WebGraph platform 4 . In this Section, we present these datasets, describe how we obtained the alive function a and observe the correlations between a, indegree and PageRank.

uk-2002 dataset

The main dataset we will use is the web graph uk-20025 crawled by UbiCrawler [START_REF] Boldi | Ubicrawler: A scalable fully distributed web crawler[END_REF]. This snapshot, crawled in 2002, contains 18,520,486 pages and 298,113,762 hyperlinks.

The preliminary task is to determine a, the liveness of the pages of the snapshot. For each URL, we have performed a GET request and hopefully obtained a corresponding HTTP code. Our main findings are:

-One third of the total pages are no longer available today, the server returns error 404. -One fourth have a DNS problem (which probably means the website is also dead). -For one fifth of the cases, the server sends back the redirection message 301.

Most redirections for pages of an old site lead to the root of a new site. If we look at the proportion of distinct pages alive at the end of redirections, it is as low as 0.1%. -Less than 13% of pages return the code 200 (success). However, we found out that half of them actually display some text mentioning that the page was not found. To handle this issue, we have fully crawled all the pages with code 200 and filtered out pages whose title or content have either Page Not Found or Error 404.

The results are summarized in Table 1. In the end, our methodology led to finding out 1,164,998 alive pages, accounting for 6.4% of the dataset.

uk-2006 dataset

The settings of uk-2002 are rather adversarial (old snapshot with relatively few alive pages), so we wanted to evaluate the impact of LiveRanks on shorter time scales. In absence of fresh enough available datasets, we used the DELIS dataset [START_REF] Boldi | A large time-aware graph[END_REF], a series of twelve continuous snapshots

Correlations

The rationale behind the LiveRanks I and P is the assumption that the liveness of pages is correlated to the graph structure of the snapshot, so that a page with high in-degree or PageRank has more chances to stay alive.

To validate this, we plot in Figure 1 the cumulative distribution of in-degree (figure 1a) and PageRank (figure 1b) for alive, dead, and all pages of the uk-2002 dataset. We observe that the curve for active nodes is slightly shifted to the right compared to the other curves in each figures: active users tend to have slightly higher in-degree and PageRank than in the overall population. The bias is bigger for PageRank, suggesting that LiveRank (P) should perform better than LiveRank (I).

LiveRanks evaluation

After having proposed several LiveRanks in Section 2 and described our datasets in previous Section, we can now benchmark our proposals.

All our evaluations are based on representations of the cost functions. In each plot, the x-axis indicates the fraction α of active nodes we aim to discover and the y-axis corresponds to the relative cost of the crawl required to achieve that goal. A low curve indicates an efficient LiveRank. Like said in Section 2.1: an ideal LiveRank would achieve a constant cost of 1; a random LiveRank is quickly constant with an average cost n/n a ; any non-clairvoyant LiveRank will tend to cost n/n a as α goes to 1.

We mainly focus on the uk-2002 dataset. When it is not specified, the training set contains the z = 100000 pages of higher (static) PageRank.

Static and sample-based LiveRanks

We first evaluate the results of static and sample-based LiveRanks. The results are displayed in Figure 2. For static LiveRanks, we see as expected that a random ordering gives an almost constant cost equal to n na ≈ 15.6. Indegree ordering (I) and PageRank (P) significantly outperform this result, PageRank being the best of the three: it is twice more efficient than random for small α, and still performs approximately 30% better when up to α = 0.6. We then notice that we can get even much better costs with sample-based approaches, the double-adaptive LiveRank P +/a giving a significant improvement over the simple-adaptive one P a . P +/a allows improving the ordering by a factor of 6 approximately around α = 0.2 with a cost of 2.5 fetches per active node found. The cost for gathering half of the alive pages is less than 4, and for 90% it stays less than 10. but similar results were obtained for P a . Figure 3a shows the impact of the size z of the sampling set (sampling the top PageRank pages). We observe some trade-off: as the sampling set grows larger, the initial cost increases as the sample does not used any fresh information, but it results in a significant increment of efficiency in the long run. For this dataset, taking a big training set (z=500 000) allows reducing the cost of the crawl for α ≥ 0.4, and maintains a cost less than 4 for up to 90%.

Another key aspect of the sampling phase is the qualitative choice of the sample set. Using z=100 000, we can observe in Figure 3b We believe that the reason is that a random sample avoids a locality effect in the sampling set as high PageRank pages tend to concentrate in some local parts of the graph. To verify that, we tried to modify Indegree and PageRank selection to avoid to select neighbor pages. The results (not displayed here) show a significant improvement while staying less efficient than using a random sample.

Note that double-adaptive LiveRank through random sampling offers a very low cost, within a factor of 2 from optimal for a large range of values α.

Dynamic LiveRanks

We then consider the performance of fully dynamic strategies, using the doubleadaptive LiveRank with random training set as a landmark. The results are displayed in Figure 4a. We see that bread-first search BFS and alive indegree AI perform similarly to double adaptive P +/a for low α and can outperform it for large α (especially BFS). BFS begin to significantly outperform double adaptive for α ≥ 0.5. However, if one needs to gather half of the active pages or less, double adaptive is still the best candidate as it is much simpler to operate, especially with a distributed crawler.

Additionally, Figure 4b shows the impact of different sampling sets on BFS and AI. Except for high values of α where a random sampling outperforms other strategies, the type of sampling does not seem to affect the two dynamic LiveRanks as much as it was observed for the double-adaptive LiveRank. We have repeated the same experiments on the dataset uk-2006, where the update interval is only one year. We show in Figure 5 the results for static and sample-based LiveRanks, using for training set z=200 000 (because the dataset is larger) and random sampling. The observation are qualitatively quite similar compared to uk-2002. The main difference is that all costs are lower due to a higher proportion of alive pages ( n na ≈ 2.81). The double-adaptive version still gives the lower relative cost among static and sample-based LiveRanks, staying under 1.4 for a wide range of α.

Comparison with a site-based approach

To compare with techniques from previous work for finding web pages that been updated after a crawl, Figure 6 compares double adaptive P +/a to active-site first ASF with random sampling. The same number of random pages is tested in each site and the overall number of tests is the same as with double adaptive. Note that given the budget z, it was not possible to sample small websites. Unsampled websites are crawled after the sampled ones.

We see that for α greater than 0.9, ASF performs like a random LiveRank. This corresponds to the point where all sampled website have been crawled. That effect aside, the performance of ASF is not as good as double-adaptive LiveRank for earlier α. In the end, ASF only beats P +/a for a small range of α, between 0.7 and 0.85, and the gain within that range stays limited.

Conclusion

In this paper, we investigated how to efficiently retrieve large portions of alive pages from an old crawl using orderings we called LiveRanks. We observed that PageRank is a good static LiveRank. However, we get a significant gain by first testing a small fraction of the pages to adjust the PageRank in a sample-based approach.

Compared to previous work on identifying modified pages, our technique performs similarly for a given large desired fraction (around 80%) when compared to the LiveRank algorithm inspired by the technique in [START_REF] Cho | Effective change detection using sampling[END_REF]. However, outside that range, our method outperforms this technique. Interesting future work could reside in using our techniques for the problem exposed in [START_REF] Cho | Effective change detection using sampling[END_REF] (identification of pages that have changed) and compare with the Website sampling approach. Interestingly, we could not get significant gain when using fully dynamic Liv-eRanks. As noticed before, each of the two phases of the sample-based approach can be easily parallelized through multiple crawlers whereas this would be much more difficult with a fully dynamic approach. The sample-based method could for example be implemented with in two rounds of a simple map-reduce program whereas the dynamic approach requires continuous exchanges of messages between the crawlers.

Our work establishes the possibility of efficiently recovering a significant portion of the alive pages of an old snapshot and advocates for the use of an adaptive sample-based PageRank for obtaining an efficient LiveRank.

To conclude, we emphasize that the LiveRank approach proposed in this paper is very generic, and its field of applications is not limited to Web graphs. It can be straightforwardly adapted to any online data with similar linkage enabling crawling, like P2P networks or online social networks. For future work, our approach will be mathematically extended. The problem can be formulated as an accuracy estimation of LiveRank vector, given a uniform distribution on the alive training set as teleportation vector.

Fig. 1 :

 1 Fig. 1: Cumulative distribution of pages according to Indegree and PageRank.

Fig. 2 :

 2 Fig. 2: Main results on static and sample-based LiveRanks

Fig. 3 :

 3 Fig.3: Impact of the training set rather than selecting it according to the PageRank or by decreasing indegree. We believe that the reason is that a random sample avoids a locality effect in the sampling set as high PageRank pages tend to concentrate in some local parts of the graph. To verify that, we tried to modify Indegree and PageRank selection to avoid to select neighbor pages. The results (not displayed here) show a significant improvement while staying less efficient than using a random sample.Note that double-adaptive LiveRank through random sampling offers a very low cost, within a factor of 2 from optimal for a large range of values α.

  seed Alive Indegree -Top Indegree seed Alive Indegree -Top PR seed BFS -Random seed BFS -Top Indegree seed BFS -Top PR seed Ideal LiveRank (b) Impact of Z on dynamic LiveRanks

Fig. 4 :

 4 Fig. 4: uk-2002 Performance of dynamic LiveRanks

Fig. 5 :

 5 Fig. 5: uk-2006 main evaluation results

Fig. 6 :

 6 Fig. 6: Comparison with the cost of an active-site first LiveRank

Table 1 :

 1 Status of web pages in uk-2002, crawled in December 2013.

	Status	Description	Number of pages Percentage
	Code HTTP 404	Page not found	6 467 219	34,92%
	No answer	Host not found	4 470 845	24,14%
	Code HTTP 301	Redirection	3 455 923	18,66%
	Target 301	Target of redirection	20 414	0,11%
	Code HTTP 200	Page exists	2 365 201	12,77%
	True 200	Page really exists	1 164 998	6,29%
	Others (403,. . . )	Other error	1 761 298	9,51%
	Total	Graph size	18 520 486	100%

  6 starting from 06/2006 to 05/2007 (one-month intervals). We set G to the first snapshot (06/2006). It contains 31,316,403 nodes and 813,807,972 hyperlinks. We then considered the last snapshot (05/2007) as "present time", setting the active set a(V ) as the intersection between the two snapshots. With this methodology, we hope to have a good approximation of a after a one-year period. For this dataset, we obtained n a = 11, 142, 177 "alive" nodes representing 35.56% of the graph.

We tested several other natural options and observed no significant impact.

http://webgraph.di.unimi.it/

http://law.di.unimi.it/webdata/uk-2002/

http://law.di.unimi.it/webdata/uk-union-2006-06-2007-05/


Tatiana Schmatko
email: tatiana.schmatko@ics-cnrs.unistra.fr

Pierre Muller

Mounir Maaloum

Surface charges effects on the 2D conformation of supercoiled DNA

We have adsorbed plasmid pUc19 DNA on a supported bilayer. By varying the fraction of cationic lipids in the membrane, we have tuned the surface charge. Plasmid conformations were imaged by Atomic Force Microscopy (AFM). We performed two sets of experiments: deposition from salt free solution on charged bilayers and deposition from salty solutions on neutral bilayers. Both sets show similar trends: at low surface charge density or low bulk salt concentration, internal electrostatic repulsion forces plasmids to adopt completely opened structures, while at high surface charge density or higher bulk salt concentration, usual supercoiled plectonemes are observed. We experimentally demonstrate the equivalence of surface screening by mobile interfacial charges and bulk screening from salt ions. At low to medium screening, the electrostatic repulsion at plasmid crossings is predominant, leading to a number of crossovers decreasing linearly with the characteristic screening length. We compare our data with an analytical 2D-equilibrated model developed recently for the system and extract the DNA effective charge density when strands are adsorbed at the surface.

Introduction

Since its discovery 1 , supercoiled DNA has been extensively studied by biologists and by physicists. The former were mostly interested in its implication in biological processes [2][3][4][5][6][7][8] , the later were amazed by the beauty of its structure and studied its topology and conformation 9, 10, . Topology and conformation are inter-dependent so that, in order to study the conformation of a supercoiled DNA we need to define a few topological concepts.

In nature, enzymes promote winding of one strand around the other during many cell processes, this is what causes supercoiling. In fact, supercoiled DNA is made of closed circular double stranded DNA where one strand usually winds around the other a specific number of times. As long as the two circular strands are not broken, this number is fixed; it is called the linking number L k .The helical nature of double-stranded DNA leads as well to some natural twist. There is an intrinsic linking number Lk 0 corresponding to the unconstrained number of helical turns for a DNA of a specific length. However the linking number Lk is generally not equal to Lk 0 , it is usually a little smaller. Therefore one introduces the difference: ∆Lk=Lk-Lk 0 . As Lk 0 increases with the DNA length, in practice one uses the supercoiled density σ , which as an intensive parameter, enables the comparison of plasmids of different lengths:

0 k k L L ∆ = σ
Two other numbers are of great importance: the Twist number T W and the Writhing number W r . These three quantities are linked by the following equation: L k =T w +W r . For a fixed linking number, twist can be traded against writhe.

A supercoiled DNA molecule attempts to relax its torsional stress by writhing. Segments of the chain go successively above and below others which finally defines the tertiary structure of the molecule. Writhe gives rise to extra bending. The conformation is fixed by a balance between twist and bending energies in physiological conditions. At lower salt concentrations, the electrostatic repulsion between strands is also involved. For DNA in solution, it is possible to adopt, non-planar conformations, with the lowest total energy that leads to some torsional twist. The reduction of the torsional energy is accompanied by an increase of the bending energy. There is an additional electrostatic energy contribution, which favours slightly open structures. The equilibrium shape thus also depends on the salt concentration in solution. For nonplanar geometries, the torsional energy is proportional to (Tw-L k0 ) 2 , therefore, in practice, Tw remains close to Lk 0 , by adopting a conformation with Wr close to ∆L k . For a planar closed double helix, without any writhe, the constraint of ∆L k would give rise to a huge torsional energy, proportional to ∆L k 2 .

Much is known about the conformation of supercoiled DNA in solution, mostly under the physiological conditions relevant in biology. Many experiments using gradient centrifugation 11 and electrophoresis have been performed in the late 70's. They tend to give precise values for W r , T W and σ, as well as ratios between them 12,13 . The first electron microscopy (EM) images of plasmids were available roughly ten years later 10, 14- 17 . This was the first time one could see what supercoiled DNA looks like. In these experiments, supercoiled DNA is shown to have a plectonemic conformation. For very long DNAs, these plectonemes may have branches as well. It is described as a superhelix of radius r. The number of crossings of one strand above or below the other is n.

W r =n.sinα, where α is the angle between the tangent to one helix and the plane perpendicular to the superhelix axis. One of the works of reference is by Boles et al 10 . It shows perfectly regular plectonemes with a particularly well defined superhelix radius. In this study the authors precisely measured n, r and α and compared their results with those obtained from solution measurements. These observations were confirmed by molecular simulations [18][19][20][21][22][23][24] . AFM data arrived later [25][26][27][28][29][30][31][START_REF] Zuccheri | Applied Physics A: Materials Science & Processing[END_REF][START_REF] Bussiek | [END_REF][34][35] . They systematically show loosely interwound conformations. The observed conformations are much less regular than those seen in EM. Small variations were observed from experiments to experiments, and sometimes the results were discarded because they did not show plectonemic conformations.

In 2002 Zhakharova et al 36 performed small angle neutron scattering on supercoiled DNA.

Their results are in agreement with pioneering EM work. For instance, they obtained in 50 mM NaCl an opening angle α of 50° and a superhelix radius r of 10nm. Surprisingly the superhelix radius distribution was rather large (± 4 nm) in comparison with EM measurements. This cannot be attributed to the precision of the measurement as the resolution of neutron scattering is much better than 4 nm. These results could then go in favour of the AFM loose conformations as well. Neutron scattering does not perturb the molecule and can be trustfully considered, but it is rather difficult to transpose the results to real space. On the other hand, real space experiments like AFM and TEM require the deposition of the molecule at the surface, whose effect on the conformation is often underestimated.

Actually it is an important issue. One might think that the problem of surface effects was solved with the appearance of cryo-EM which is surely a real improvement in this direction 7,37 . With cryo-EM, the sample solution is frozen and micro sliced before imaging, such as we may think that the observed conformation is the real 3D conformation. The results obtained with cryo-EM were by many aspects comparable to those from pioneering TEM work. For example the idea of a perfectly regular 3D, plectonemic conformation was reinforced.

Nonetheless, cryo-EM can generate surface artefacts as well. Sample preparation is very subtle and small volumes are required. The sample thickness is often of the same order of magnitude as size of the molecule, confinement may occur before freezing at the air/water interface which will modify the structure and arrangements of the molecules 37 . At large ionic strength, cryo-EM also showed strong deviations from solution measurements; unexpectedly, the gyration radius of the molecule was seen to increase with the salt concentration 14 17 . This discrepancy was attributed to a quenching of the conformation at very low temperature. Indeed, the native twist of the DNA molecule should increase when the temperature is decreased. Simulations at -50°C have confirmed this assumption 38 .

Our goal in this article is to understand the influence of surface charges when supercoiled DNA is confined in 2D, and to help rationalize seemingly conflicting observations reported in the literature. The physics of the problem is complex. There is entropy loss consecutive to DNA adsorption, entropy gain consecutive to counter-ions release, and there are various electrostatic interactions. For constrained cyclic DNA, supercoiling introduces an extra level of complexity. All these aspects enter the description with an impact depending on the concentration of salt in solution. Vologodski and Cozzarelli 39 performed simulations in order to elucidate the influence of the surface on the conformation of supercoiled DNA. This work focused on non-equilibrium immobilization. Later on, Velichko and coworkers 40 did molecular simulations on supercoiled semi flexible polymers and reported writhe gain when the macromolecule was adsorbed on a surface. The model used to describe the supercoiled macromolecule was a freely-joined chain with uncharged segments. Their study was dedicated to the entropic and mechanical deformation aspects then their conclusions apply probably well to DNA at high salt concentrations. In a more recent Monte Carlo simulation, Fujimoto and Schurr 41 used a model previously validated with supercoiled DNA in solution. They added a surface potential to mimic the 2D immobilization of the molecule. Our own experiments will turn out to be quite close to their simulation results at equilibrium. The authors compared their computation with the AFM results from Lyubchenko and Shlyakhtenko 29 even though neither the surface charge of the amino-modified mica, nor the plasmid supercoiled density, were known. Their results match the AFM data at 160 mM salt and show that after surface immobilization, the DNA molecule seems to rearrange as an unbranched plectoneme. At 10 mM however, they show plectonemic conformations, while experiments were reporting quite open conformations, with multiple strands crossing nearly at the same point. The authors suggested that the unusual multi-arm conformations reported in AFM might be due to irregularities of the surface used for DNA fixing, or local This journal is © The Royal Society of Chemistry 2014 Soft Matter, 2014, 10, 2520-2529 higher charge densities. Starting from this statement, Bussiek and Langowsky [START_REF] Bussiek | [END_REF] performed AFM experiments where the DNA was deposited on polylysine films. The polymer density was varied. Testing linear DNA with the model from Rivetti et al 42 on their surfaces, they showed that for high polylysine densities, DNA was immediately stuck and remained in a conformation that is a projection of the full 3D conformation. For plasmids of the same length they observed conformations that were irregular and frozen. For low polylysine densities, the linear DNAs reached an equilibrated 2D conformation and plasmids were observed with plectonemic conformations. They concluded that the plectonemes were the result of a 2D equilibrium conformation and that open or multi-arm or many crossing conformations were the result of a 3D freezing. This work is a good starting point toward the understanding of surface induced conformations, although internal polymeric electrostatics is not taken into account and surface charges were only considered as an adhesion promoter.

In the present article we present AFM experiments performed on surfaces with known surface charge densities. By adsorbing DNA on lipid bilayers whose composition was a mixture of cationic lipids and zwitterionic phospholipids, we have varied the surface charge quantitatively. Furthermore, lipids are mobile within a membrane which ensures that DNA molecules are not frozen and conformations should be equilibrated in 2D. The lipids diffusion coefficient has been measured by Fluorescence Recovery After Patterned Photobleaching (FRAPP) 43 ; it is 0.7 µm 2 .s -1 at room temperature. Our membranes are in the gel phase where the dynamics are 1000 times slower than in the fluid phase, but still fast enough to allow small segments of the DNA chain to move and rearrange at the surface. Thus, we can study the influence of the charge density without risks of freezing the conformations. To our knowledge this is the first time that charged lipid membranes have been used to observe supercoiled DNA conformations by AFM. In contrast to bare mica or polylysine films, a membrane is a soft, elastic substrate for the deposition of DNA. It allows the molecule to rearrange. On mica, in the presence of divalent cations, the location of the surface charges is constrained by the crystal lattice. On membranes, charges are fairly mobile. We study the influence of the surface charge density on the conformation of supercoiled DNA. We observe various 2D equilibrium conformations: plectonemic conformations as well as open conformations or loose conformations with only a few crossings. This merely depends on the amount of mobile charges around the molecule, either in the solution or at the surface. We show that in a similar manner to salt in bulk, surface charges screen the phosphate charge on the DNA backbone resulting in an evolution of supercoiled DNA conformations to more regular and more writhed when surface charge is increased. We compare the efficiency of surface screening and bulk screening (from salt), using two sets of experiments.

Materials and methods

AFM

All experiments were performed in tapping mode in a liquid cell of a multimode AFM connected to a nanoscope III controller (Bruker, Santa Barbara). The cantilevers were TAP75 from "Nano and more". The volume of the cell is approximately 400 microliters. The diluted DNA solution was injected into the AFM fluid cell and allowed to adsorb gently on the membrane. Imaging of the conformation of the DNA took place immediately after the injection. A very gentle force was applied. By using small attenuations of the working amplitude we tend to prevent deformation or degradation of the molecule by the tip.

Substrate preparation

Because of its atomic smoothness, mica was chosen for the bare substrate. However, it is negatively charged, therefore it needs to be modified to promote DNA adhesion. To bridge the macromolecule and the mica, we have chosen charged supported lipid bilayers as a substrate. These model membranes are formed by vesicle fusion on mica 44 . By adjusting the ratio between a positively charged lipid and a neutral phospholipid we can vary the surface charge density. Assuming that the proportion of charged lipids within the bilayer is the same as the one within the starting lipid mixture, we can evaluate quantitatively this surface charge density. Liposomes of 30 nm in diameter on average, as determined by dynamic light scattering, are formed by tip sonication of a solution of a mixture of lipids diluted in pure MilliQ water or buffer. The lipid concentration is (0.24 mg/mL). The two lipids chosen are Di-Palmytoyl-Trimethyl-Amonium-Propane, chloride salt (DPTAP), and Di-Palmytoyl-Phosphatidyl-Choline (DPPC) (Avanti Polar Lipids). They only differ by their head, DPTAP being positively charged, while DPPC is zwitterionic. Their fluid-gel transitions are respectively 41 and 46°C, therefore we heated up the vesicle solution during sonication, 20 °C above the fluid gel transition. The hot solution was injected immediately after sonication into the fluid cell of the AFM. When floppy nano vesicles break on the cold mica, they form instantaneously a bilayer that cools rapidly down. The membrane was rinsed with 3 mL water at RT or buffer with the same salt concentration. The obtained bilayers are in the gel phase. They are particularly smooth, even smoother than the bare substrate because they partially absorb the corrugation of the mica. However, due to the mechanism of formation of the bilayer, i.e. small patches nucleating and growing, grain boundary and sometimes small holes showing the bare mica are clearly visible on the AFM images. Mixed DPPC DPTAP bilayers are homogenous at low DPTAP content. Above 50% of DPTAP, we see the appearance of lipid domains of different heights. The domains size does not evolve with time. In the thinner domains, lipids are tilted. These domains also exist at 100% of DPTAP with a higher thickness Soft Matter, 2014, 10, 2520-2529 This journal is © The Royal Society of Chemistry 2014 difference. Most of the time, tilted domains are smaller than the size of the macromolecule and the surface present fractal like digitations. Similar domains have been described by Radler and coworkers 45 for DMPC/DMTAP mixed bilayers. The authors have evidenced a non-linear behaviour of the fluid/gel transition of the lipid mixtures. The temperature T m , at which the lipids main transition occurs, increases up to 45% of DMTAP before decreasing again. They also performed Langmuir isotherms by compressing monolayers of different mixtures at the air water interface. They have shown that at a fixed high pressure, the area per lipid in the monolayer presents a minimum around stoichiometry 1:1. They explain these results by the fact that there should be a high affinity between the phosphate group of the PC head and the ammonium group of the TAP, which is maximized for stoichiometry 1:1. From SAXS results, they deduced that at high DMTAP contents, small domains of solid phases of stoichiometry 1:1 would be embedded in a matrix of LC phase. Although bilayers and monolayers can behave differently; we have performed Langmuir isotherms on DPPC/DPTAP mixed monolayers, which shall give us a good insight into the interactions between the two lipids used in this work. We show them in supplementary information. The presence of DPTAP in the monolayer results in the disappearance of the LE/LC plateau of pure DPPC. Increasing the DPTAP content in monolayers, results in a shift of the isotherms to smaller areas. The minimum is achieved at a 50-50 ratio. Above 50 % of DPTAP, the isotherms are shifted back to the large areas. However, the area per lipid head at fixed pressures hardly changed, in contradiction to what was reported for DMTAP/DMPC mixtures by Radler and coworkers. In conclusion, the surface charge density of the mixed DPPC/DPTAP bilayers shall not be much affected by the peculiar phosphate-ammonium affinity. Moreover, all the quantitative analysis that we have pursued in this article, have been performed at low surface charge densities where the bilayers are still homogenous.

DNA

The DNA used for this study is supercoiled pUc19 2686 base pairs long from New England Biolabs (NEB). It was aliquoted as received (1mg/mL in10mM Tris buffer), without any further purification. This supercoiled DNA appears to be particularly pure of broken or relaxed circles. The manufacturer gives a specification of at least 90% of the DNA in the supercoiled form but agarose gel electrophoresis (1%) performed on several batches in presence of ethidium bromide showed only one bright spot indicating that apparently no relaxed, linear DNA or other sizes of supercoiled DNA were present. One aliquot containing 1 µg of stock DNA was unfrozen a few minutes before each experiment and diluted in ultra-pure milliQ water (resistivity 18.2 MΩ.cm) or in buffer solutions to reach a final concentration of 1µg/mL. It is commonly assumed that DNA is not stable in pure water at room temperature 46 47 . But how fast the denaturation takes place is still an issue. We used the hypochromism of DNA to determine the kinetics of denaturation of pUc19 DNA in the conditions of our AFM experiments 48 . The absorbance of the solution at 260 nm was stable for more than twelve hours at RT. It increased rapidly and reached a plateau when heating the sample up to 80°C (See supplementary information fig. S1). This result clearly shows that the DNA we used is stable enough at RT for the time of our AFM experiment although it denatures quickly at 80°C. This result is not in contradiction with the existence of denaturation bubbles along the chain. However, the fact that plasmids are supercoiled might prevent a complete denaturation at large scale at RT. The precision of the measurement is given by the signal to noise ratio on the UV absorbance signal. It did not seem to evolve with time or be larger than for DNA dissolved in buffer solution.

To assess the exact linking number of our DNA, we performed 1D agarose gel (1.5 % w/w) electrophoresis in presence of chloroquine (2µg/mL) at 20V for 17h. Chloroquine is an intercalating agent inducing positive superturns and thus reducing negative supercoiling of DNA. An appropriate concentration allows a separation of the topoisomers (Fig. 1). As a control, we injected at the same time relaxed pUc19 (one strand nicked with NtbspqI (NEB) and relaxed pUc19 that was afterward religated with T4 DNA ligase (NEB). Both restriction and ligation were done following the manufacturer protocol. The DNA was purified using a Miniprep PCR purification kit (Qiagen) and resuspended in 10 mM Tris buffer at pH 7.5 before being run through the gel. The conformation of relaxed supercoiled DNA (one strand nicked) is not modified by the presence of chloroquine. As it is circular, its hydrodynamic radius is large and the migration on the gel is the slowest (lane 2). Relaxed DNA that has been religated is positively supercoiled by chloroquine and migrates the fastest (lane 1). The spot of the native pUc19 appears in between (lane 3). A line profile of lane3 is given on figure 1.B. Fitting the intensities with a skewed Gaussian curve gave on averaged, ∆L k =-7. This value is in agreement with the literature 36 .

This journal is © The Royal Society of Chemistry 2014

Soft Matter, 2014, 10, 2520-2529

Results and discussions

Deposition of supercoiled DNA from pure water on charged membranes

In a first set of experiments we have studied the conformation of supercoiled pUc19 that we allow to adsorb on lipid bilayers with DPTAP content ranging from 0% to 100%. For the purpose of the experiment we get away from physiological conditions and dilute our DNA in milliQ water. Working in salt free solution allows us to explore a much larger range of DNA surface interactions. After dilution, the residual salt concentration was 10 -5 M; as shown in the supplementary materials, in such a dilution our plasmids are stable at RT for more than 10 hours. Typical conformations of supercoiled pUc19 DNA in milliQ water are shown on Fig. 2 (mixed DPPC/DPTAP bilayers) and Fig 3 (pure DPPC). For each surface charge on Fig. 2, we present a series of zooms on single molecules; all conformations within the population studied look relatively similar, with of course some variations. Next to the AFM images on Fig. 2, we present normalized histograms of the number of nodes (crossovers between strands) and the corresponding Gaussian fit (red line). For each experiment, the statistic was done on fifty molecules on average. For DPTAP fractions above 50%, the nodes number dispersion is quite large, due to surface inhomogeneities. For the pure DPTAP surface it was rather difficult to count nodes: the superhelix was really tight and the AFM tip had trouble resolving the tertiary structure. Discarding this additional surface complexity, we averaged the number of nodes over the entire surface, but restricted our further data analysis to low surface charge densities where the membrane looks homogenous at nanoscopic scale. On DPPC (Fig. 2A and3), Plasmids adopt an open circular conformation in miliQ water. For the record, nicked circles also adopt the same open circular conformation on DPPC. However, plasmids were not nicked in bulk, as shown in the material and method section, and it is unlikely that the adhesion to the substrate would have only broken one strand. In such a geometry pUc19 DNA with a ∆L k of -7 must be particularly constrained. Besides, the surface of DPPC is neutral (in fact zwitterionic), but we do see DNA adhesion. When approaching the membrane, plasmids should be repelled by their own image charge, which is due to the high dielectric contrast between the membrane and water. Therefore there must be some kind of compensating short range interaction that allows for adhesion. The origin of this short range attraction is unclear but we speculate a dipole-charge interaction, the positive charge of the dipole being pointing out of the membrane. On DPPC-DPTAP mixed bilayers, as seen on Fig 2B to 2G, writhing increases with surface charge fraction. For low surface charges, plasmids adopt relatively loose conformations, which tighten along with an increase of the surface charge density. We have noticed that plasmid shapes vary slowly, with nodes shifting along the closed chain, presumably to reach the most stable conformation in 2D. At equilibrium, supercoiled DNA molecules end up in conformations with small loops scattered along a main cycle. Hence, if the crossings are well scattered all over the DNA molecule just after immobilization, their positions evolve during the first minutes. After some time, there is equilibrium of very small loops next to much larger ones. This effect has been previously reported in the literature, in computer simulations performed on 2D knots 49,50 . When charges are added to the bilayer, the superhelix writhes more and more until it reaches the plectonemic conformation that was so often reported in the literature. Additionally, as one can see on Fig. 4, relaxed pUc19 DNA is insensitive to surface charge as it stays perfectly open on 50% DPTAP surface. All surface interactions are likely to be similar for nicked circular DNAs and for closed constrained circular DNAs. We thus deduce that for wild (non-nicked) plasmids, the additional internal stress due to extra turns is accountable for writhing and that supercoiling is made easier and easier when the surface charge is increased. This writhing along with a surface charge increase can be explained with the help of a simple physical argument. Indeed, in a recent analytical study 51 we show that in salt free solution, for constrained polyelectrolytes adsorbed in 2D, the electrostatic interaction at crossing is dominant compared to other interactions. When charges are added to the bilayer, the polarizable interfacial charge screens the DNA charges and thus reduces the electrostatic repulsion at crossings. On DPPC, the zwitterionic surface, the membrane is neutral. DNA bears counter-ions which ordinarily reduce its internal charge. The electrostatic energy needed for crossing strands in 2D is of the order of one hundred of k B T, it exceeds bending and twisting costs (tenths of k B T). Therefore, a DNA molecule would prefer to be under high twist rather than having crossings. Rings are more favourable than conformations with one single crossing ("figures of eight"), even though DNA is highly constrained. For charged surface, DNA plasmids do feel the surface potential. The repulsion between strands is reduced; twist might be partially traded against writhe. For moderate surface charge densities, we experimentally noticed that crossovers are right-angled. This is strong evidence that electrostatic repulsion at crossings is dominant. On highlycharged surfaces however, we observe plectonemes. The angle at crossings is of the order of 30°. Introducing an extra superhelical turn is more favourable than having torsion within the chain.

More precise consideration of electrostatics effects shows indeed that the surface charges provide some screening and play a similar role to ionic charges in solution. In order to get a better picture of the problem, we need to introduce a few concepts.

At surface carrying µ charges per unit area, DNA chains adopt a flat conformation and are confined within a counter-ion layer whose thickness is characterized by the so-called Gouy-Chapman (GC) length λ from the surface. [START_REF] Adamson | Physical Chemistry of Surfaces[END_REF][START_REF] Andelman | Structure and Dynamics of Membranes[END_REF] .

The effective charge of the plasmid is fixed by the interplay between electrostatic interactions and entropy. In solution, it is rather simple; cations condense on the negatively charged backbone of the plasmids. This counter-ion layer reduces significantly the repulsive electrostatic interaction between charged phosphate groups of DNA chains. On positively charged surfaces, the vicinity of the surface further reduces the electrostatic interaction between DNA charges. Because of the annealed surface charges, since mobile surface charges tend to accumulate under the DNA (Fig. 5), this additional screening is somewhat stronger. At the same time, the electrostatic potential of the surface repels cations condensed on the plasmid. They will be released to a large extent, which will drastically increase their entropy. As a result, the final net charge of the plasmid (condensed cations + DNA) shall be larger than for a plasmid only subjected to counter-ion condensation in solution. 51,[START_REF] Fleck | [END_REF] .

Comparison of conformations with charges at the surface or in volume

To compare the effect of surface charges with the effect of charges in bulk, we have performed a second set of experiments on the zwitterionic DPPC surface with addition of salt in solution. This set of experiments showed, as expected, supercoiled conformations with an increase of the number of nodes when the salt concentration was increased. We present typical conformations in Fig. 6A to 6E, accompanied by histograms of the node numbers (Fig. 6F-J). As already shown by others in the literature, the conformation of supercoiled DNA shows more writhe as the salt concentration of the solution is increased. Adhesion to the substrate was rather weak above 10 mM of salt Hence, plasmids appeared to be whitish on the image Fig. 6D and6E, indicating that they were almost not touching the substrate. We encountered a lot of trouble imaging at 30mM therefore the node number was not counted (Fig. 6J) .

Fig. 6 Effect of salt addition on the adsorption of plasmid DNA onto an uncharged DPPC bilayer. From A to E: 1µm*1µm AFM zooms showing the effect of increasing salt concentration, respectively 0, 1, 5, 10 and 30 mM of NaCl. From F to J: the corresponding statistical analysis of the number of nodes. The number of DNA superturns increases along with the bulk salt concentration, but at the same time the affinity for the surface is reduced and imaging becomes very difficult. The colour scale is the same as on Fig. 3.

From the two sets of experiments that we have performed we can compare the screening effect from charges at the surface and from charges in bulk. We expect to see similar behaviour for surface screening and bulk screening. For a charged object in solution in the vicinity of a membrane, the electrostatic potentials involved are namely the GC potentials V GC for surface screening and the Debye-Hückel (DH) potential V DH for bulk screening. Both potentials are characterized by a single screening length; respectively the GC length λ and the Debye length κ -1 .

The number of nodes n being a direct indicator of the screening efficiency, we plot it as a function of both screening lengths.

µ π λ ⋅ ⋅ = B l e 2 s B C l π κ 8 2 =
with C s the bulk monovalent salt concentration and l B the Bjerrum length.

T k e l B r B ε πε 0 2 4 = 1 -
κ is of the same order of magnitude than λ 55 . However the two potentials (GC and DH) do not have the same dependence with their respective screening length, therefore we will only retain that

λ κ ∝ -1
without any pre estimation of the coefficient of proportionaly.

In order to get λ, one needs beforehand to compute the surface charge density of the bilayers µ. In the moderate screening regime, this surface charge density is proportional to the fraction of cationic lipids within the bilayer f, and inversely proportional to the mean area per lipid head in the bilayer A bilayer . For highly charges surfaces this would not be the case any longer. There would be a greater ionic organization within the GC layer. Counter-ions condensation could also take place until the effective distance between charges matches l B . We did not take this effect into account in our calculation and use only nominal values of µ.

While a surface per lipid head of 64 Å 2 is commonly admitted for a DPPC bilayer as measured by neutron reflectivity 56 , for pure DPTAP and all DPPC/DPTAP mixed bilayers, we have not found any data in the literature. We expect similar behaviour for monolayers and bilayers; therefore we will evaluate the area per lipid head in the bilayer by using the data measured in the monolayer. As specified before (see material and methods), for mixed DPPC-DPTAP monolayers, the mean area per lipid head undergoes non-linear but small variations of less than 10% depending on the DPTAP content. Nonetheless, it is not easy to estimate what would be the area per lipid head in the bilayer. Transfers are usually performed around 30 mN/m. Although for DPPC where both values of the area per molecule are known, the area of the monolayer at this pressure does not correspond to the one of the bilayer. Assuming that the area variation relative to the DPTAP composition is the same within the bilayer than within the monolayer, we estimated the area per lipid in the mixed bilayers. We compared the areas obtained for mixed DPPC-DPTAP monolayers with the pure DPPC monolayers and transposed the variations to bilayers of the same compositions. The surface charge density with respect to the DPTAP proportion was subsequently computed. Results are presented in Table 1. The resulting node numbers as a function of the screening lengths are presented on Fig. For both types of screening, we see that the number of nodes decreases with the screening length. It drops to zero for large screening lengths. We will use the results of ref 51 to analyse our data. This analytical model was developed in the mean field approach. For a plasmid adsorbed in 2D at the surface, the minimization of the total free energy of the plasmids with respect to n shows that the free energy has a linear dependence on n.

| | = -4 + + |∆ |
with L is the contour length of the plasmid, l t is the twist length, F h the free energy of interaction with the surface and F cross is the penalty for crossing helices in 2D. F h can usually be neglected in front of F cross . n and ∆L k . are negative by definition for a plasmid negatively supercoiled. A linear dependence with

λ or κ -1 is hidden in F cross .
Writhing is thus only a question of how we screen the electrostatic penalty for crossing helices in 2D.

The minimum of electrostatic free energy is obtained when the segments are perpendicular to each other as we also witnessed in the experiments for moderate range of screening. We only consider this case in the following:

) 0 ( ~= = q V F cross where ) 0 ( ~= q V
is the FT of the potential taken at the surface.

λ ρ π λ 2 ~3 4 ) 0 ( B GC l q V = =
with ρ λ the linear charge density of DNA in the case of surface screening. The above formula takes into account the fact that in the presence of annealed charges, the GC potential is reduced by a factor of 3 due to lipids mobility. with ρ κ the linear charge density of DNA for bulk screening.

For both types of screening, the intercept of the line should give |∆L k |. As we only have a few data points, in order to minimize the error on the slopes, we used the value of |∆L k | which was independently measured as a starting point of our fits. This data point should be common for surface and bulk screening if one only considers the electrostatic cost. This point at zero screening lengths is only an extrapolation of the mean field regime.

For highly charged surfaces, and high salt concentrations, other types of interactions do play a role (for instance bending).

For surface screening we use only the data points in a moderate range of screening, i.e. where the coupling between counterions is weak.

In practice, the limit occurs between the data points at 15 % (λ=9.45 Å) and 30 % of DPTAP (λ=4.69Å). We plotted the value at 30 % as well as it helps to see a trend. From the all set of data, we only have two points that surely belong to the mean field regime: the points at 10% and 15% of DPTAP. Using, these points, we find a line with a slope S λ =0.35 Å -1 . As expected the data point at 30% DPTAP slightly deviates from the mean field regime. The linear dependence is also cut at low number of nodes when the curve must smoothly goes to zero. From the slope, we can deduce the linear charge density of the plasmid when adsorbed on charged surfaces. We found a value of 1.5 e -per Bjerrum length, which is the effective linear charge density of the plasmid including its cloud of counter-ions. It has been increased by one third as compared to what is usually assumed in salty bulk solutions. This is consistent with the fact that some counter-ions have been released during adsorption. For bulk screening, the number of nodes is also decreasing but less sharply. At large screening length it is nevertheless null. The linear dependence must only be valid for moderate screening lengths, therefore we discarded the points at κ -1 = 96 and κ -1 = 960 Å.

The straight line based on the first three data points has for slope S κ =0.13 Å -1 .

By comparing the slopes S κ and S λ , one obtains the ratio: For a specific node number n, the two DNA segments at crossing must be screened the same way by a DH or by a GC potential, the value of the two interactions (penalty for crossing helices) are thus equal. This suggests that the ratio of effective charges is The linear charge density of DNA appears to be two times smaller for bulk screening than for surface screening, which is compatible with our assumption that DNA has less condensed counter-ions on charged surfaces than in bulk. On DPPC, this gives approximately a DNA effective linear charge density of 0.75 e-per l B which is smaller than what is usually assumed for DNA in salt solutions. It is compatible with the idea that, in order to compensate for the repulsion of plasmids by their own image charge, there is over-condensation of counter-ions, which further reduces the effective linear charge of DNA. On the neutral bilayer (zwitterionic), counter-ion condensation is slightly enhanced while on the charged bilayer, there is counter-ion release. Hence, we experimentally demonstrated that screening from charges at the surface is equivalent to screening from salt in At large Debye screening lengths, i.e. at κ -1 =96Å and κ - 1 =960Å, the analytical model shows huge electrostatic repulsion, (at this distance the electrostatic cost for crossing helices in 2D is above 100 k B T 19 57 ), however, experimentally the distribution of nodes was non-zero. The occurrence of one crossing conformations ("figure of eight") and two crossings was of the order of 20% of the overall plasmid population for κ - 1 =960 Å and above 60% for κ -1 =96Å, which is extremely large considering the energy cost given by the model. We shall expect that counter-ions condensation would have taken place at the crossover, which shall decrease the effective energy cost, but it would not be sufficient to decrease it by one order of magnitude. We postulate that for these two data points, the conformations we have imaged are not fully 2D equilibrated as the model presupposed. Loose writhe might be possible in 3D although in 2D it is energetically not favourable. DNA molecules enduring a rapid transition between 3D and 2D might sometimes trap some writhe during adsorption. We compare it to 3D freezing. This could be the result of a side effect that occurs during the adsorption step. We guess that it has something to do with the existence of a repelling image charge. Plasmids shall stand perpendicular to the surface before adhering, which will increase the probability of forming writhe. This presumed additional "frozen crossing" might shift the average node number by one, but it cannot account for more than one. In this case, distributions shall look slightly asymmetric, which seems indeed to be the case at κ -1 =96Å. When salt is added to the bulk, the repulsion between the plasmid and its image charge is decreased and the proportion of this extra node to the overall population of nodes must be less.

The average node number shall then be more reliable. For charged surfaces, this problem does not exist. Plasmids must already feel the surface potential and stand parallel to the surface before adhering. They have time to equilibrate.

Considering that we have a few numbers of data points available in the valid range of screening lengths where the analytical model does apply, our estimation of the effective charge density of DNA when adsorbed at an interface shall then be truthful, but with a rather large error bare.

Conclusion:

In this article we have presented experiments realized on pUc19 plasmid DNA adsorbed on a bilayer and changed the surface charge density to see its effect on the 2D supercoiled conformation of the DNA. We have been able to reproduce many conformations reported in literature either by AFM or by TEM, just by changing the surface charge. In pure water, the most important energetic cost is the repulsion at crossing which cannot be avoided in 2D. In the absence of electrostatic screening, in bulk or at the surface, the molecule favours open circular conformations, even though it remains very constrained by the linking number. When charges are added at the surface, the mobile lipids reduce the effective charge of the DNA backbone, and supercoiling occurs. It is non-trivial, that the stronger interaction could favour nodes formation. Naively, one would think instead that a greater affinity between plasmids and surface would untighten them. By demonstrating experimentally the equivalence of surface screening and bulk screening we show that electrostatic screening dominates. The presence of mobile charges at the surface does play a very important role. The mobility of the lipids ensures the 2D equilibrium of the molecule but it enhances surface screening as well. As a direct consequence of different counter-ions condensation mechanisms, the effective charge density of plasmids appears to be larger for surface screening than for bulk screening. As a general rule, membranes of other lipid compositions can also be a good substrate to study the dynamics of macromolecules or macromolecules at 2D equilibrium 58 . The similar case of interaction between anionic lipids and cationic biomolecules is also of interest. In the present case, the DNA is negatively charged and the membrane underneath is positively charged. In protein-membrane interactions, both charges are of reversed sign. Cell membranes are negative and objects that bind to them are positive. Nevertheless, electrostatic effects would lead to similar consequences.

a

  Institut Charles Sadron, CNRS UPR 22 et Université de Strasbourg, 23 rue du loess BP 84047 67034 Strasbourg Cedex2, France.

Fig. 1 A

 1 Fig.1 A. Agarose gel electrophoresis (1%) of pUc 19 DNA in presence of chloroquine (2µg/mL). Lane 1: Closed circular pUc19 DNA (Relaxed by nicking and re ligated). Lane 2: open circular (one strand nicked) pUc19 DNA (relaxed by nicking). Lane 3: native supercoiled pUc 19 DNA (initially negatively supercoiled). Fig.1 B: intensity line profile of lane 3.

Fig. 2 A

 2 Fig.2 A to G show 400 x400 nm zooms of representative pUc19 DNA conformations. Plasmids are diluted in miliQ water and adsorbed on bilayers with a controlled surface charge containing a fraction of cationic lipid of 0, 10, 15, 30, 50, 70 and 100 % respectively. On the left, the corresponding normalized histograms of the number of nodes (number of crossings) with Gaussian fit.

.

Fig. 3

 3 Fig.3 AFM image (5µm*5µm) of pUc19 plasmids adsorbed on DPPC in salt free solution. Most of the conformations are open rings although the DNA is not nicked. A small fraction of plasmids over cross strands in a perpendicular manner.

Fig. 4

 4 Fig.4 Open circular (one strand nicked) pUc19 DNA adsorbed on a 50% charged membrane. The DNA is lying open on the surface. There is no apparent crossing of strands in the tertiary structure. Black areas are holes in the bilayer that let appear the mica substrate underneath.

Fig. 5

 5 Fig.5 Sketch of a charged rod adsorbed on an oppositely charged membrane with mobile charges. Drawing bulk counter-ions has been voluntary omitted.

7

 7

Fig. 7

 7 Fig.7Comparison of the efficiency of surface screening and bulk screening. We measured the crossing number as a function of the corresponding screening length in the case of the Gouy-Chapman (black solid circles) and Debye Huckel (red solid squares) theories respectively. As predicted by the analytical model of ref 51, the extrapolation at zero screening length of the mean field regime shall be ∆Lk. We plotted the value measured by electrophoresis (blue triangle).

Table 1

 1 Area per lipid head for pure and mixed monolayers of DPPC /DPTAP measured at 30mN/m. Estimation of the corresponding area in the bilayer of the same composition as compared to pure DPPC where the area in the bilayer was previously measured by Neutron reflectivity. Corresponding computed surface charge density of the bilayer and estimation of the distance between charges. Bold values are measured

	% DPTAP	Amono (Å 2 )	Abilayer (Å 2 )	µ (e .Å -2 )	dcharges (Å)
	0	43	64 (a)	0
	10	41	62.7	0.0016	25
	15	40	62.4	0.0025	20
	30	40	62	0.0048	14
	50	40	62.08	0.0081	11
	70	42	63.3	0.0111	9.5
	100	43	64	0.0156	8

a. As measured in ref

56

  This journal is © The Royal Society of Chemistry 2014 bulk solution. It is only a matter of how many mobile charges are available around the crossing.

	Soft Matter, 2014, 10, 2520-2529

Acknowledgments

The authors thank Albert Johner for fruitful discussions and critical corrections of the manuscript.