Informations

Quelle est l'autre utilisation des graphes de Bruijn en bioinformatique, à l'exception de l'assemblage d'ADN ?

Quelle est l'autre utilisation des graphes de Bruijn en bioinformatique, à l'exception de l'assemblage d'ADN ?


We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

J'ai implémenté mon propre graphe générique de Bruijn, que j'utilise pour l'assemblage d'ADN (alphabet : A, C, G, T). J'essaie de trouver l'utilité du graphe de Bruijn pour un autre problème de bioinformatique, s'il en existe. Je veux utiliser/modifier mon implémentation pour résoudre ce problème. Existe-t-il d'autres problèmes en bioinformatique que nous pouvons résoudre avec les graphes de Bruijn ?

Je n'ai trouvé que l'assemblage d'ARN, qui est similaire à l'assemblage d'ADN.


Assemblage de longues lectures sujettes aux erreurs à l'aide de graphes de Bruijn

Lorsque les longues lectures générées à l'aide de la technologie de séquençage de molécules uniques (SMS) ont été mises à disposition, la plupart des chercheurs étaient sceptiques quant à la capacité des algorithmes existants à générer des assemblages de haute qualité à partir de longues lectures sujettes aux erreurs. Néanmoins, les récentes percées algorithmiques ont abouti à de nombreux projets de séquençage SMS réussis. Cependant, comme l'illustrent les assemblages récents d'importants phytopathogènes, le problème de l'assemblage de longues lectures sujettes aux erreurs est loin d'être résolu même dans le cas de génomes bactériens relativement courts. Nous proposons une approche algorithmique pour assembler de longues lectures sujettes aux erreurs et décrivons l'assembleur ABruijn, ce qui permet des reconstructions précises du génome.


Euler, L. Commentarii Academiae Scientiarum Petropolitanae 8, 128–140 (1741).

Skiena, S. Le manuel de conception d'algorithmes (Springer, Berlin, 2008).

Lander, E. et al. La nature 409, 860–921 (2001).

Venter, J.C. et al. Science 291, 1304–1351 (2001).

Kececioglu, J. & Myers, E. Algorithmique 13, 7–51 (1995).

Adams, M. et al. Science 287, 2185–2195 (2000).

Fleischmann, R. et al. Science 269, 496–512 (1995).

Schatz, M., Delcher, A. & Salzberg, S. Génome Res. 20, 1165–1173 (2010).

Bandeira, N., Pham, V., Pevzner, P., Arnott, D. et Lill, J. Nat. Biotechnologie. 26, 1336–1338 (2008).

Pham, S. & Pevzner, P.A. Bioinformatique 26, 2509–2516 (2010).

Grabherr, M. et al. Nat. Biotechnologie. 29, 644–652 (2011).

de Bruijn, N. Proc. Nederl. Akad. Wetensch. 49, 758–764 (1946).

Idury, R. & Waterman, M. J. Informatique. Biol. 2, 291–306 (1995).

Pevzner, P.A., Tang, H. & Waterman, M. Proc. Natl. Acad. Sci. Etats-Unis 98, 9748–9753 (2001).

Pevzner, P.A., Tang, H. & Tesler, G. Génome Res. 14, 1786–1796 (2004).

Chaisson, M. & Pevzner, P.A. Génome Res. 18, 324–330 (2008).

Zerbino, D. & Birney, E. Génome Res. 18, 821–829 (2008).

Butler, J. et al. Génome Res. 18, 810–820 (2008).

Simpson, J. et al. Génome Res. 19, 1117–1123 (2009).

Li, R. et al. Génome Res. 20, 265–272 (2010).

Paszkiewicz, K. & Studholme, D. Bref. Bio-informer. 11, 457–472 (2010).

Miller, J., Koren, S. et Sutton, G. Génomique 95, 315–327 (2010).

Drmanac, R., Labat, I., Brukner, I. & Crkvenjakov, R. Génomique 4, 114–128 (1989).

Southern, E. Demande de brevet du Royaume-Uni gb8810400 (1988).

Lysov, Y. et al. Doklady Academy Nauk URSS 303, 1508–1511 (1988).

Pevzner, P.A. J. Biomol. Structurer. Dyna. 7, 63–73 (1989).


Graphe de De-Bruijn avec le framework MapReduce vers la classification des données métagénomiques

Les classifications des gènes métagénomiques sont importantes dans la recherche en bioinformatique et en biologie computationnelle. Il existe d'énormes ensembles de données interdépendants qui traitent des caractéristiques humaines, des maladies et des fonctionnalités moléculaires. L'analyse de la réorganisation métagénomique est un problème difficile en raison de leur diversité et de leurs outils de classification efficaces. L'approche MapReducing basée sur des graphes peut facilement gérer la diversité génomique. MapReduce a deux parties telles que la cartographie et la réduction. En phase de cartographie, un algorithme récursif naïf est utilisé pour générer des K-mers. Le graphe de De-Bruijn est une représentation compacte des k-mers et trouve un chemin optimal (solution) pour l'assemblage du génome. Des mesures de similarité ont été utilisées pour trouver une similarité parmi les séquences d'acide désoxyribonucléique (ADN). Du côté réducteur, la similitude Jaccard et la pureté du clustering sont utilisées comme classificateur d'ensembles de données pour classer les séquences en fonction de leur similitude. La phase de réduction peut facilement classer les séquences d'ADN à partir d'une grande base de données. Une analyse expérimentale approfondie a démontré que l'analyse MapReduce basée sur des graphes génère des solutions optimales. Des améliorations remarquables dans le temps et dans l'espace ont été enregistrées et observées. Les résultats ont établi que le cadre proposé fonctionnait plus rapidement que SSMA-SFSD lorsque les éléments classifiés étaient augmentés. Il a fourni une meilleure précision pour le regroupement des données métagénomiques.


Il existe deux types d'algorithmes couramment utilisés par ces assembleurs : les algorithmes gloutonnes, qui visent des optima locaux, et les algorithmes de méthode des graphes, qui visent des optima globaux. Différents assembleurs sont adaptés à des besoins particuliers, tels que l'assemblage de (petits) génomes bactériens, de (grands) génomes eucaryotes ou de transcriptomes.

Assembleurs d'algorithmes gourmands sont des assembleurs qui trouvent des optima locaux dans des alignements de lectures plus petites. Les assembleurs d'algorithmes gourmands comportent généralement plusieurs étapes : 1) calcul de la distance des lectures par paires, 2) regroupement des lectures avec le plus grand chevauchement, 3) assemblage des lectures qui se chevauchent dans des contigs plus grands et 4) répétition. Ces algorithmes ne fonctionnent généralement pas bien pour les ensembles de lecture plus volumineux, car ils n'atteignent pas facilement un optimum global dans l'assemblage et ne fonctionnent pas bien sur les ensembles de lecture qui contiennent des régions de répétition. [1] Les premiers assembleurs de séquences de novo, tels que SEQAID [2] (1984) et CAP [3] (1992), utilisaient des algorithmes gourmands, tels que les algorithmes de chevauchement-disposition-consensus (OLC). Ces algorithmes trouvent un chevauchement entre toutes les lectures, utilisent le chevauchement pour déterminer une disposition (ou une mosaïque) des lectures, puis produisent une séquence de consensus. Certains programmes utilisant des algorithmes OLC comportaient une filtration (pour supprimer les paires de lecture qui ne se chevauchent pas) et des méthodes heuristiques pour augmenter la vitesse des analyses.

