Search

Your search keyword '"Langmead, Ben"' showing total 381 results
Start Over Author "Langmead, Ben"
381 results on '"Langmead, Ben"'

1. MIOV: Reordering MOVI for even better locality

Author

Perešíni, Peter, Brown, Nathaniel K., Gagie, Travis, and Langmead, Ben

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We consider how to reorder the rows of Nishimoto and Tabei's move structure such that we more often move from one row to the next in memory.

Published
2024

2. Taxonomic classification with maximal exact matches in KATKA kernels and minimizer digests

Author

Draesslerová, Dominika, Ahmed, Omar, Gagie, Travis, Holub, Jan, Langmead, Ben, Manzini, Giovanni, and Navarro, Gonzalo

Subjects
Computer Science - Data Structures and Algorithms, Quantitative Biology - Genomics, Quantitative Biology - Populations and Evolution
Abstract

For taxonomic classification, we are asked to index the genomes in a phylogenetic tree such that later, given a DNA read, we can quickly choose a small subtree likely to contain the genome from which that read was drawn. Although popular classifiers such as Kraken use $k$-mers, recent research indicates that using maximal exact matches (MEMs) can lead to better classifications. For example, we can build an augmented FM-index over the the genomes in the tree concatenated in left-to-right order; for each MEM in a read, find the interval in the suffix array containing the starting positions of that MEM's occurrences in those genomes; find the minimum and maximum values stored in that interval; take the lowest common ancestor (LCA) of the genomes containing the characters at those positions. This solution is practical, however, only when the total size of the genomes in the tree is fairly small. In this paper we consider applying the same solution to three lossily compressed representations of the genomes' concatenation: a KATKA kernel, which discards characters that are not in the first or last occurrence of any $k_{\max}$-tuple, for a parameter $k_{\max}$; a minimizer digest; a KATKA kernel of a minimizer digest. With a test dataset and these three representations of it, simulated reads and various parameter settings, we checked how many reads' longest MEMs occurred only in the sequences from which those reads were generated ("true positive" reads). For some parameter settings we achieved significant compression while only slightly decreasing the true-positive rate.

Published
2024

3. Suffixient Sets

Author

Depuydt, Lore, Gagie, Travis, Langmead, Ben, Manzini, Giovanni, and Prezza, Nicola

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We define a suffixient set for a text $T [1..n]$ to be a set $S$ of positions between 1 and $n$ such that, for any edge descending from a node $u$ to a node $v$ in the suffix tree of $T$, there is an element $s \in S$ such that $u$'s path label is a suffix of $T [1..s - 1]$ and $T [s]$ is the first character of $(u, v)$'s edge label. We first show there is a suffixient set of cardinality at most $2 \bar{r}$, where $\bar{r}$ is the number of runs in the Burrows-Wheeler Transform of the reverse of $T$. We then show that, given a straight-line program for $T$ with $g$ rules, we can build an $O (\bar{r} + g)$-space index with which, given a pattern $P [1..m]$, we can find the maximal exact matches (MEMs) of $P$ with respect to $T$ in $O (m \log (\sigma) / \log n + d \log n)$ time, where $\sigma$ is the size of the alphabet and $d$ is the number of times we would fully or partially descend edges in the suffix tree of $T$ while finding those MEMs.

Published
2023

7. KATKA: A KRAKEN-like tool with $k$ given at query time

Author

Gagie, Travis, Kashgouli, Sana, and Langmead, Ben

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We describe a new tool, KATKA, that stores a phylogenetic tree $T$ such that later, given a pattern $P [1..m]$ and an integer $k$, it can quickly return the root of the smallest subtree of $T$ containing all the genomes in which the $k$-mer $P [i..i + k - 1]$ occurs, for $1 \leq i \leq m - k + 1$. This is similar to KRAKEN's functionality but with $k$ given at query time instead of at construction time.

Published
2022

10. Analysis of somatic mutations in 131 human brains reveals aging-associated hypermutability

Author

Bae, Taejeong, Fasching, Liana, Wang, Yifan, Shin, Joo Heon, Suvakov, Milovan, Jang, Yeongjun, Norton, Scott, Dias, Caroline, Mariani, Jessica, Jourdon, Alexandre, Wu, Feinan, Panda, Arijit, Pattni, Reenal, Chahine, Yasmine, Yeh, Rebecca, Roberts, Rosalinda C, Huttner, Anita, Kleinman, Joel E, Hyde, Thomas M, Straub, Richard E, Walsh, Christopher A, Urban, Alexander E, Leckman, James F, Weinberger, Daniel R, Vaccarino, Flora M, Abyzov, Alexej, Park, Peter J, Sestan, Nenad, Weinberger, Daniel, Moran, John V, Gage, Fred H, Gleeson, Joseph, Mathern, Gary, Courchesne, Eric, Roy, Subhojit, Chess, Andrew J, Akbarian, Schahram, Bizzotto, Sara, Coulter, Michael, D’Gama, Alissa, Ganz, Javier, Hill, Robert, Huang, August Yue, Khoshkhoo, Sattar, Kim, Sonia, Lee, Alice, Lodato, Michael, Maury, Eduardo A, Miller, Michael, Borges-Monroy, Rebeca, Rodin, Rachel, Zhou, Zinan, Bohrson, Craig, Chu, Chong, Cortes-Ciriano, Isidro, Dou, Yanmei, Galor, Alon, Gulhan, Doga, Kwon, Minseok, Luquette, Joe, Sherman, Maxwell, Viswanadham, Vinay, Jones, Attila, Rosenbluh, Chaggai, Cho, Sean, Langmead, Ben, Thorpe, Jeremy, Erwin, Jennifer, Jaffe, Andrew, McConnell, Michael, Narurkar, Rujuta, Paquola, Apua, Shin, Jooheon, Straub, Richard, Molitor, Cindy, Peters, Mette, Linker, Sara, Reed, Patrick, Wang, Meiyan, Urban, Alexander, Zhou, Bo, Zhu, Xiaowei, Serres Amero, Aitor, Juan, David, Lobon, Irene, Marques-Bonet, Tomas, Solis Moruno, Manuel, Garcia Perez, Raquel, Povolotskaya, Inna, Soriano, Eduardo, Antaki, Danny, and Averbuj, Dan