Assembleurs de méthodes de graphes [4] se déclinent en deux variétés : string et De Bruijn. Les assembleurs de graphe de cordes et de graphe de De Bruijn ont été introduits lors d'un atelier DIMACS [5] en 1994 par Waterman [6] et Gene Myers. [7] Ces méthodes ont représenté un pas en avant important dans l'assemblage de séquences, car elles utilisent toutes les deux des algorithmes pour atteindre un optimum global au lieu d'un optimum local. Alors que ces deux méthodes ont progressé vers de meilleurs assemblages, la méthode des graphes de De Bruijn est devenue la plus populaire à l'ère du séquençage de nouvelle génération. Lors de l'assemblage du graphe de De Bruijn, les lectures sont divisées en fragments plus petits d'une taille spécifiée, k. Les k-mers sont ensuite utilisés comme nœuds dans l'assemblage du graphe. Les nœuds qui se chevauchent dans une certaine mesure (généralement, k-1) sont ensuite connectés par une arête. L'assembleur construira ensuite des séquences basées sur le graphe de De Bruijn. Les assembleurs de graphes De Bruijn fonctionnent généralement mieux sur des ensembles de lecture plus grands que les assembleurs d'algorithmes gourmands (en particulier lorsqu'ils contiennent des régions de répétition).

Les technologies Auteur Présenté /