Subjects
Biotechnology, Brain Disorders, Intellectual and Developmental Disabilities (IDD), Genetics, Autism, Pediatric, Mental Health, Human Genome, Underpinning research, 2.1 Biological and endogenous factors, Aetiology, 1.1 Normal biological development and functioning, Mental health, Aging, Autistic Disorder, Brain, Enhancer Elements, Genetic, Gene Expression Regulation, Humans, Mutagenesis, Mutation, Protein Binding, Transcription Factors, Whole Genome Sequencing, Brain Somatic Mosaicism Network§, General Science & Technology
Abstract

We analyzed 131 human brains (44 neurotypical, 19 with Tourette syndrome, 9 with schizophrenia, and 59 with autism) for somatic mutations after whole genome sequencing to a depth of more than 200×. Typically, brains had 20 to 60 detectable single-nucleotide mutations, but ~6% of brains harbored hundreds of somatic mutations. Hypermutability was associated with age and damaging mutations in genes implicated in cancers and, in some brains, reflected in vivo clonal expansions. Somatic duplications, likely arising during development, were found in ~5% of normal and diseased brains, reflecting background mutagenesis. Brains with autism were associated with mutations creating putative transcription factor binding motifs in enhancer-like regions in the developing brain. The top-ranked affected motifs corresponded to MEIS (myeloid ectopic viral integration site) transcription factors, suggesting a potential link between their involvement in gene regulation and autism.

Published
2022

11. Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing

Author

Kempa, Dominik and Langmead, Ben

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Grammar compression is, next to Lempel-Ziv (LZ77) and run-length Burrows-Wheeler transform (RLBWT), one of the most flexible approaches to representing and processing highly compressible strings. The main idea is to represent a text as a context-free grammar whose language is precisely the input string. This is called a straight-line grammar (SLG). An AVL grammar, proposed by Rytter [Theor. Comput. Sci., 2003] is a type of SLG that additionally satisfies the AVL-property: the heights of parse-trees for children of every nonterminal differ by at most one. In contrast to other SLG constructions, AVL grammars can be constructed from the LZ77 parsing in compressed time: $\mathcal{O}(z \log n)$ where $z$ is the size of the LZ77 parsing and $n$ is the length of the input text. Despite these advantages, AVL grammars are thought to be too large to be practical. We present a new technique for rapidly constructing a small AVL grammar from an LZ77 or LZ77-like parse. Our algorithm produces grammars that are always at least five times smaller than those produced by the original algorithm, and never more than double the size of grammars produced by the practical Re-Pair compressor [Larsson and Moffat, Proc. IEEE, 2000]. Our algorithm also achieves low peak RAM usage. By combining this algorithm with recent advances in approximating the LZ77 parsing, we show that our method has the potential to construct a run-length BWT from an LZ77 parse in about one third of the time and peak RAM required by other approaches. Overall, we show that AVL grammars are surprisingly practical, opening the door to much faster construction of key compressed data structures.

Published
2021
Full Text
View/download PDF

13. PHONI: Streamed Matching Statistics with Multi-Genome References

Author

Boucher, Christina, Gagie, Travis, I, Tomohiro, Köppl, Dominik, Langmead, Ben, Manzini, Giovanni, Navarro, Gonzalo, Pacheco, Alejandro, and Rossi, Massimiliano

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Computing the matching statistics of patterns with respect to a text is a fundamental task in bioinformatics, but a formidable one when the text is a highly compressed genomic database. Bannai et al. gave an efficient solution for this case, which Rossi et al. recently implemented, but it uses two passes over the patterns and buffers a pointer for each character during the first pass. In this paper, we simplify their solution and make it streaming, at the cost of slowing it down slightly. This means that, first, we can compute the matching statistics of several long patterns (such as whole human chromosomes) in parallel while still using a reasonable amount of RAM; second, we can compute matching statistics online with low latency and thus quickly recognize when a pattern becomes incompressible relative to the database., Comment: Our code is available at https://github.com/koeppl/phoni

Published
2020

17. Matching reads to many genomes with the $r$-index

Author

Mun, Taher, Kuhnle, Alan, Boucher, Christina, Gagie, Travis, Langmead, Ben, and Manzini, Giovanni

Subjects
Computer Science - Data Structures and Algorithms, Quantitative Biology - Genomics
Abstract

The $r$-index is a tool for compressed indexing of genomic databases for exact pattern matching, which can be used to completely align reads that perfectly match some part of a genome in the database or to find seeds for reads that do not. This paper shows how to download and install the programs ri-buildfasta and ri-align; how to call ri-buildfasta on a FASTA file to build an $r$-index for that file; and how to query that index with ri-align. Availability: The source code for these programs is released under GPLv3 and available at https://github.com/alshai/r-index .

Published
2019

19. Schizophrenia-associated somatic copy-number variants from 12,834 cases reveal recurrent NRXN1 and ABCB11 disruptions

Author

Marshall, Christian R., Merico, Daniele, Thiruvahindrapuram, Bhooma, Wang, Zhouzhi, Scherer, Stephen W., Howrigan, Daniel P, Ripke, Stephan, Bulik-Sullivan, Brendan, Farh, Kai-How, Fromer, Menachem, Goldstein, Jacqueline I., Huang, Hailiang, Lee, Phil, Daly, Mark J., Neale, Benjamin M., Belliveau, Richard A., Jr., Bergen, Sarah E., Bevilacqua, Elizabeth, Chambert, Kimberley D., O'Dushlaine, Colm, Scolnick, Edward M., Smoller, Jordan W., Moran, Jennifer L., Palotie, Aarno, Petryshen, Tracey L., Wu, Wenting, Greer, Douglas S., Antaki, Danny, Shetty, Aniket, Gujral, Madhusudan, Brandler, William M., Malhotra, Dheeraj, Fuentes Fajarado, Karin V., Maile, Michelle S., Holmans, Peter A., Carrera, Noa, Craddock, Nick, Escott-Price, Valentina, Georgieva, Lyudmila, Hamshere, Marian L., Kavanagh, David, Legge, Sophie E., Pocklington, Andrew J., Richards, Alexander L., Ruderfer, Douglas M., Williams, Nigel M., Kirov, George, Owen, Michael J., Pinto, Dalila, Cai, Guiqing, Davis, Kenneth L., Drapeau, Elodie, Friedman, Joseph I, Haroutunian, Vahram, Parkhomenko, Elena, Reichenberg, Abraham, Silverman, Jeremy M., Buxbaum, Joseph D., Domenici, Enrico, Agartz, Ingrid, Djurovic, Srdjan, Mattingsdal, Morten, Melle, Ingrid, Andreassen, Ole A., Jönsson, Erik G., Söderman, Erik, Albus, Margot, Alexander, Madeline, Laurent, Claudine, Levinson, Douglas F., Amin, Farooq, Atkins, Joshua, Cairns, Murray J., Scott, Rodney J., Tooney, Paul A., Wu, Jing Qin, Bacanu, Silviu A., Bigdeli, Tim B., Reimers, Mark A., Webb, Bradley T., Wolen, Aaron R., Wormley, Brandon K., Kendler, Kenneth S., Riley, Brien P., Kähler, Anna K., Magnusson, Patrik K.E., Hultman, Christina M., Bertalan, Marcelo, Hansen, Thomas, Olsen, Line, Rasmussen, Henrik B., Werge, Thomas, Mattheisen, Manuel, Black, Donald W., Bruggeman, Richard, Buccola, Nancy G., Buckner, Randy L., Roffman, Joshua L., Byerley, William, Cahn, Wiepke, Kahn, René S, Strengman, Eric, Ophoff, Roel A., Carr, Vaughan J., Catts, Stanley V., Henskens, Frans A., Loughland, Carmel M., Michie, Patricia T., Pantelis, Christos, Schall, Ulrich, Jablensky, Assen V., Kelly, Brian J., Campion, Dominique, Cantor, Rita M., Cheng, Wei, Cloninger, C. Robert, Svrakic, Dragan M, Cohen, David, Cormican, Paul, Donohoe, Gary, Morris, Derek W., Corvin, Aiden, Gill, Michael, Crespo-Facorro, Benedicto, Crowley, James J., Farrell, Martilias S., Giusti-Rodríguez, Paola, Kim, Yunjung, Szatkiewicz, Jin P., Williams, Stephanie, Curtis, David, Pimm, Jonathan, Gurling, Hugh, McQuillin, Andrew, Davidson, Michael, Weiser, Mark, Degenhardt, Franziska, Forstner, Andreas J., Herms, Stefan, Hoffmann, Per, Hofman, Andrea, Cichon, Sven, Nöthen, Markus M., Del Favero, Jurgen, DeLisi, Lynn E., McCarley, Robert W., Levy, Deborah L., Mesholam-Gately, Raquelle I., Seidman, Larry J., Dikeos, Dimitris, Papadimitriou, George N., Dinan, Timothy, Duan, Jubao, Sanders, Alan R., Gejman, Pablo V., Gershon, Elliot S., Dudbridge, Frank, Eichhammer, Peter, Eriksson, Johan, Salomaa, Veikko, Essioux, Laurent, Fanous, Ayman H., Knowles, James A., Pato, Michele T., Pato, Carlos N., Frank, Josef, Meier, Sandra, Schulze, Thomas G., Strohmaier, Jana, Witt, Stephanie H., Rietschel, Marcella, Franke, Lude, Karjalainen, Juha, Freedman, Robert, Olincy, Ann, Freimer, Nelson B., Purcell, Shaun M., Roussos, Panos, Stahl, Eli A., Sklar, Pamela, Giegling, Ina, Hartmann, Annette M., Konte, Bettina, Rujescu, Dan, Godard, Stephanie, Hirschhorn, Joel N., Pers, Tune H., Price, Alkes, Esko, Tõnu, Gratten, Jacob, Lee, S. Hong, Visscher, Peter M., Wray, Naomi R., Mowry, Bryan J., de Haan, Lieuwe, Meijer, Carin J., Hansen, Mark, Ikeda, Masashi, Iwata, Nakao, Joa, Inge, Kalaydjieva, Luba, Keller, Matthew C., Kennedy, James L., Zai, Clement C., Knight, Jo, Lerer, Bernard, Liang, Kung-Yee, Lieberman, Jeffrey, Stroup, T. Scott, Lönnqvist, Jouko, Suvisaari, Jaana, Maher, Brion S., Maier, Wolfgang, Mallet, Jacques, McDonald, Colm, McIntosh, Andrew M., Blackwood, Douglas H.R., Metspalu, Andres, Milani, Lili, Milanova, Vihra, Mokrab, Younes, Collier, David A., Müller-Myhsok, Bertram, Murphy, Kieran C., Murray, Robin M., Powell, John, Myin-Germeys, Inez, Van Os, Jim, Nenadic, Igor, Nertney, Deborah A., Nestadt, Gerald, Pulver, Ann E., Nicodemus, Kristin K., Nisenbaum, Laura, Nordin, Annelie, Adolfsson, Rolf, O'Callaghan, Eadbhard, Oh, Sang-Yun, O'Neill, F. Anthony, Paunio, Tiina, Pietiläinen, Olli, Perkins, Diana O., Quested, Digby, Savitz, Adam, Li, Qingqin S., Schwab, Sibylle G., Shi, Jianxin, Spencer, Chris C.A., Thirumalai, Srinivas, Veijola, Juha, Waddington, John, Walsh, Dermot, Wildenauer, Dieter B., Bramon, Elvira, Darvasi, Ariel, Posthuma, Danielle, St. Clair, David, Shanta, Omar, Klein, Marieke, Park, Peter J., Weinberger, Daniel, Moran, John V., Gage, Fred H., Vaccarino, Flora M., Gleeson, Joseph, Mathern, Gary, Courchesne, Eric, Roy, Subhojit, Bizzotto, Sara, Coulter, Michael, Dias, Caroline, D'Gama, Alissa, Ganz, Javier, Hill, Robert, Huang, August Yue, Khoshkhoo, Sattar, Kim, Sonia, Lodato, Michael, Miller, Michael, Borges-Monroy, Rebeca, Rodin, Rachel, Zhou, Zinan, Bohrson, Craig, Chu, Chong, Cortes-Ciriano, Isidro, Dou, Yanmei, Galor, Alon, Gulhan, Doga, Kwon, Minseok, Luquette, Joe, Viswanadham, Vinay, Jones, Attila, Rosenbluh, Chaggai, Cho, Sean, Langmead, Ben, Thorpe, Jeremy, Erwin, Jennifer, Jaffe, Andrew, McConnell, Michael, Narurkar, Rujuta, Paquola, Apua, Shin, Jooheon, Straub, Richard, Abyzov, Alexej, Bae, Taejeong, Jang, Yeongjun, Wang, Yifan, Gage, Fred, Linker, Sara, Reed, Patrick, Wang, Meiyan, Urban, Alexander, Zhou, Bo, Zhu, Xiaowei, Pattni, Reenal, Amero, Aitor Serres, Juan, David, Lobon, Irene, Marques-Bonet, Tomas, Moruno, Manuel Solis, Perez, Raquel Garcia, Povolotskaya, Inna, Soriano, Eduardo, Averbuj, Dan, Ball, Laurel, Breuss, Martin, Yang, Xiaoxu, Chung, Changuk, Emery, Sarah B., Flasch, Diane A., Kidd, Jeffrey M., Kopera, Huira C., Kwan, Kenneth Y., Mills, Ryan E., Moldovan, John B., Sun, Chen, Zhao, Xuefang, Zhou, Weichen, Frisbie, Trenton J., Cherskov, Adriana, Fasching, Liana, Jourdon, Alexandre, Pochareddy, Sirisha, Scuderi, Soraya, Sestan, Nenad, Maury, Eduardo A., Sherman, Maxwell A., Genovese, Giulio, Gilgenast, Thomas G., Kamath, Tushar, Burris, S.J., Rajarajan, Prashanth, Flaherty, Erin, Akbarian, Schahram, Chess, Andrew, McCarroll, Steven A., Loh, Po-Ru, Phillips-Cremins, Jennifer E., Brennand, Kristen J., Macosko, Evan Z., Walters, James T.R., O’Donovan, Michael, Sullivan, Patrick, Sebat, Jonathan, Lee, Eunjung A., and Walsh, Christopher A.