Différents assembleurs sont conçus pour différents types de technologies de lecture. Les lectures des technologies de deuxième génération (appelées technologies de lecture courte) comme Illumina sont généralement courtes (avec des longueurs de l'ordre de 50 à 200 paires de bases) et ont des taux d'erreur d'environ 0,5 à 2 %, les erreurs étant principalement des erreurs de substitution. Cependant, les lectures des technologies de troisième génération comme PacBio et les technologies de quatrième génération comme Oxford Nanopore (appelées technologies de lecture longue) sont plus longues avec des longueurs de lecture généralement de plusieurs milliers ou dizaines de milliers et ont des taux d'erreur beaucoup plus élevés d'environ 10-20% avec des erreurs étant principalement des insertions et des suppressions. Cela nécessite des algorithmes d'assemblage différents à partir des technologies de lecture courte et longue.

Il existe de nombreux programmes pour l'assemblage de séquences de novo et beaucoup ont été comparés dans l'Assemblathon. L'Assemblathon est un effort de collaboration périodique pour tester et améliorer les nombreux assembleurs disponibles. À ce jour, deux assemblathons ont été achevés (2011 et 2013) et un troisième est en cours (en avril 2017). Des équipes de chercheurs du monde entier choisissent un programme et assemblent des génomes simulés (Assemblathon 1) et les génomes d'organismes modèles dont ils ont été préalablement assemblés et annotés (Assemblathon 2). Les assemblages sont ensuite comparés et évalués à l'aide de nombreuses métriques.

Assemblathon 1 Modifier

L'Assemblathon 1 [22] a été organisé en 2011 et comprenait 59 assemblées de 17 groupes différents et des organisateurs. L'objectif de cet Assembalthon était d'assembler le plus précisément et complètement un génome composé de deux haplotypes (chacun avec trois chromosomes de 76,3, 18,5 et 17,7 Mb, respectivement) générés à l'aide d'Evolver. De nombreux paramètres ont été utilisés pour évaluer les assemblages, notamment : NG50 (point auquel 50 % de la taille totale du génome est atteint lorsque les longueurs d'échafaudage sont additionnées du plus long au plus court), LG50 (nombre d'échafaudages supérieur ou égal à à, la longueur N50), la couverture du génome et le taux d'erreur de substitution.

  • Logiciels comparés : ABySS, Phusion2, phrap, Velvet, SOAPdenovo, PRICE, ALLPATHS-LG
  • Analyse N50 : les assemblages du Plant Genome Assembly Group (en utilisant l'assembleur Meraculous) et ALLPATHS, Broad Institute, USA (en utilisant ALLPATHS-LG) ont obtenu les meilleurs résultats dans cette catégorie, par un ordre de grandeur par rapport aux autres groupes. Ces assemblages ont marqué un N50 de >8 000 000 de bases.
  • Couverture du génome par assemblage : pour cette métrique, l'assemblage de BGI via SOAPdenovo a donné les meilleurs résultats, avec 98,8 % du génome total couvert. Tous les assembleurs se sont relativement bien comportés dans cette catégorie, tous les groupes sauf trois ayant une couverture de 90 % et plus, et la couverture totale la plus faible étant de 78,5 % (Dept. of Comp. Sci., University of Chicago, USA via Kiki).
  • Erreurs de substitution : l'assemblage avec le taux d'erreur de substitution le plus bas a été soumis par l'équipe du Wellcome Trust Sanger Institute, Royaume-Uni à l'aide du logiciel SGA.
  • Dans l'ensemble : aucun assembleur n'a obtenu de meilleurs résultats que les autres dans toutes les catégories. Alors que certains assembleurs ont excellé dans une catégorie, ils ne l'ont pas fait dans d'autres, ce qui suggère qu'il y a encore beaucoup de place pour l'amélioration de la qualité du logiciel assembleur.

Assemblathon 2 Modifier

Assemblathon 2 [23] a amélioré l'Assemblathon 1 en incorporant les génomes de plusieurs vertébrés (un oiseau (Melopsittacus undulatus), un poisson (Zèbre de Maylandia), et un serpent (Boa constricteur constricteur)) avec des génomes estimés à 1,2, 1,0 et 1,6 Gbp de longueur) et une évaluation par plus de 100 métriques. Chaque équipe a eu quatre mois pour assembler son génome à partir des données de séquence de nouvelle génération (NGS), y compris les données de séquence Illumina et Roche 454.

  • Logiciels comparés : ABySS, ALLPATHS-LG, PRICE, Ray et SOAPdenovo
  • Analyse N50 : pour l'assemblage du génome de l'oiseau, les équipes du Baylor College of Medicine Human Genome Sequencing Center et ALLPATHS ont obtenu les NG50 les plus élevés, à plus de 16 000 000 et plus de 14 000 000 pb, respectivement.
  • Présence de gènes de base : la plupart des assemblages se sont bien comportés dans cette catégorie (


Structure de marquage supplémentaire pour la traversée du graphique

De nombreuses applications NGS, par ex. de novo assemblage de génomes [15] et de transcriptomes [2], et de novo détection de variantes [6], reposent sur (i) la simplification et (ii) la traversée du graphe de de Bruijn. Cependant, le graphe tel que représenté dans la section précédente ne supporte ni (i) les simplifications (car il est immuable) ni (ii) les traversées (car le filtre de Bloom ne peut pas stocker un bit visité supplémentaire par nœud). Pour résoudre le premier problème, nous soutenons que l'étape de simplification peut être évitée en concevant une procédure de parcours légèrement plus complexe [16].

Nous introduisons un nouveau mécanisme léger pour enregistrer les portions du graphe qui ont déjà été visitées. L'idée derrière ce mécanisme est que tous les nœuds n'ont pas besoin d'être marqués. Plus précisément, les nœuds qui se trouvent à l'intérieur de chemins simples (c'est-à-dire les nœuds ayant un degré d'entrée de 1 et un degré de sortie de 1) seront tous marqués ou tous non marqués. Nous ferons référence aux nœuds ayant leur degré d'entrée ou de sortie différent de 1 comme complexe nœuds. Nous proposons de stocker les informations de marquage des nœuds complexes, en stockant explicitement les nœuds complexes dans une table de hachage séparée. Dans les graphes de génomes de Bruijn, l'ensemble complet de nœuds éclipse l'ensemble de nœuds complexes, cependant le rapport dépend de la complexité du génome [17]. L'utilisation de la mémoire de la structure de marquage est mcC, où mc est le nombre de nœuds complexes dans le graphe et C est l'utilisation de la mémoire de chaque entrée dans la table de hachage (C≈2k+8).


Biologie de la taille des octets

J'ai récemment postulé pour une bourse de la Fondation Moore en Data Science pour les sciences biologiques. Dans le cadre de la pré-candidature, il m'a été demandé de choisir les 5 meilleurs travaux en data science dans mon domaine. Pas si sûr de la science des données, j'ai donc choisi ce que je pense être les travaux les plus influents en bioinformatique, c'est sur quoi portait ma proposition. Quoi qu'il en soit, le choix a été difficile, et j'ai proposé ce qui suit. L'ordre dans lequel j'énumère les œuvres est chronologique, car je n'essaie pas de les classer. Si vous me demandez dans les commentaires “Comment pouvez-vous choisir X sur Y ?” ma réponse serait probablement : “I did’t”.

Dayhoff, M.O., Eck RV et Eck CM. 1972. Un modèle de changement évolutif dans les protéines. Pp. 89-99 dans Atlas de la séquence et de la structure des protéines, vol. 5, Fondation nationale de la recherche biomédicale, Washington DC

Résumé : il s'agit de l'introduction de la matrice PAM, l'article qui a ouvert la voie à notre compréhension de l'évolution moléculaire au niveau des protéines, de l'alignement des séquences et du BLASTing que nous faisons tous. La question posée : comment quantifier les changements entre séquences protéiques ? Comment pouvons-nous développer un système qui nous indique, au fil du temps, la façon dont les protéines évoluent ? Dayhoff a développé une méthode statistique élégante pour ce faire, qu'elle a nommée PAM, “Accepted Point Mutations”. Elle a aligné des centaines de protéines et calculé la fréquence à laquelle les différents acides aminés se substituent les uns aux autres. Dayhoff a introduit une version plus robuste [PDF] en 1978, une fois que le nombre de protéines qu'elle pouvait utiliser a été augmenté pour qu'elle puisse compter un grand nombre de substitutions.

Altschul, S.F., Madden, T.L., Schaffer, A.A., Zhang, J., Zhang, Z., Miller, W. & Lipman, D.J. (1997) Gapped BLAST et PSI-BLAST : une nouvelle génération de programmes de recherche de bases de données de protéines. Acides nucléiques Res. 25:3389-3402.

BLAST, l'outil de recherche d'alignement local de base est l'outil informatique de référence en biologie moléculaire. C'est l'article le plus cité en sciences de la vie, donc probablement l'article le plus influent en biologie aujourd'hui. Pour les non-initiés : BLAST permet de prendre une séquence de protéine ou d'ADN, et de rechercher rapidement des séquences similaires dans une base de données contenant des millions. La recherche à l'aide d'une séquence prend quelques secondes, voire quelques minutes au mieux. BLAST a en fait été introduit dans un autre article en 1990. Cependant, les heuristiques développées ici ont permis l'alignement des séquences avec intervalle et la recherche de séquences moins similaires, avec une robustesse statistique. BLAST a tout changé en biologie moléculaire et a déplacé la biologie vers les sciences riches en données. S'il y a jamais eu un cas pour donner le prix Nobel de physiologie ou de médecine à une personne informatique, c'est BLAST.

Durbin R., Eddy S., Krogh A et Mitchison G Analyse de séquence biologique : modèles probabilistes de protéines et d'acides nucléiques Cambridge University Press 1998

La sollicitation de la Fondation Moore demandait des “works” plutôt que de simples “research papers”. S'il y a quelque chose de commun à tous les laboratoires de bioinformatique, c'est bien ce livre. Un aperçu des méthodes d'analyse de séquence de base. Ce livre résume les fondements d'avant 2000 sur lesquels presque toutes nos connaissances sont actuellement construites : alignement par paires, modèles de Markov, alignement de séquences multiples, profils, PSSM et phylogénétique.

Gene Ontology : outil d'unification de la biologie. Le consortium d'ontologie génétique (2000) Génétique de la nature 25: 25-29

Pas un document de recherche, et pas un livre, mais un “commentaire”. Ce travail a popularisé l'utilisation d'ontologies en bioinformatique et a cimenté GO comme l'ontologie principale que nous utilisons.

Pevzner PA, Tang H, Waterman MS. Une approche par voie eulérienne pour l'assemblage de fragments d'ADN. Proc Natl Acad Sci États-Unis. 2001 août 1498 (17) : 9748-53.

Assemblage de séquences à l'aide de graphes de de-Bruijn, rendant l'assemblage traitable pour un grand nombre de séquences. A l'époque, les séquences shotgun produites par le séquençage de Sanger pouvaient encore être assemblées en un temps fini en résolvant un chemin hamiltonien. Une fois que les données de séquençage de nouvelle génération ont commencé à affluer, l'utilisation de graphes de De-Bruijn et d'un chemin eulérien est devenue essentielle. Pour une bonne explication de la transition méthodologique, voir cet article dans Biotechnologie Natureoui

Oui, je sais qu'il y a beaucoup d'œuvres méritantes qui ne sont pas ici. Lorsqu'on se résume à cinq, le choix est presque arbitraire. Si vous vous sentez offensé qu'un travail que vous aimez ne soit pas ici, alors je suis désolé.


Graphique de de Bruijn compressé

Étant donné une chaîne S de longueur m et un nombre naturel k, le graphique de Bruijn de S contient un nœud pour chaque longueur distincte k sous-chaîne de S, appelé un k-mer. Deux nœuds vous et v sont reliés par une arête dirigée (vous, v) si vous et v se produire consécutivement dans S, c'est-à-dire (u = S[i..i+k-1]) et (v = S[i+1..i+k]) . La figure 1 montre un exemple. De toute évidence, le graphique contient au plus m nœuds et m bords. Par construction, les nœuds adjacents se chevaucheront de (k-1) caractères, et le graphe peut inclure plusieurs des arêtes reliant la même paire de nœuds ou d'auto-boucles représentant des répétitions qui se chevauchent. Pour chaque nœud, à l'exception du nœud de départ (contenant le premier k personnages de S) et le nœud d'arrêt (contenant le dernier k personnages de S), le degré d'entrée coïncide avec le degré de sortie. Un graphe de Bruijn peut être « compressé » en fusionnant des chaînes de nœuds non ramifiés en un seul nœud avec une chaîne plus longue. Plus précisément, si le nœud vous est le seul prédécesseur de node v et v est le seul successeur de vous (mais il peut y avoir plusieurs bords (vous, v)), alors vous et v peut être fusionné en un seul nœud qui a les prédécesseurs de vous et les successeurs de v. Après avoir compressé au maximum le graphe, chaque nœud (à part éventuellement le nœud de départ) a au moins deux prédécesseurs différents ou son unique prédécesseur a au moins deux successeurs différents et chaque nœud (à part le nœud d'arrêt) a au moins deux successeurs différents ou son un seul successeur a au moins deux prédécesseurs différents voir Fig. 1. Bien sûr, le graphe de Bruijn compressé peut être construit à partir de son homologue non compressé (un graphe beaucoup plus grand), mais cela est désavantageux en raison de l'énorme consommation d'espace. C'est pourquoi nous allons le construire directement.

Représentation explicite du graphe de Bruijn compressé de la Fig. 1

La figure 2 montre comment splitMEM représente le graphique de Bruijn compressé g pour (k=3) et la chaîne (S=) ACTACGTACGTACG$. Chaque nœud correspond à une sous-chaîne (omega ) de S et se compose des composants (identifiant, longueur, posListe, adjListe), où identifiant est un nombre naturel qui identifie de manière unique le nœud, longueur est la longueur (|omega |) de (omega ) , posListe est la liste des positions auxquelles (omega ) apparaît dans S (classés par ordre croissant), et adjListe est la liste des successeurs du nœud (triés de telle sorte que le parcours g ça donne S est induite par les listes d'adjacence : si nœud g[identifiant] est visité pour le je-ième fois, alors son successeur est le nœud qui peut être trouvé à la position je dans la liste de contiguïté de g[identifiant]).

Les nœuds du graphe de Bruijn compressé d'un pan-génome peuvent être classés comme suit :

Un uniqueNode représente une sous-chaîne unique dans le pan-génome et a une seule position de départ (c'est-à-dire, posListe contient un seul élément)

Un repeatNode représente une sous-chaîne qui apparaît au moins deux fois dans le pan-génome, soit en tant que répétition dans un seul génome, soit en tant que segment partagé par plusieurs génomes.

Dans l'analyse pangénomique, S est la concaténation de plusieurs séquences génomiques, où les différentes séquences sont séparées par un symbole spécial (#) . (En théorie, on pourrait utiliser des symboles différents par paires pour séparer les séquences, mais en pratique, cela ferait exploser l'alphabet.) Cela a pour effet que (#) peut faire partie d'une répétition. Contrairement à splitMEM, notre algorithme traite les différentes occurrences de (#) comme s'il s'agissait de caractères différents. Par conséquent, (#) ne fera pas partie d'une répétition. Dans notre approche, chaque occurrence de (#) sera la fin d'un nœud d'arrêt (c'est-à-dire qu'il y a un nœud d'arrêt pour chaque séquence).

Selon [5], le graphe de Bruijn compressé est le plus approprié pour l'analyse du pan-génome : identifiables, ainsi que le contexte des séquences flanquantes. Cette stratégie permet également une analyse topologique puissante du pan-génome impossible à partir d'une représentation linéaire. Il a cependant un défaut : il n'est pas possible de rechercher efficacement certains nœuds puis d'explorer le graphe au voisinage de ces nœuds. Un utilisateur peut, par exemple, vouloir rechercher un certain allèle dans le pan-génome et, s'il est présent, examiner le voisinage de cet allèle dans le graphique. Ici, nous proposons une nouvelle représentation spatialement efficace du graphe de Bruijn compressé qui ajoute exactement cette fonctionnalité.

Nous stockons le graphique dans un tableau g de longueur N, où N est le nombre de nœuds dans le graphe de Bruijn compressé. De plus, nous attribuons à chaque nœud un identifiant unique (id in <1,dots ,N>) . Un nœud g[identifiant] a maintenant la forme ((len,lb,size,< suffix>\_lb)) , où

La variable longueur est la longueur de la chaîne (omega = S[mathsf [lb]..mathsf [lb]+len-1]) qui correspond au nœud avec identifiant identifiant

([lb..lb+size-1]) est l'intervalle (omega ) , kg est sa limite gauche, et Taille est sa taille

([< suffix>\_lb..< suffix>\_lb+size-1]) est l'intervalle du k suffixe de longueur de (omega )

Il y a cependant une exception : la sentinelle $ et chaque occurrence du séparateur (#) sera la fin d'un nœud d'arrêt. Clairement, le suffixe $ de S apparaît à l'index 1 dans le tableau des suffixes car $ est le plus petit caractère de l'alphabet. L'intervalle du tableau de suffixes de $ est [1..1], nous définissons donc (< suffix>\_lb= 1) . De manière analogue, un suffixe de S qui commence par (#) apparaît à un index (j in <2,dots ,d>) dans le tableau de suffixes (où (d) est le nombre de séquences dans S) car (#) est le deuxième plus petit caractère de l'alphabet, nous définissons donc (< suffix>\_lb= j) .

Représentation implicite du graphe de Bruijn compressé de la Fig. 1

La figure 3 montre un exemple. Dorénavant, cette représentation sera appelée représentation implicite, tandis que la représentation de la figure 2 sera appelée représentation explicite. Il est clair que dans la représentation implicite la liste de toutes les positions auxquelles (omega ) apparaît dans S peut être calculé comme suit : ([mathsf [i] mid lb le i le lb+taille-1]) . Il sera expliqué plus loin, comment le graphe peut être parcouru et comment un motif peut être recherché. Nous verrons que cela peut être fait efficacement au moyen du quatrième composant (< suffix>\_lb) .


Quelle est l'autre utilisation des graphes de Bruijn en bioinformatique, à l'exception de l'assemblage d'ADN ? - La biologie

Bioinformatique, 32, 2016, i201–i208 doi : 10.1093/bioinformatique/btw279 ISMB 2016

Compactage rapide et en faible mémoire de graphes de Bruijn à partir de données de séquençage Rayan Chikhi1,*, Antoine Limasset2 et Paul Medvedev3,4,5 1

CNRS, CRIStAL, Lille, France, 2ENS Cachan Brittany, Bruz, France, 3Department of Computer Science and Engineering, The Pennsylvania State University, USA, 4Department of Biochemistry and Molecular Biology, The Pennsylvania State University, USA et 5Genome Sciences Institute of the Huck , The Pennsylvania State University, États-Unis *À qui la correspondance doit être adressée.

Motivation abstraite : À mesure que la quantité de données par expérience de séquençage augmente, les défis de l'assemblage de fragments deviennent de plus en plus informatiques. Le graphe de Bruijn est une structure de données largement utilisée dans les algorithmes d'assemblage de fragments, utilisée pour représenter les informations d'un ensemble de lectures. Le compactage est une étape importante de réduction des données dans la plupart des algorithmes basés sur des graphes de Bruijn où de longs chemins simples sont compactés en des sommets uniques. Le compactage est récemment devenu le goulot d'étranglement des pipelines d'assemblage, et l'amélioration de son temps d'exécution et de son utilisation de la mémoire est un problème important. Résultats : Nous présentons un algorithme et un outil BCALM 2 pour le compactage de graphes de de Bruijn. BCALM 2 est un algorithme parallèle qui distribue l'entrée sur la base d'une technique de hachage de minimiseur, permettant un bon équilibre de l'utilisation de la mémoire tout au long de son exécution. Pour les données de séquençage humain, BCALM 2 réduit la charge de calcul du compactage du graphique de Bruijn à environ une heure et 3 Go de mémoire. Nous avons également appliqué BCALM 2 aux ensembles de données de séquençage de 22 Gbp de pin à encens et de 20 Gbp d'épinette blanche. Les graphiques compactés ont été construits à partir de lectures brutes en moins de 2 jours et 40 Go de mémoire sur une seule machine. Par conséquent, BCALM 2 est au moins un ordre de grandeur plus efficace que les autres méthodes disponibles. Disponibilité et mise en œuvre : le code source de BCALM 2 est disponible gratuitement sur : https://github.com/GATB/bcalm Contact : [email protected]

1 Introduction La technologie de séquençage moderne peut générer des milliards de lectures à partir d'un échantillon, qu'il s'agisse d'ARN, d'ADN génomique ou d'un métagénome. Dans certaines applications, un génome de référence peut permettre la cartographie de ces lectures, mais dans de nombreuses autres, le but est de reconstruire de longs contigs. Ce problème est connu sous le nom d'assemblage de fragments et continue d'être l'un des défis les plus importants en bioinformatique. L'assemblage de fragments est le composant algorithmique central derrière l'assemblage de nouveaux génomes, la détection de transcrits de gènes (ARN-seq) (Grabherr et al., 2011), la découverte d'espèces à partir de métagénomes, l'appel de variantes structurelles (Iqbal et al., 2012). L'amélioration continue des technologies de séquençage et l'augmentation de la quantité de données produites par expérience représentent un sérieux défi pour les algorithmes d'assemblage fragmentés. Par exemple, s'il existe de nombreux assembleurs de génomes capables d'assembler des génomes de taille bactérienne, le nombre d'assembleurs pouvant assembler un génome de mammifère de haute qualité est limité, la plupart d'entre eux étant développés par de grandes équipes et nécessitant des ressources importantes (Gnerre C L'Auteur 2016 Publié par Oxford University Press. V

et al., 2011 Luo et al., 2012 Simpson et al., 2009). Pour des génomes encore plus gros, tels que le Picea glauca (épinette blanche) de 20 Gbp, la construction et le compactage de graphes ont nécessité 4,3 To de mémoire, 38 h et 1 380 cœurs de processeur (Birol et al., 2013). Dans un autre cas, l'ensemble du génome de 22 Gbp Pinus taeda (pin à encens) nécessitait 800 Go de mémoire et trois mois d'autonomie sur une seule machine (Zimin et al., 2014). La plupart des algorithmes d'assemblage de fragments à lecture courte utilisent le graphe de Bruijn pour représenter les informations d'un ensemble de lectures. Étant donné un ensemble de lectures R, chaque k-mer distinct dans R forme un sommet du graphe, tandis qu'une arête relie deux k-mers s'ils se chevauchent de k – 1 caractères. L'utilisation du graphe de de Bruijn dans l'assemblage de fragments consiste en un pipeline à plusieurs étapes, cependant, les étapes les plus gourmandes en données sont généralement les trois premières : énumération des nœuds, compactage et nettoyage du graphe. Dans la première étape (parfois appelée comptage k-mer), l'ensemble des k-mers distincts est extrait des lectures. Dans la deuxième étape, tous les unitigs (chemins avec tout sauf le premier sommet ayant un degré d'entrée 1 et tous sauf le dernier sommet ayant un degré de sortie 1) sont compactés en un seul i201

Il s'agit d'un article en libre accès distribué sous les termes de la licence Creative Commons Attribution Non-Commercial (http://creativecommons.org/licenses/by-nc/4.0/), qui permet la réutilisation, la distribution et reproduction sur quelque support que ce soit, à condition que l'œuvre originale soit correctement citée. Pour une réutilisation commerciale, veuillez contacter [email protected]

sommet i202. Dans la troisième étape, les artefacts dus aux erreurs de séquençage et au polymorphisme sont supprimés du graphe. La deuxième et la troisième étape sont parfois alternées pour compacter davantage le graphe. Après ces étapes initiales, la taille des données est réduite progressivement, par ex. pour un ensemble de données humaines avec une couverture de 45, Pour surmonter les défis d'évolutivité de l'assemblage de fragments de grands ensembles de données de séquençage, l'accent a été mis sur l'amélioration de l'utilisation des ressources de la construction de graphes de de Bruijn. En particulier, le comptage k-mer a vu des améliorations de plusieurs ordres de grandeur dans l'utilisation de la mémoire et la vitesse. En conséquence, le compactage des graphes devient le nouveau goulot d'étranglement, mais il a reçu peu d'attention (Kundeti et al., 2010). Récemment, nous avons développé un outil de compactage qui utilise peu de mémoire, mais sans amélioration du temps (Chikhi et al., 2014). D'autres approches parallèles de compactage ont été proposées, dans le cadre d'assembleurs de génomes. Cependant, la plupart ne sont implémentés que dans le contexte d'un assembleur spécifique et ne peuvent pas être utilisés comme modules pour la construction d'autres assembleurs de fragments ou pour d'autres applications des graphes de Bruijn (par exemple la métagénomique). Dans cet article, nous présentons un algorithme rapide et à faible mémoire pour le compactage de graphes. Notre algorithme se compose de trois étapes : une distribution minutieuse des k-mers d'entrée dans des seaux, un compactage parallèle des seaux et une étape de réunification parallèle pour coller ensemble les chaînes compactées en unitigs. L'algorithme s'appuie sur l'utilisation de minimiseurs pour partitionner le graphe (Chikhi et al., 2014), cependant, la stratégie de partitionnement est complètement nouvelle puisque la stratégie de Chikhi et al. (2014) ne se prête pas à la parallélisation. En raison de la complexité de l'algorithme, nous prouvons formellement son exactitude. Nous l'évaluons ensuite sur des données de séquençage du génome entier humain, du pin et de l'épicéa. Le graphique de de Bruijn pour l'ensemble de données du génome humain est compacté en environ une heure et 3 Go de mémoire en utilisant 16 cœurs. Pour les génomes de pin et d'épinette > 20 Gbp, le comptage k-mer et le compactage graphique ne prennent que 2 jours et 40 Go de mémoire, améliorant d'au moins un ordre de grandeur les résultats précédemment publiés.

2 Travaux connexes La parallélisation du compactage de graphes de de Bruijn a déjà été explorée. Dans (Jackson et al., 2010 Kundeti et al., 2010), le problème est réduit au problème classique de classement de liste et résolu en utilisant des techniques parallèles telles que le saut de pointeur. Une autre approche récurrente basée sur MPI consiste à implémenter une table de hachage distribuée, où les k-mers et les informations sur leurs voisinages sont distribués entre les processus. Chaque processeur étend ensuite les semences k-mers localement aussi loin que possible pour créer des sous-unités, puis les transmet à d'autres processeurs pour une extension ultérieure. Des variantes de cette approche sont utilisées dans (Georganas et al., 2014 Liu et al., 2011 Simpson et al., 2009). D'autres articles ont proposé d'utiliser une recherche parallélisée en profondeur d'abord (Zeng et al., 2013) ou un modèle parallèle asynchrone du petit monde (Meng et al., 2014, 2012). Avant qu'un graphe de de Bruijn puisse être compacté, il doit être construit. Les approches parallèles représentent actuellement l'état de l'art dans ce domaine. De nombreux efforts originaux ont été concentrés sur les graphes de Bruijn centrés sur les arêtes, où les arêtes sont représentées par ðk þ 1Þ-mers. Ils nécessitaient l'identification à la fois de tous les k-mers distincts et des ðk þ 1Þmers (Jackson et Aluru, 2008 Jackson et al., 2010 Kundeti et al., 2010 Lu et al., 2013 Zeng et al., 2013). Des efforts plus récents se sont concentrés sur le graphe node-centric, qui ne nécessite que le comptage des k-mers (Deorowicz et al., 2014 Li et al., 2013 Lu et al., 2013 Marc¸ais et Kingsford, 2011 Melsted et Pritchard , 2011 Rizk et coll., 2013 Simpson et coll., 2009).

R. Chikhi et al. Dans l'assemblage du génome, la construction et le compactage d'un graphe de de Bruijn ne forment que les étapes initiales. Il existe également des approches alternatives qui n'utilisent pas du tout le graphe de de Bruijn (par exemple, le graphe glouton ou à cordes). Numerous parallel assemblers are available for use, including ABySS (Simpson et al., 2009), SOAPdenovo (Luo et al., 2012), Ray (Boisvert et al., 2010), PASQUAL (Liu et al., 2013), PASHA (Liu et al., 2011), SAND (Moretti et al., 2012), SWAPAssembler (Meng et al., 2014). Other methods for parallel assembly have been published but without publicly available software (Duan et al., 2014 Garg et al., 2013 Georganas et al., 2015 Jackson et al., 2010). There has also been work done in reducing the overall memory footprint de Bruijn graph assembly. This challenge is most pronounced for k-mer counters. However, when scaling to mammaliansized genomes, memory usage continues to be an issue in downstream steps such as compaction. Chikhi et al. (2014) used minimizers to compact the de Bruijn graph of a human whole-genome dataset in under 50 MB of memory, but the algorithm did not improve the running time. Wu et al. (2012) propose an approach based on dividing the assembly problem into mutually independent instances. Ye et al. (2012) exploit the notion of graph sparseness for reducing memory use. Kleftogiannis et al. (2013) perform a comparative analysis and propose several memory-reducing strategies. Chikhi and Rizk (2012) use Bloom filters to reduce memory usage. Movahedi et al. (2012) propose a divide-and-conquer approach for compacting a de Bruijn graph.

3 Definitions We assume, for the purposes of this paper, that all strings are over the alphabet R ¼ fA C G Tg. A string of length k is called a k-mer. For a string s, we define its k-spectrum, spk ðsÞ, as the multi-set of all k-mer substrings of s. For a set of strings S, we define its multi-set k-spectrum as spk ðSÞ ¼ [s2S spk ðsÞ. For two strings u and v, we write u 2 v to mean that u is a substring of v. We write u½i::j to denote the substring of u from the ith to the jth character, inclusive. We define sufk ðuÞ ¼ u½juj k þ 1 juj and prek ðuÞ ¼ u½1::k . For two strings u and v such that sufk ðuÞ ¼ prek ðuÞ, we define a glue operation as u k v ¼ u v½k þ 1::jvj . The binary relation u ! v between two strings denotes that sufk 1 ðuÞ ¼ prek 1 ðvÞ. For a set of k-mers K, the de Bruijn graph of K is a directed graph such that the nodes are exactly the k-mers in K and the edges are given by the ! relation. Note that our definition of the de Bruijn graph is node-centric, where the edges are implicit given the vertices therefore, we use the terms de Bruijn graph and a set of k-mers interchangeably. Suppose we are given a de Bruijn graph, represented by a set of k-mers K. Consider a path p ¼ ðx1 . . . xm Þ over m 1 vertices. We allow the path to be a cycle, i.e. it is possible that x1 ¼ xm . The endpoints of a path are x1 and xm if it is not a cycle. A single-vertex path has one endpoint. A cycle does not have endpoints. The internal vertices of a path are vertices that are not endpoints. p is said to be a unitig if either jpj ¼ 1 or for all 1 ‘ and a string x with at least k characters, we define lmmðxÞ as the ‘-minimizer of the prefix ðk 1Þ-mer, and rmmðxÞ as the ‘-minimizer of the suffix ðk 1Þ-mer. We refer to these as the left and right minimizers of x, respectively. Two strings (u, v) are m-compactable in S if they are compactable in S and if m ¼ rmmðuÞ ¼ lmmðvÞ. The m-compaction of a set S is obtained from S by applying the compaction operation as much as possible in any order to all pairs of strings that are m-compactable in S.

4 Algorithm overview In this section, we give a high-level description of our BCALM 2 algorithm (Algorithm 1), leaving important optimizations and implementation details to Section 6. Recall that the input is a set of k-mers K and the output are the strings corresponding to all the maximal unitigs of the de Bruijn graph of K. If time and memory are not an issue, then there is a trivial algorithm: repeatedly find compactable strings and compact them until no further compactions are possible. However, such an approach requires loading all the data into memory, which is not feasible for larger genomes. Instead, BCALM 2 proceeds in three stages. In the first stage, the k-mers are distributed into buckets, with some k-mers being thrown into two buckets. In the second stage, each bucket is compacted, separately. In the third stage, the k-mers that were thrown into two buckets are glued back together so that duplicates are removed. Figure 1 shows the execution of BCALM 2 on a small example.

Input: the set of k-mers K. 1: for all parallel x 2 K do 2: Write x to FðlmmðxÞÞ. 3: if lmmðxÞ 6¼ rmmðxÞ then 4: Write x to FðrmmðxÞÞ. 5: for all parallel i 2 f1 . . . 4‘ g do 6: Run CompactBucket(i) 7: ReuniteðÞ

In the second stage of the algorithm, we process each bucket file using the CompactBucket procedure (Algorithm 2). After the k-mer distribution of the first stage, the bucket file F(i) contains all the k-mers whose left or right minimizer is i. We can therefore load F(i) into memory and perform i-compaction on it. Since the size of the bucket is small, this compaction can be performed using a simple inmemory algorithm. The resulting strings are then written to disk, and will be processed during the third stage. At the end of the second stage, when all CompactBucket procedures are finished, we have performed all the necessary compactions on the data. At this stage of the algorithm, notice that the k-mers x 2 K with lmmðxÞ 6¼ rmmðxÞ exist in two copies. We call such k-mers doubled. We will prove in Section 5 that these k-mers are always at the ends (prefix or suffix) of the compacted strings, never internal, and they can be recognized by the fact that the minimizer at that end does not correspond to the bucket where it resides. We record these ends that have doubled k-mers by marking them ‘lonely’ (lines 4 and 5 of Algorithm 2), since they will need to be ‘reunited’ at the third stage of the algorithm. Strings that have no lonely ends are maximal unitigs, therefore they are output (line 8).

Algorithm 3. Reunite() Input: the set of strings R from the Reunite file. 1: UF Union find data structure whose elements are the distinct k-mer extremities in R. 2: for all parallel u 2 R do 3: if both ends of u are lonely then 4: UF:unionðsufk ðuÞ prek ðuÞÞ 5: for all parallel classes C of UF do 6: P all u 2 R that have a lonely extremity in C 7: while 9u 2 P that does not have a lonely prefix do 8: Remove u from P 9: Let s ¼ u 10: while 9 v 2 P such that sufk ðsÞ ¼ prek ðvÞ do 11: s Glueðs vÞ 12: Remove v from P 13: Output s

Algorithm 4. Glue(u, v) In the first stage (lines 1–6 of Algorithm 1), BCALM 2 distributes the k-mers of K to files Fð1Þ . . . Fð4‘ Þ. These are called bucket files. Each k-mer x 2 K goes into file FðlmmðxÞÞ, and if lmmðxÞ 6¼ rmmðxÞ, also in FðrmmðxÞÞ. The parameter ‘ controls the minimizer size (in our implementation, we set ‘ ¼ 8). Algorithm 2. CompactBucket(i) 1: Load F(i) into memory. 2: U i-compaction of F(i). 3: for all strings u 2 U do 4: Mark u’s prefix as “lonely” if i 6¼ lmmðuÞ. 5: Mark u’s suffix as “lonely” if i 6¼ rmmðuÞ. 6: if u’s prefix and suffix are not lonely then 7: Output u. 8: else 9: Place u in the Reunite file

Input: strings u and v, such that sufk ðuÞ ¼ prek ðvÞ. 1: Let w ¼ u k v. 2: Set lonely prefix bit of w to be the lonely prefix bit of u. 3: Set lonely suffix bit of w to be the lonely suffix bit of v. 4: return w

At the third stage of the algorithm, we process the strings output by CompactBucket with the Reunite procedure (Algorithm 3). At a high level, the purpose of Reunite is to process each string u that has a lonely end, and find a corresponding string v that has a matching lonely end with the same k-mer. When one is found, then u and v are glued together (Algorithm 4), thereby ‘reuniting’ the doubled k-mer that was split in the k-mer distribution stage. The new string inherits its end lonely marks from the glued strings, and the process is then repeated for the next string u that has a lonely end. After Reunite() completes, all duplicate k-mers will have been removed, and the strings in the output will correspond to the maximal unitigs.

Fig. 1. Execution of BCALM 2 on a small example, with k ¼ 4 and ‘ ¼ 2. On the top left, we show the input de Bruijn graph. The maximal unitigs correspond to the path from CCCT to TCTA (spelling CCCTCTA), and to the k-mers CCCC, CCCA, CTAC, CTAA. In this example, minimizers are defined using a lexicographic ordering of ‘-mers. In the top right, we show the contents of the bucket files. Only five of the bucket files are non-empty, corresponding to the minimizers CC, CT, AA, AC and CA. The doubled k-mers are italicized. Below that, we show the set of strings that each i-compaction generates. For example in the bucket CC, the k-mers CCCT and CCTC are compacted into CCCTC, however CCCC and CCCT are not compactable because CCCA is another out-neighbor of CCCC. The lonely ends are denoted by •. In the bottom half we show the execution steps of the Reunite algorithm. Nodes in bold are output

To perform these operations efficiently in time and memory, Reunite first partitions the strings of R so that any two strings that need to be reunited are guaranteed to be in the partition. Then, each partition can be processed independently. To achieve the partition, we use a union-find (UF) data structure of all k-mers extremities. Recall that a UF data structure is created by first assigning a set to each distinct element (here, an element is the k-mer extremity of a string). Then, the union operation replaces the sets of two elements by a single set corresponding to their union. Here, union is applied to both k-mer extremities of a string. After the UF is constructed, the set of strings to be reunited is partitioned such that k-mer extremities of sequences in a partition all belong to the same UF set.

besides at t½p k þ 1 p . Since there are no duplicate k-mers in T, this is a contradiction. Now, we show that S T. Let s 2 S and let t 2 T such that s 2 t. By applying an argument symmetrical to the one above, there exists a s0 2 S such that t 2 s0 . This means that s 2 s0 , and, in particular, s½1::k 2 s0 . Since k-mers can only appear once in S, we must have that s ¼ s0 and hence s ¼ t 2 T. h Next, we characterize the k and k þ 1 spectrums of U. Given a multi-set M, we denote by Set(M) as the set version of M, with all multiplicity information implicitly removed. When referring to a set, such as K, as a multi-set, we will mean that all the elements have multiplicity one. LEMMA 2. spk ðUÞ ¼ K

5 Proof of correctness Recall that K is the input to the algorithm and let U be the strings corresponding to the set of all maximal unitigs of K. We will assume for our proof that U does not contain any circular unitigs. We note that since BCALM 2 outputs strings, it cannot represent circular unitigs in its output. Circular unitigs present a corner case for both the analysis and the algorithm itself, and, for the sake of presentation brevity, we do not consider them here. We prove the correctness of BCALM 2 by showing that it outputs U. We first give a Lemma that will allow us to show that the output is U by arguing about its k and k þ 1 spectrums. LEMMA 1. Let S and T be two sets of strings of length at least k such that spkþ1 ðSÞ ¼ spkþ1 ðTÞ and spk ðSÞ ¼ spk ðTÞ and all these spectrums are without duplicates. Then, S ¼ T. PROOF. We will prove that S T. The same argument will be symmetrically applicable to prove T S, which will imply S ¼ T. First, we show that for all s 2 S, there exists a t 2 T such that s 2 t. Let s 2 S and let p ¼ maxfi : 9t 2 T s½1::i 2 tg, and let t be a string achieving the max. Note that p k þ 1 since every ðk þ 1Þmer of S is also in T. Suppose for the sake of contradiction that p 362KB Sizes 0 Downloads 5 Views


Introduction

The de Bruijn graph is a data structure first brought to bioinformatics as a method to assemble genomes from the experimental data generated by sequencing by hybridization [1]. It later became the key algorithmic technique in genome assembly [2, 3] that resulted in dozens of software tools [4–12]. In addition, the de Bruijn graphs have been used for repeat classification [13], de novo protein sequencing [14], synteny block construction [15, 16], multiple sequence alignment [17], and other applications in genomics and proteomics.

The breakpoint graph is a data structure introduced to study the reversal distance [18], which has formed the basis for much algorithmic research on rearrangements over the last two decades [19].

Since the connections between the breakpoint graphs and the de Bruijn graphs was never explicitly described, researchers studying genome rearrangements often do not realize that breakpoint graphs are merely de Bruijn graphs in disguise. As a result, they often do not know how to move from the traditional breakpoint graphs on synteny blocks to the breakpoint graphs on genomes (with "single nucleotide" resolution), particularly in the case of double-stranded genomes with inverted repeats. Likewise, researchers working in genome assembly are often unaware about the connections between the de Bruijn graphs and the breakpoint graphs. As a result, the exchange of ideas between these two communities has been limited. For example, Iqbal et al. [20] recently introduced the notion of the colored de Bruijn graphs that resulted in a popular Cortex assembler. While the notion of the colored de Bruijn graphs is essentially identical to the notion of the breakpoint graph, authors of [20] are probably unaware about this connection since they provided no references to previous genome rearrangement studies. This is unfortunate since various results about the breakpoint graphs (e.g., the connection between rearrangements and alternating cycles) remained beyond the scope of this very useful study.

Recently, genome rearrangement studies moved from the level of synteny blocks to the level of single nucleotides [21]. Likewise, genome assembly experts recently moved towards the analysis of structural variations and comparative assembly of related species based on the analysis of the de Bruijn graphs [20]. We thus argue that the time has come to explain that the breakpoint graphs and the de Bruijn graphs are two identical data structures (if one ignores a cosmetic difference between them) as they both represent specific instances of a general notion of the A-Bruijn graph introduced in [13]. The A-Bruijn graphs are based on representing genomes as sets of labeled paths and further gluing identically labeled edges (breakpoint graphs) or vertices (de Bruijn graphs) in the resulting paths.

We argue that a unified framework covering both breakpoint and de Bruijn graphs is important to bridge the divide between researchers working with breakpoint graphs (that usually focus in rearrangements and ignore repeats) and researchers working with de Bruijn graphs (that usually focus on repeats and ignore rearrangements). In reality, there exists a complex interplay between rearrangements and repeats, e.g., LINE repeats and segmental duplications often trigger rearrangements [22–24]. However, this interplay is not explicitly revealed by the breakpoint graphs since they do not even encode repeats (repeats are intentionally masked at the synteny block construction step). For example, the interplay between LINEs and rearrangements cannot be derived from the breakpoint graph alone forcing Zhao and Bourque [23] to perform additional analysis. Our goal is to introduce the graphs that encode both rearrangements and repeats and immediately reveal this interplay. For example, encoding repeats present in the breakpoint regions (that may potentially trigger rearrangements) leads to gluing alternating cycles in the breakpoint graphs and requires development of new algorithms that integrate rearrangements and repeats. In such graphs, the classical non-self-intersecting alternating cycles formed by edges alternating between two colors (the workhorse of genome rearrangement studies) may turn into self-intersecting cycles formed by edges alternating between 3 colors, where the third color corresponds to repeated elements (see Figure 1). Nurk and Pevzner [25] recently used this framework to develop a new comparative genome analysis tool SPArcle and applied it to analyzing multiple bacterial strains resulting from the "controlled evolution" experiments [26]. SPArcle is based on SPAdes assembler and, in difference from Cortex, it uses ideas from the previous genome rearrangement studies (e.g., alternating cycles) to analyze the resulting A-Bruijn graphs.

Genomes g UNE= S 1, S 2, S 3 et g B= S 1, − S 2, S 3 (represented as bicolored paths) differ from each other by a single reversal of segment S 2. The breakpoint graph PA(g UNE, G B) and the alternating cycle constructed from genomes g UNE et g B (left: no repeats at the breakpoint regions right, a pair of repeats colored in green at the breakpoint regions).

Genome rearrangement studies usually start from constructing a set of synteny blocks shared by two genomes (see Figure 2). Each genome is defined as a sequence of synteny blocks separated by breakpoint regions and is represented as a path formed by alternating colored and black edges, where synteny blocks correspond to directed and labeled black edges and breakpoint regions correspond to undirected colored edges. Figure 3(a) presents paths corresponding to 11 synteny blocks shared by Human and Mouse × chromosomes. Each synteny block S je is represented as an directed black edge ( S i t , S i h ) , where S i t and S i h refer to the endpoints of the synteny blocks representing its tail and head, respectively. Two consecutive synteny blocks are separated by a breakpoint region in the Human (Mouse) × chromosome that is modeled by a red (blue) edge connecting the corresponding endpoints of these synteny blocks. The (traditional) breakpoint graph of Human and Mouse × chromosomes is obtained by "gluing" identically labeled black edges in these two paths as shown in Figure 3.

The 11 synteny blocks shared by Human and Mouse × chromosomes (adapted from Pevzner and Tesler [33]).


Publisher’s note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary Figure 1 A comparison of the Flye and HINGE assembly graphs on bacterial genomes from the BACTERIA dataset.

(Left) The Flye and Hinge assembly graphs of the KP9657 dataset. There is a single unique edge entering into (and exiting) the unresolved “yellow” repeat and connecting it to the rest of the graph. Thus, this repeat can be resolved if one excludes the possibility that it is shared between a chromosome and a plasmid. In contrast to HINGE, Flye does not rule out this possibility and classifies the yellow repeat as unresolved. (Right) The Flye and Hinge assembly graphs of the EC10864 dataset show a mosaic repeat of multiplicity four formed by yellow, blue, red and green edges (the two copies of each edge represent complementary strands). HINGE reports a complete assembly into a single chromosome.

Supplementary Figure 2 The assembly graph of the YEAST-ONT dataset.

Edges that were classified as repetitive by Flye are shown in color, while unique edges are black. Flye assembled the YEAST-ONT dataset into a graph with 21 unique and 34 repeat edges and generated 21 contigs as unambiguous paths in the assembly graph. A path v1, …vje, vi+1vm in the graph is called unambiguous if there exists a single incoming edge into each vertex of this path before vi+1 and a single outgoing edge from each vertex after vje. Each unique contig is formed by a single unique edge and possibly multiple repeat edges, while repetitive contigs consist of the repetitive edges which were not covered by the unique contigs. The visualization was generated using the graphviz tool (http://graphviz.org).

Supplementary Figure 3 The assembly graph of the WORM dataset.

Edges that were classified as repetitive by Flye are shown in color, while unique edges are black. Flye assembled the WORM dataset into a graph with 127 unique and 61 repeat edges and generated 127 contigs as unambiguous paths in the assembly graph. The visualization was generated using the graphviz tool (http://graphviz.org).

Supplementary Figure 4 Dot plots showing the alignment of reads against the Flye assembly, the Miniasm assembly and the reference C. elegans génome.

(une) The reference genome contains a tandem repeat of length 1.9 kb (10 copies) on chromosome X with the repeated unit having length ≈190 nucleotides. In contrast, the Flye and Miniasm assemblies of this region suggest a tandem repeat of length 5.5 kb (27 copies) and 2.8 kb (13 copies), respectively. 15 reads that span over the tandem repeat support the Flye assembly (the mean length between the flanking unique sequence matches the repeat length reconstructed by Flye) and suggests that the Flye length estimate is more accurate. (b) The reference genome contains a tandem repeat of length 2 kb on chromosome 1. In contrast, the Flye and Miniasm assemblies of this region suggest a tandem repeat of length 10 kb and 5.6 kb, respectively. A single read that spans over the tandem repeat supports the Flye assembly. Since the mean read length in the WORM dataset is 11 kb, it is expected to have a single read spanning a given 10.0 kb region but many more reads spanning any 5.6 kb region (as implied by the Miniasm assembly) or 2.0 kb region (as implied by the reference genome). Six out of 23 reads cross the “left” border (two out of 18 reads cross the “right” border) of this tandem repeat by more than 5.6 kb, thus contradicting the length estimate given by Miniasm and suggesting that the Flye length estimate is more accurate. (c) The reference genome contains a tandem repeat of length 3 kb on chromosome X. In contrast, the Flye and Miniasm assemblies of this region suggest a tandem repeat of lengths 13.6 kb and 8 kb, respectively. A single read that spans over the tandem repeat reveals the repeat cluster to be of length 12.2k, which suggests that the Flye length estimate is more accurate. () The reference genome contains a tandem repeat of length 1.5 kb on chromosome 1. In contrast, the Flye and Miniasm assemblies of this region suggest tandem repeats of length 17 kb and 4.3 kb, respectively. One read that spans over the tandem repeat reveals the repeat cluster to be of length 18.0 kb, which suggests that the Flye length estimate is more accurate.