Published
2023
Full Text
View/download PDF

21. KATKA: A KRAKEN-Like Tool with k Given at Query Time

Author

Gagie, Travis, Kashgouli, Sana, Langmead, Ben, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Arroyuelo, Diego, editor, and Poblete, Barbara, editor

Published
2022
Full Text
View/download PDF

22. Efficient Construction of a Complete Index for Pan-Genomics Read Alignment

Author

Kuhnle, Alan, Mun, Taher, Boucher, Christina, Gagie, Travis, Langmead, Ben, and Manzini, Giovanni

Subjects
Computer Science - Data Structures and Algorithms
Abstract

While short read aligners, which predominantly use the FM-index, are able to easily index one or a few human genomes, they do not scale well to indexing databases containing thousands of genomes. To understand why, it helps to examine the main components of the FM-index in more detail, which is a rank data structure over the Burrows-Wheeler Transform (BWT) of the string that will allow us to find the interval in the string's suffix array (SA) containing pointers to starting positions of occurrences of a given pattern; second, a sample of the SA that --- when used with the rank data structure --- allows us access the SA. The rank data structure can be kept small even for large genomic databases, by run-length compressing the BWT, but until recently there was no means known to keep the SA sample small without greatly slowing down access to the SA. Now that Gagie et al. (SODA 2018) have defined an SA sample that takes about the same space as the run-length compressed BWT --- we have the design for efficient FM-indexes of genomic databases but are faced with the problem of building them. In 2018 we showed how to build the BWT of large genomic databases efficiently (WABI 2018) but the problem of building Gagie et al.'s SA sample efficiently was left open. We compare our approach to state-of-the-art methods for constructing the SA sample, and demonstrate that it is the fastest and most space-efficient method on highly repetitive genomic databases. Lastly, we apply our method for indexing partial and whole human genomes, and show that it improves over Bowtie with respect to both memory and time.

Published
2018

23. Prefix-Free Parsing for Building Big BWTs

Author

Boucher, Christina, Gagie, Travis, Kuhnle, Alan, Langmead, Ben, Manzini, Giovanni, and Mun, Taher

Subjects
Computer Science - Data Structures and Algorithms
Abstract

High-throughput sequencing technologies have led to explosive growth of genomic databases; one of which will soon reach hundreds of terabytes. For many applications we want to build and store indexes of these databases but constructing such indexes is a challenge. Fortunately, many of these genomic databases are highly-repetitive---a characteristic that can be exploited to ease the computation of the Burrows-Wheeler Transform (BWT), which underlies many popular indexes. In this paper, we introduce a preprocessing algorithm, referred to as {\em prefix-free parsing}, that takes a text $T$ as input, and in one-pass generates a dictionary $D$ and a parse $P$ of $T$ with the property that the BWT of $T$ can be constructed from $D$ and $P$ using workspace proportional to their total size and $O (|T|)$-time. Our experiments show that $D$ and $P$ are significantly smaller than $T$ in practice, and thus, can fit in a reasonable internal memory even when $T$ is very large. In particular, we show that with prefix-free parsing we can build an 131-megabyte run-length compressed FM-index (restricted to support only counting and not locating) for 1000 copies of human chromosome 19 in 2 hours using 21 gigabytes of memory, suggesting that we can build a 6.73 gigabyte index for 1000 complete human-genome haplotypes in approximately 102 hours using about 1 terabyte of memory., Comment: Preliminary version appeared at WABI '18; full version submitted to a journal

Published
2018

24. Cell-specific regulation of gene expression using splicing-dependent frameshifting

Author

Ling, Jonathan P., Bygrave, Alexei M., Santiago, Clayton P., Carmen-Orozco, Rogger P., Trinh, Vickie T., Yu, Minzhong, Li, Yini, Liu, Ying, Bowden, Kyra D., Duncan, Leighton H., Han, Jeong, Taneja, Kamil, Dongmo, Rochinelle, Babola, Travis A., Parker, Patrick, Jiang, Lizhi, Leavey, Patrick J., Smith, Jennifer J., Vistein, Rachel, Gimmen, Megan Y., Dubner, Benjamin, Helmenstine, Eric, Teodorescu, Patric, Karantanos, Theodoros, Ghiaur, Gabriel, Kanold, Patrick O., Bergles, Dwight, Langmead, Ben, Sun, Shuying, Nielsen, Kristina J., Peachey, Neal, Singh, Mandeep S., Dalton, W. Brian, Rajaii, Fatemeh, Huganir, Richard L., and Blackshaw, Seth

Published
2022
Full Text
View/download PDF

29. Efficient Construction of a Complete Index for Pan-Genomics Read Alignment

Author

Kuhnle, Alan, Mun, Taher, Boucher, Christina, Gagie, Travis, Langmead, Ben, Manzini, Giovanni, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, and Cowen, Lenore J., editor

Published
2019
Full Text
View/download PDF

33. Sigmoni: classification of nanopore signal with a compressed pangenome index.

Author

Shivakumar, Vikram S, Ahmed, Omar Y, Kovaka, Sam, Zakeri, Mohsen, and Langmead, Ben

Subjects
HUMAN genome, PAN-genome, SIGNAL classification, GENOMES, CLASSIFICATION
Abstract

Summary Improvements in nanopore sequencing necessitate efficient classification methods, including pre-filtering and adaptive sampling algorithms that enrich for reads of interest. Signal-based approaches circumvent the computational bottleneck of basecalling. But past methods for signal-based classification do not scale efficiently to large, repetitive references like pangenomes, limiting their utility to partial references or individual genomes. We introduce Sigmoni: a rapid, multiclass classification method based on the r -index that scales to references of hundreds of Gbps. Sigmoni quantizes nanopore signal into a discrete alphabet of picoamp ranges. It performs rapid, approximate matching using matching statistics, classifying reads based on distributions of picoamp matching statistics and co-linearity statistics, all in linear query time without the need for seed-chain-extend. Sigmoni is 10–100× faster than previous methods for adaptive sampling in host depletion experiments with improved accuracy, and can query reads against large microbial or human pangenomes. Sigmoni is the first signal-based tool to scale to a complete human genome and pangenome while remaining fast enough for adaptive sampling applications. Availability and implementation Sigmoni is implemented in Python, and is available open-source at https://github.com/vshiv18/sigmoni. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

39. Schizophrenia-associated somatic copy-number variants from 12,834 cases reveal recurrent NRXN1 and ABCB11 disruptions

Author

Maury, Eduardo A., primary, Sherman, Maxwell A., additional, Genovese, Giulio, additional, Gilgenast, Thomas G., additional, Kamath, Tushar, additional, Burris, S.J., additional, Rajarajan, Prashanth, additional, Flaherty, Erin, additional, Akbarian, Schahram, additional, Chess, Andrew, additional, McCarroll, Steven A., additional, Loh, Po-Ru, additional, Phillips-Cremins, Jennifer E., additional, Brennand, Kristen J., additional, Macosko, Evan Z., additional, Walters, James T.R., additional, O’Donovan, Michael, additional, Sullivan, Patrick, additional, Sebat, Jonathan, additional, Lee, Eunjung A., additional, Walsh, Christopher A., additional, Marshall, Christian R., additional, Merico, Daniele, additional, Thiruvahindrapuram, Bhooma, additional, Wang, Zhouzhi, additional, Scherer, Stephen W., additional, Howrigan, Daniel P, additional, Ripke, Stephan, additional, Bulik-Sullivan, Brendan, additional, Farh, Kai-How, additional, Fromer, Menachem, additional, Goldstein, Jacqueline I., additional, Huang, Hailiang, additional, Lee, Phil, additional, Daly, Mark J., additional, Neale, Benjamin M., additional, Belliveau, Richard A., additional, Bergen, Sarah E., additional, Bevilacqua, Elizabeth, additional, Chambert, Kimberley D., additional, O'Dushlaine, Colm, additional, Scolnick, Edward M., additional, Smoller, Jordan W., additional, Moran, Jennifer L., additional, Palotie, Aarno, additional, Petryshen, Tracey L., additional, Wu, Wenting, additional, Greer, Douglas S., additional, Antaki, Danny, additional, Shetty, Aniket, additional, Gujral, Madhusudan, additional, Brandler, William M., additional, Malhotra, Dheeraj, additional, Fuentes Fajarado, Karin V., additional, Maile, Michelle S., additional, Holmans, Peter A., additional, Carrera, Noa, additional, Craddock, Nick, additional, Escott-Price, Valentina, additional, Georgieva, Lyudmila, additional, Hamshere, Marian L., additional, Kavanagh, David, additional, Legge, Sophie E., additional, Pocklington, Andrew J., additional, Richards, Alexander L., additional, Ruderfer, Douglas M., additional, Williams, Nigel M., additional, Kirov, George, additional, Owen, Michael J., additional, Pinto, Dalila, additional, Cai, Guiqing, additional, Davis, Kenneth L., additional, Drapeau, Elodie, additional, Friedman, Joseph I, additional, Haroutunian, Vahram, additional, Parkhomenko, Elena, additional, Reichenberg, Abraham, additional, Silverman, Jeremy M., additional, Buxbaum, Joseph D., additional, Domenici, Enrico, additional, Agartz, Ingrid, additional, Djurovic, Srdjan, additional, Mattingsdal, Morten, additional, Melle, Ingrid, additional, Andreassen, Ole A., additional, Jönsson, Erik G., additional, Söderman, Erik, additional, Albus, Margot, additional, Alexander, Madeline, additional, Laurent, Claudine, additional, Levinson, Douglas F., additional, Amin, Farooq, additional, Atkins, Joshua, additional, Cairns, Murray J., additional, Scott, Rodney J., additional, Tooney, Paul A., additional, Wu, Jing Qin, additional, Bacanu, Silviu A., additional, Bigdeli, Tim B., additional, Reimers, Mark A., additional, Webb, Bradley T., additional, Wolen, Aaron R., additional, Wormley, Brandon K., additional, Kendler, Kenneth S., additional, Riley, Brien P., additional, Kähler, Anna K., additional, Magnusson, Patrik K.E., additional, Hultman, Christina M., additional, Bertalan, Marcelo, additional, Hansen, Thomas, additional, Olsen, Line, additional, Rasmussen, Henrik B., additional, Werge, Thomas, additional, Mattheisen, Manuel, additional, Black, Donald W., additional, Bruggeman, Richard, additional, Buccola, Nancy G., additional, Buckner, Randy L., additional, Roffman, Joshua L., additional, Byerley, William, additional, Cahn, Wiepke, additional, Kahn, René S, additional, Strengman, Eric, additional, Ophoff, Roel A., additional, Carr, Vaughan J., additional, Catts, Stanley V., additional, Henskens, Frans A., additional, Loughland, Carmel M., additional, Michie, Patricia T., additional, Pantelis, Christos, additional, Schall, Ulrich, additional, Jablensky, Assen V., additional, Kelly, Brian J., additional, Campion, Dominique, additional, Cantor, Rita M., additional, Cheng, Wei, additional, Cloninger, C. Robert, additional, Svrakic, Dragan M, additional, Cohen, David, additional, Cormican, Paul, additional, Donohoe, Gary, additional, Morris, Derek W., additional, Corvin, Aiden, additional, Gill, Michael, additional, Crespo-Facorro, Benedicto, additional, Crowley, James J., additional, Farrell, Martilias S., additional, Giusti-Rodríguez, Paola, additional, Kim, Yunjung, additional, Szatkiewicz, Jin P., additional, Williams, Stephanie, additional, Curtis, David, additional, Pimm, Jonathan, additional, Gurling, Hugh, additional, McQuillin, Andrew, additional, Davidson, Michael, additional, Weiser, Mark, additional, Degenhardt, Franziska, additional, Forstner, Andreas J., additional, Herms, Stefan, additional, Hoffmann, Per, additional, Hofman, Andrea, additional, Cichon, Sven, additional, Nöthen, Markus M., additional, Del Favero, Jurgen, additional, DeLisi, Lynn E., additional, McCarley, Robert W., additional, Levy, Deborah L., additional, Mesholam-Gately, Raquelle I., additional, Seidman, Larry J., additional, Dikeos, Dimitris, additional, Papadimitriou, George N., additional, Dinan, Timothy, additional, Duan, Jubao, additional, Sanders, Alan R., additional, Gejman, Pablo V., additional, Gershon, Elliot S., additional, Dudbridge, Frank, additional, Eichhammer, Peter, additional, Eriksson, Johan, additional, Salomaa, Veikko, additional, Essioux, Laurent, additional, Fanous, Ayman H., additional, Knowles, James A., additional, Pato, Michele T., additional, Pato, Carlos N., additional, Frank, Josef, additional, Meier, Sandra, additional, Schulze, Thomas G., additional, Strohmaier, Jana, additional, Witt, Stephanie H., additional, Rietschel, Marcella, additional, Franke, Lude, additional, Karjalainen, Juha, additional, Freedman, Robert, additional, Olincy, Ann, additional, Freimer, Nelson B., additional, Purcell, Shaun M., additional, Roussos, Panos, additional, Stahl, Eli A., additional, Sklar, Pamela, additional, Giegling, Ina, additional, Hartmann, Annette M., additional, Konte, Bettina, additional, Rujescu, Dan, additional, Godard, Stephanie, additional, Hirschhorn, Joel N., additional, Pers, Tune H., additional, Price, Alkes, additional, Esko, Tõnu, additional, Gratten, Jacob, additional, Lee, S. Hong, additional, Visscher, Peter M., additional, Wray, Naomi R., additional, Mowry, Bryan J., additional, de Haan, Lieuwe, additional, Meijer, Carin J., additional, Hansen, Mark, additional, Ikeda, Masashi, additional, Iwata, Nakao, additional, Joa, Inge, additional, Kalaydjieva, Luba, additional, Keller, Matthew C., additional, Kennedy, James L., additional, Zai, Clement C., additional, Knight, Jo, additional, Lerer, Bernard, additional, Liang, Kung-Yee, additional, Lieberman, Jeffrey, additional, Stroup, T. Scott, additional, Lönnqvist, Jouko, additional, Suvisaari, Jaana, additional, Maher, Brion S., additional, Maier, Wolfgang, additional, Mallet, Jacques, additional, McDonald, Colm, additional, McIntosh, Andrew M., additional, Blackwood, Douglas H.R., additional, Metspalu, Andres, additional, Milani, Lili, additional, Milanova, Vihra, additional, Mokrab, Younes, additional, Collier, David A., additional, Müller-Myhsok, Bertram, additional, Murphy, Kieran C., additional, Murray, Robin M., additional, Powell, John, additional, Myin-Germeys, Inez, additional, Van Os, Jim, additional, Nenadic, Igor, additional, Nertney, Deborah A., additional, Nestadt, Gerald, additional, Pulver, Ann E., additional, Nicodemus, Kristin K., additional, Nisenbaum, Laura, additional, Nordin, Annelie, additional, Adolfsson, Rolf, additional, O'Callaghan, Eadbhard, additional, Oh, Sang-Yun, additional, O'Neill, F. Anthony, additional, Paunio, Tiina, additional, Pietiläinen, Olli, additional, Perkins, Diana O., additional, Quested, Digby, additional, Savitz, Adam, additional, Li, Qingqin S., additional, Schwab, Sibylle G., additional, Shi, Jianxin, additional, Spencer, Chris C.A., additional, Thirumalai, Srinivas, additional, Veijola, Juha, additional, Waddington, John, additional, Walsh, Dermot, additional, Wildenauer, Dieter B., additional, Bramon, Elvira, additional, Darvasi, Ariel, additional, Posthuma, Danielle, additional, St. Clair, David, additional, Shanta, Omar, additional, Klein, Marieke, additional, Park, Peter J., additional, Weinberger, Daniel, additional, Moran, John V., additional, Gage, Fred H., additional, Vaccarino, Flora M., additional, Gleeson, Joseph, additional, Mathern, Gary, additional, Courchesne, Eric, additional, Roy, Subhojit, additional, Bizzotto, Sara, additional, Coulter, Michael, additional, Dias, Caroline, additional, D'Gama, Alissa, additional, Ganz, Javier, additional, Hill, Robert, additional, Huang, August Yue, additional, Khoshkhoo, Sattar, additional, Kim, Sonia, additional, Lodato, Michael, additional, Miller, Michael, additional, Borges-Monroy, Rebeca, additional, Rodin, Rachel, additional, Zhou, Zinan, additional, Bohrson, Craig, additional, Chu, Chong, additional, Cortes-Ciriano, Isidro, additional, Dou, Yanmei, additional, Galor, Alon, additional, Gulhan, Doga, additional, Kwon, Minseok, additional, Luquette, Joe, additional, Viswanadham, Vinay, additional, Jones, Attila, additional, Rosenbluh, Chaggai, additional, Cho, Sean, additional, Langmead, Ben, additional, Thorpe, Jeremy, additional, Erwin, Jennifer, additional, Jaffe, Andrew, additional, McConnell, Michael, additional, Narurkar, Rujuta, additional, Paquola, Apua, additional, Shin, Jooheon, additional, Straub, Richard, additional, Abyzov, Alexej, additional, Bae, Taejeong, additional, Jang, Yeongjun, additional, Wang, Yifan, additional, Gage, Fred, additional, Linker, Sara, additional, Reed, Patrick, additional, Wang, Meiyan, additional, Urban, Alexander, additional, Zhou, Bo, additional, Zhu, Xiaowei, additional, Pattni, Reenal, additional, Amero, Aitor Serres, additional, Juan, David, additional, Lobon, Irene, additional, Marques-Bonet, Tomas, additional, Moruno, Manuel Solis, additional, Perez, Raquel Garcia, additional, Povolotskaya, Inna, additional, Soriano, Eduardo, additional, Averbuj, Dan, additional, Ball, Laurel, additional, Breuss, Martin, additional, Yang, Xiaoxu, additional, Chung, Changuk, additional, Emery, Sarah B., additional, Flasch, Diane A., additional, Kidd, Jeffrey M., additional, Kopera, Huira C., additional, Kwan, Kenneth Y., additional, Mills, Ryan E., additional, Moldovan, John B., additional, Sun, Chen, additional, Zhao, Xuefang, additional, Zhou, Weichen, additional, Frisbie, Trenton J., additional, Cherskov, Adriana, additional, Fasching, Liana, additional, Jourdon, Alexandre, additional, Pochareddy, Sirisha, additional, Scuderi, Soraya, additional, and Sestan, Nenad, additional

Published
2023
Full Text
View/download PDF

40. Efficient encoding of large antigenic spaces by epitope prioritization with Dolphyn

Author

Liebhoff, Anna-Maria, primary, Venkataraman, Thiagarajan, additional, Morgenlander, William R, additional, Na, Miso, additional, Kula, Tomasz, additional, Waugh, Kathleen, additional, Morrison, Charles, additional, Rewers, Marian, additional, Longman, Randy, additional, Round, June, additional, Elledge, Stephen, additional, Ruczinski, Ingo, additional, Langmead, Ben, additional, and Larman, H Benjamin, additional

Published
2023
Full Text
View/download PDF

46. A scalable and unbiased discordance metric with H.

Author

Dyjack, Nathan, Baker, Daniel N, Braverman, Vladimir, Langmead, Ben, and Hicks, Stephanie C

Subjects
DISCRETE groups, EUCLIDEAN distance, CLUSTER analysis (Statistics), RNA sequencing, METAL clusters, VALIDITY of statistics
Abstract

A standard unsupervised analysis is to cluster observations into discrete groups using a dissimilarity measure, such as Euclidean distance. If there does not exist a ground-truth label for each observation necessary for external validity metrics, then internal validity metrics, such as the tightness or separation of the clusters, are often used. However, the interpretation of these internal metrics can be problematic when using different dissimilarity measures as they have different magnitudes and ranges of values that they span. To address this problem, previous work introduced the "scale-agnostic" $G_{+}$ discordance metric; however, this internal metric is slow to calculate for large data. Furthermore, in the setting of unsupervised clustering with $k$ groups, we show that $G_{+}$ varies as a function of the proportion of observations assigned to each of the groups (or clusters), referred to as the group balance, which is an undesirable property. To address this problem, we propose a modification of $G_{+}$, referred to as $H_{+}$, and demonstrate that $H_{+}$ does not vary as a function of group balance using a simulation study and with public single-cell RNA-sequencing data. Finally, we provide scalable approaches to estimate $H_{+}$, which are available in the $\mathtt{fasthplus}$ R package. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results