-mer in the suffix array of the human genome to within 255 positions. Furthermore, we demonstrate the potential of our approach to impact a variety of downstream applications. First, the PLA-index halves the time of binary search on the suffix array of the human genome. Second, the PLA-index reduces the space of a direct-access lookup table by 76 percent, without increasing the run time. Third, we plug the PLA-index into a state-of-the-art read aligner Strobealign and replace a 2 GiB component with a PLA-index of size 1.5 MiB, without significantly effecting runtime. The software and reproducibility information is freely available at https://github.com/medvedevgroup/pla-index.

genomes. Our modified algorithms lead to a substantial improvement in alignment-based contiguity, with negligible additional computational costs and either no or a small increase in the number of misassemblies.

A colored de Bruijn graph (also called a set of k-mer sets), is a set of k-mers with every k-mer assigned a set of colors. Colored de Bruijn graphs are used in a variety of applications, including variant calling, genome assembly, and database search. However, their size has posed a scalability challenge to algorithm developers and users. There have been numerous indexing data structures proposed that allow to store the graph compactly while supporting fast query operations. However, disk compression algorithms, which do not need to support queries on the compressed data and can thus be more space-efficient, have received little attention. The dearth of specialized compression tools has been a detriment to tool developers, tool users, and reproducibility efforts. In this paper, we develop a new tool that compresses colored de Bruijn graphs to disk, building on previous ideas for compression of k-mer sets and indexing colored de Bruijn graphs. We test our tool, called ESS-color, on various datasets, including both sequencing data and whole genomes. ESS-color achieves better compression than all evaluated tools and all datasets, with no other tool able to consistently achieve less than 44% space overhead.

-mers from the pattern sketch occur in the sketch of the text. We evaluate our algorithm's performance in mapping long reads to the T2T assembly of human chromosome Y, where ampliconic regions make it desirable to find all good mapping positions. For an equivalent level of precision as minimap2, the recall of our algorithm is 0.88, compared to only 0.76 of minimap2.

MOTIVATION: Sketching is now widely used in bioinformatics to reduce data size and increase data processing speed. Sketching approaches entice with improved scalability but also carry the danger of decreased accuracy and added bias. In this article, we investigate the minimizer sketch and its use to estimate the Jaccard similarity between two sequences. RESULTS: We show that the minimizer Jaccard estimator is biased and inconsistent, which means that the expected difference (i.e. the bias) between the estimator and the true value is not zero, even in the limit as the lengths of the sequences grow. We derive an analytical formula for the bias as a function of how the shared k-mers are laid out along the sequences. We show both theoretically and empirically that there are families of sequences where the bias can be substantial (e.g. the true Jaccard can be more than double the estimate). Finally, we demonstrate that this bias affects the accuracy of the widely used mashmap read mapping tool. AVAILABILITY AND IMPLEMENTATION: Scripts to reproduce our experiments are available at https://github.com/medvedevgroup/minimizer-jaccard-estimator/tree/main/reproduce. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUMMARY: Bioinformatics applications increasingly rely on ad hoc disk storage of k-mer sets, e.g. for de Bruijn graphs or alignment indexes. Here, we introduce the K-mer File Format as a general lossless framework for storing and manipulating k-mer sets, realizing space savings of 3-5× compared to other formats, and bringing interoperability across tools. AVAILABILITY AND IMPLEMENTATION: Format specification, C++/Rust API, tools: https://github.com/Kmer-File-Format/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Genome annotations are a common way to represent genomic features such as genes, regulatory elements or epigenetic modifications. The amount of overlap between two annotations is often used to ascertain if there is an underlying biological connection between them. In order to distinguish between true biological association and overlap by pure chance, a robust measure of significance is required. One common way to do this is to determine if the number of intervals in the reference annotation that intersect the query annotation is statistically significant. However, currently employed statistical frameworks are often either inefficient or inaccurate when computing P-values on the scale of the whole human genome. RESULTS: We show that finding the P-values under the typically used 'gold' null hypothesis is NP-hard. This motivates us to reformulate the null hypothesis using Markov chains. To be able to measure the fidelity of our Markovian null hypothesis, we develop a fast direct sampling algorithm to estimate the P-value under the gold null hypothesis. We then present an open-source software tool MCDP that computes the P-values under the Markovian null hypothesis in O(m2+n) time and O(m) memory, where m and n are the numbers of intervals in the reference and query annotations, respectively. Notably, MCDP runtime and memory usage are independent from the genome length, allowing it to outperform previous approaches in runtime and memory usage by orders of magnitude on human genome annotations, while maintaining the same level of accuracy. AVAILABILITY AND IMPLEMENTATION: The software is available at https://github.com/fmfi-compbio/mc-overlaps. All data for reproducibility are available at https://github.com/fmfi-compbio/mc-overlaps-reproducibility. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Many students are taught about genome assembly using the dichotomy between the complexity of finding Eulerian and Hamiltonian cycles (easy versus hard, respectively). This dichotomy is sometimes used to motivate the use of de Bruijn graphs in practice. In this paper, we explain that while de Bruijn graphs have indeed been very useful, the reason has nothing to do with the complexity of the Hamiltonian and Eulerian cycle problems. We give 2 arguments. The first is that a genome reconstruction is never unique and hence an algorithm for finding Eulerian or Hamiltonian cycles is not part of any assembly algorithm used in practice. The second is that even if an arbitrary genome reconstruction was desired, one could do so in linear time in both the Eulerian and Hamiltonian paradigms.

MOTIVATION: Algorithmic solutions to index and search biological databases are a fundamental part of bioinformatics, providing underlying components to many end-user tools. Inexpensive next generation sequencing has filled publicly available databases such as the Sequence Read Archive beyond the capacity of traditional indexing methods. Recently, the Sequence Bloom Tree (SBT) and its derivatives were proposed as a way to efficiently index such data for queries about transcript presence. RESULTS: We build on the SBT framework to construct the HowDe-SBT data structure, which uses a novel partitioning of information to reduce the construction and query time as well as the size of the index. Compared to previous SBT methods, on real RNA-seq data, HowDe-SBT can construct the index in less than 36% of the time and with 39% less space and can answer small-batch queries at least five times faster. We also develop a theoretical framework in which we can analyze and bound the space and query performance of HowDe-SBT compared to other SBT methods. AVAILABILITY AND IMPLEMENTATION: HowDe-SBT is available as a free open source program on https://github.com/medvedevgroup/HowDeSBT. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Conferences are great venues for disseminating algorithmic bioinformatics results, but they unfortunately do not offer an opportunity to make major revisions in the way that journals do. As a result, it is not possible for authors to fix mistakes that might be easily correctable but nevertheless can cause the paper to be rejected. As a reviewer, I wish that I had the opportunity to tell the authors, "Hey, you forgot to do this really important thing, without which it is hard to accept the paper, but if you could go back and fix it, you might have a great paper for the conference." This lack of a back and forth can be especially problematic for first-time submitters or those from outside the field, e.g., biologists. In this article, I outline Ten Simple Rules to follow when writing an algorithmic bioinformatics conference paper to avoid having it rejected.

As computer scientists working in bioinformatics/computational biology, we often face the challenge of coming up with an algorithm to answer a biological question. This occurs in many areas, such as variant calling, alignment and assembly. In this tutorial, we use the example of the genome assembly problem to demonstrate how to go from a question in the biological realm to a solution in the computer science realm. We show the modeling process step-by-step, including all the intermediate failed attempts. Please note this is not an introduction to how genome assembly algorithms work and, if treated as such, would be incomplete and unnecessarily long-winded.

Motivation: Genotyping a set of variants from a database is an important step for identifying known genetic traits and disease-related variants within an individual. The growing size of variant databases as well as the high depth of sequencing data poses an efficiency challenge. In clinical applications, where time is crucial, alignment-based methods are often not fast enough. To fill the gap, Shajii et al. propose LAVA, an alignment-free genotyping method which is able to more quickly genotype single nucleotide polymorphisms (SNPs); however, there remains large room for improvements in running time and accuracy. Results: We present the VarGeno method for SNP genotyping from Illumina whole genome sequencing data. VarGeno builds upon LAVA by improving the speed of k-mer querying as well as the accuracy of the genotyping strategy. We evaluate VarGeno on several read datasets using different genotyping SNP lists. VarGeno performs 7-13 times faster than LAVA with similar memory usage, while improving accuracy. Availability and implementation: VarGeno is freely available at: https://github.com/medvedevgroup/vargeno. Supplementary information: Supplementary data are available at Bioinformatics online.

In this article, we consider the following problem. Given a directed graph G , output all walks of G that are sub-walks of all closed edge-covering walks of G . This problem was first considered by Tomescu and Medvedev (RECOMB 2016), who characterized these walks through the notion of omnitig . Omnitigs were shown to be relevant for the genome assembly problem from bioinformatics, where a genome sequence must be assembled from a set of reads from a sequencing experiment. Tomescu and Medvedev (RECOMB 2016) also proposed an algorithm for listing all maximal omnitigs, by launching an exhaustive visit from every edge. In this article, we prove new insights about the structure of omnitigs and solve several open questions about them. We combine these to achieve an O ( nm )-time algorithm for outputting all the maximal omnitigs of a graph (with n nodes and m edges). This is also optimal, as we show families of graphs whose total omnitig length is Ω( nm ). We implement this algorithm and show that it is 9--12 times faster in practice than the one of Tomescu and Medvedev (RECOMB 2016).

We present MetaPartMin and MetaPart, two new lightweight parallel metagenomic read partitioning strategies. Metagenomic data partitioning can aid the concurrent de novo assembly of partitions. Prior read partitioning methods tend to create a giant component of reads. We avoid this problem with new heuristics amenable to statically load-balanced parallelization. Our strategies require enumerating and sorting k-mers and minimizers from the input read sequences, and traversing an implicit graph to identify components. MetaPartMin uses minimizers to significantly lower aggregate main memory use, thereby enabling the processing of massive datasets on a modest number of compute nodes. All steps in our strategies exploit hybrid multicore and distributed-memory parallelism. We demonstrate scaling and efficiency on a collection of large-scale datasets. MetaPartMin can process a 1.25 terabase soil metagenome in 6 minutes on just 32 Intel Skylake nodes (48 cores each) of the Stampede2 supercomputer, and a 252 gigabase soil metagenome in 54 seconds on 16 Stampede2 Skylake nodes. The source code is available at https://github.com/vasupsu/MetaPart.

Motivation: The haploid mammalian Y chromosome is usually under-represented in genome assemblies due to high repeat content and low depth due to its haploid nature. One strategy to ameliorate the low coverage of Y sequences is to experimentally enrich Y-specific material before assembly. As the enrichment process is imperfect, algorithms are needed to identify putative Y-specific reads prior to downstream assembly. A strategy that uses k-mer abundances to identify such reads was used to assemble the gorilla Y. However, the strategy required the manual setting of key parameters, a time-consuming process leading to sub-optimal assemblies. Results: We develop a method, RecoverY, that selects Y-specific reads by automatically choosing the abundance level at which a k-mer is deemed to originate from the Y. This algorithm uses prior knowledge about the Y chromosome of a related species or known Y transcript sequences. We evaluate RecoverY on both simulated and real data, for human and gorilla, and investigate its robustness to important parameters. We show that RecoverY leads to a vastly superior assembly compared to alternate strategies of filtering the reads or contigs. Compared to the preliminary strategy used by Tomaszkiewicz et al., we achieve a 33% improvement in assembly size and a 20% improvement in the NG50, demonstrating the power of automatic parameter selection. Availability and implementation: Our tool RecoverY is freely available at https://github.com/makovalab-psu/RecoverY. Contact: [email protected] or [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

Genome assembly is the problem of reconstructing a genome sequence from a set of reads from a sequencing experiment. Typical formulations of the assembly problem admit in practice many genomic reconstructions, and actual genome assemblers usually output contigs, namely substrings that are promised to occur in the genome. To bridge the theory and practice, Tomescu and Medvedev [RECOMB 2016] reformulated contig assembly as finding all substrings common to all genomic reconstructions. They also gave a characterization of those walks (omnitigs) that are common to all closed edge-covering walks of a (directed) graph, a typical notion of genomic reconstruction. An algorithm for listing all maximal omnitigs was also proposed, by launching an exhaustive visit from every edge. In this paper, we prove new insights about the structure of omnitigs and solve several open questions about them. We combine these to achieve an O(nm)-time algorithm for outputting all the maximal omnitigs of a graph (with n nodes and m edges). This is also optimal, as we show families of graphs whose total omnitig length is Omega(nm). We implement this algorithm and show that it is 9-12 times faster in practice than the one of Tomescu and Medvedev [RECOMB 2016].

MOTIVATION: de Bruijn graphs have been proposed as a data structure to facilitate the analysis of related whole genome sequences, in both a population and comparative genomic settings. However, current approaches do not scale well to many genomes of large size (such as mammalian genomes). RESULTS: In this article, we present TwoPaCo, a simple and scalable low memory algorithm for the direct construction of the compacted de Bruijn graph from a set of complete genomes. We demonstrate that it can construct the graph for 100 simulated human genomes in less than a day and eight real primates in < 2 h, on a typical shared-memory machine. We believe that this progress will enable novel biological analyses of hundreds of mammalian-sized genomes. AVAILABILITY AND IMPLEMENTATION: Our code and data is available for download from github.com/medvedevgroup/TwoPaCo. CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Motivation: Small variant calling is an important component of many analyses, and, in many instances, it is important to determine the set of variants which appear in multiple callsets. Variant matching is complicated by variants that have multiple equivalent representations. Normalization and decomposition algorithms have been proposed, but are not robust to different representation of complex variants. Variant matching is also usually done to maximize the number of matches, as opposed to other optimization criteria. Results: We present the VarMatch algorithm for the variant matching problem. Our algorithm is based on a theoretical result which allows us to partition the input into smaller subproblems without sacrificing accuracy. VarMatch is robust to different representation of complex variants and is particularly effective in low complexity regions or those dense in variants. VarMatch is able to detect more matches than either the normalization or decomposition algorithms on tested datasets. It also implements different optimization criteria, such as edit distance, that can improve robustness to different variant representations. Finally, the VarMatch software provides summary statistics, annotations and visualizations that are useful for understanding callers' performance. Availability and Implementation: VarMatch is freely available at: https://github.com/medvedevgroup/varmatch. Contact: [email protected] or [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

MOTIVATION: As the quantity of data per sequencing experiment increases, the challenges of fragment assembly are becoming increasingly computational. The de Bruijn graph is a widely used data structure in fragment assembly algorithms, used to represent the information from a set of reads. Compaction is an important data reduction step in most de Bruijn graph based algorithms where long simple paths are compacted into single vertices. Compaction has recently become the bottleneck in assembly pipelines, and improving its running time and memory usage is an important problem. RESULTS: We present an algorithm and a tool bcalm 2 for the compaction of de Bruijn graphs. bcalm 2 is a parallel algorithm that distributes the input based on a minimizer hashing technique, allowing for good balance of memory usage throughout its execution. For human sequencing data, bcalm 2 reduces the computational burden of compacting the de Bruijn graph to roughly an hour and 3 GB of memory. We also applied bcalm 2 to the 22 Gbp loblolly pine and 20 Gbp white spruce sequencing datasets. Compacted graphs were constructed from raw reads in less than 2 days and 40 GB of memory on a single machine. Hence, bcalm 2 is at least an order of magnitude more efficient than other available methods. AVAILABILITY AND IMPLEMENTATION: Source code of bcalm 2 is freely available at: https://github.com/GATB/bcalm CONTACT: [email protected].

MOTIVATION: Genome assembly tools based on the de Bruijn graph framework rely on a parameter k, which represents a trade-off between several competing effects that are difficult to quantify. There is currently a lack of tools that would automatically estimate the best k to use and/or quickly generate histograms of k-mer abundances that would allow the user to make an informed decision. RESULTS: We develop a fast and accurate sampling method that constructs approximate abundance histograms with several orders of magnitude performance improvement over traditional methods. We then present a fast heuristic that uses the generated abundance histograms for putative k values to estimate the best possible value of k. We test the effectiveness of our tool using diverse sequencing datasets and find that its choice of k leads to some of the best assemblies. AVAILABILITY: Our tool KmerGenie is freely available at: http://kmergenie.bx.psu.edu/.

MOTIVATION: The importance of fast and affordable DNA sequencing methods for current day life sciences, medicine and biotechnology is hard to overstate. A major player is Ion Torrent, a pyrosequencing-like technology which produces flowgrams--sequences of incorporation values--which are converted into nucleotide sequences by a base-calling algorithm. Because of its exploitation of ubiquitous semiconductor technology and innovation in chemistry, Ion Torrent has been gaining popularity since its debut in 2011. Despite the advantages, however, Ion Torrent read accuracy remains a significant concern. RESULTS: We present FlowgramFixer, a new algorithm for converting flowgrams into reads. Our key observation is that the incorporation signals of neighboring flows, even after normalization and phase correction, carry considerable mutual information and are important in making the correct base-call. We therefore propose that base-calling of flowgrams should be done on a read-wide level, rather than one flow at a time. We show that this can be done in linear-time by combining a state machine with a Viterbi algorithm to find the nucleotide sequence that maximizes the likelihood of the observed flowgram. FlowgramFixer is applicable to any flowgram-based sequencing platform. We demonstrate FlowgramFixer's superior performance on Ion Torrent Escherichia coli data, with a 4.8% improvement in the number of high-quality mapped reads and a 7.1% improvement in the number of uniquely mappable reads. AVAILABILITY: Binaries and source code of FlowgramFixer are freely available at: http://www.cs.tau.ac.il/~davidgo5/flowgramfixer.html.

MOTIVATION: The continuing improvements to high-throughput sequencing (HTS) platforms have begun to unfold a myriad of new applications. As a result, error correction of sequencing reads remains an important problem. Though several tools do an excellent job of correcting datasets where the reads are sampled close to uniformly, the problem of correcting reads coming from drastically non-uniform datasets, such as those from single-cell sequencing, remains open. RESULTS: In this article, we develop the method Hammer for error correction without any uniformity assumptions. Hammer is based on a combination of a Hamming graph and a simple probabilistic model for sequencing errors. It is a simple and adaptable algorithm that improves on other tools on non-uniform single-cell data, while achieving comparable results on normal multi-cell data. AVAILABILITY: http://www.cs.toronto.edu/~pashadag. CONTACT: [email protected].

High-throughput sequencing (HTS) technologies are revolutionizing the way biologists acquire and analyze genomic data. HTS instruments, such as the Illumina Genomic Analyzer and the Applied Biosystems SOLiD System, are currently able to sequence tens of gigabases per week, at a cost of 200-fold less than previous methods, potentially enabling the routine sequencing of human and other genomes. Over the last few years the promise of HTS technologies has become a reality, however, realizing that the full promise of these technologies requires the development of computational methods that can analyze the resulting datasets to infer biological meaning. HTS can be used to study many biological problems, including assembling genomes of new organisms, identifying genome variation within a population, discovering novel transcripts, analyzing gene expression, discerning the regulatory mechanisms behind the expression levels and profiling the metagenome of a community. While many HTS datasets are readily available, the main bottleneck in the analysis is the dearth of computational methods that are able to directly answer biologists' questions from these datasets. The Special Interest Group on Short Read Sequencing and Algorithms (Short-SIG), held in conjunction with the Intelligent Systems in Molecular Biology (ISMB) conference, is a meeting that brings together computational biologists interested in analyzing these HTS datasets. The first Short-SIG, held in Toronto in 2008, brought together over 120 attendees, and featured 18 podium presentations, with many of them addressing the computational problems of read mapping—the alignment of reads to a larger reference genome—and assembly—the de novo generation of the genome of an organism from short read data. During the year that followed, significant progress has been made in these fields, and the topic of the 2009 meeting, held in Stockholm on June 28, concentrated on the development of methods that can analyze the resulting read mappings and assemblies to infer biological meaning. The meeting brought together over 200 researchers, and featured 17 platform presentations selected from 27 abstracts and 17 full paper submissions. The keynote address at the SIG was delivered by Dr Edwin Cuppen of the Hubrecht Laboratory (Utrecht, The Netherlands). The paper submissions were handled in coordination with the Bioinformatics journal, and a physical copy of the Bioinformatics ‘virtual issue’ on HTS, featuring papers published on this topic in Bioinformatics over the past year, was presented to all meeting attendees. Bioinformatics also sponsored a best paper award for the conference, given to Kai Ye and his co-authors for the paper ‘Pindel: a pattern growth approach to detect break points of large deletions and medium sized insertions from paired-end short reads’, as well as an award for a paper chosen from the ‘virtual issue’, that was given to Cole Trapnell and colleagues for ‘TopHat: discovering splice junctions with RNA-Seq’. One of the most prominent applications of HTS is the resequencing of human genomes. Genomic variants are discovered by mapping reads from a donor genome to a reference human genome (typically the NCBI assembly), and the resulting mappings are then analyzed to identify differences between the donor and the reference. The SIG saw eight presentations on variation identification, including variants of all sizes—from SNPs to larger, structural variants. From the SNP discovery perspective, Adrian Dalca presented VARiD, a generalized framework for calling SNPs from both regular (letter-space) reads and di-base encoded (color-space) data. Sohrab Shah presented SNVmix, a Bayesian mixture model-based method for discovering single nucleotide variants from somatic tissues, where the observed alleles and their ratios may vary due to adjacent tissues being present in a biopsy. There were also presentations on variation discovery methods from the two leading HTS technology manufacturers, Illumina and Life Technologies (Applied Biosystems). Dirk Evers of Illumina spoke of recent improvements to the CASAVA framework that allows for more accurate discovery of variants from long reads, especially indel and copy number variants. He presented the results of CASAVA on recently sequenced paired tumor/normal genomes from a melanoma cell line. Fiona C. L. Hyland, from Life Technologies, described diBayes, a Bayesian framework for SNP discovery from color-space data, and presented an extensive analysis of a SOLiD human dataset, including discovered SNPs, small indels and larger structural variants. The advent of high-throughput sequencing has for the first time allowed large, cost-effective studies to detect larger, structural variants. Such variation has been associated with numerous diseases, including autism, schizophrenia and cancer, making their discovery an important challenge for computational biologists. Several talks at the SIG focused on the development of novel methods for discovery of such variants. Kai Ye presented a method called Pindel, which, by anchoring the mates of nonmapping reads to a genomic location, was able to use split-mapping to detect deletion events as large as 10 kb with base-level precision (Ye et al., 2009). This paper was the winner of the best SIG paper award, sponsored by Bioinformatics. Seunghak Lee and Weldon Whitener showed how to detect smaller indels from pair-end data by using the distribution of insert sizes of all matepairs that span each genomic location. Paul Medvedev described a way that the depth-of-coverage signal can be combined with pair-end mapping-based techniques to detect copy number variants within segmental duplications. Overall, this year has seen the detection of structural variation come to the forefront of algorithmic research, and the next year will hopefully bring about more fully developed biologist-friendly tools. Another exciting application of HTS technologies is RNA sequencing. RNA sequencing is currently used for several applications, including RNA expression, de novo transcriptome sequencing for nonmodel organisms and novel transcript discovery; however, computational methods for the analysis of this data are in their infancy. For RNA and microRNA expression profiling, HTS has significant advantages compared with microarray methods in that it is better able to identify quantities of very common and very rare transcripts. Short-SIG featured five talks addressing various computational problems in RNA sequencing. Cole Trapnell presented his work on BowTie (Trapnell et al., 2009), a tool to map reads from RNA sequencing to a reference genome, while allowing for split-reads where the two ends of a read map in different locations (due to exon splicing). While the original paper was published as part of the ‘virtual issue’, the presentation included new improvements to the tool. Jan Prins presented MapSplice, a RNA mapping tool that is similar to TopHat, but includes the ability to consider noncanonical splice sites. Inanc Birol presented a version of the ABySS assembler for de novo mRNA assembly. ABySS was the first tool to attempt de novo assembly of the human genome, and in their presentation they presented the first results on de novo assembly of human transcriptome data. Finally, three presentations demonstrated methods to mine RNA-seq data for specific biomedical phenomena: Regina Bohnert presented an algorithm for identifying alternative transcripts and their expression levels, Chol-Hee Jung presented an analysis of combining multiple Drosophila RNA-seq datasets in order to discover novel noncoding RNAs, and Gerald Quon showed that using the ISOLATE framework (Quon and Morris, 2009), mRNA expression levels can be used to identify the tissue of origin in metastasized tumors. The final session of the SIG was devoted to a variety of classical and newly upcoming HTS applications. Bas Dutilh presented a method for mapping metagenomic reads to a reference genome, where the reference is changed during the mapping process to more accurately represent the community consensus genome, thus allowing a larger fraction of reads to map (Dutilh et al., 2009). Juliane Klein presented LOCAS, an assembler for short read data that is targeted toward low-coverage datasets, and significantly outperforms previous methods in this context. The last two presentations addressed the statistical issues underlying HTS. Su Yeon Kim described statistical foundation of designing association studies with HTS, specifically the use of a combination of pooled and unpooled samples from a number of individuals to design association studies. Adam Kowalczyk showed that it is possible to develop univariate statistical tests to compute the likelihood that two distributions of short read datasets are identical (P-values) based on the Poisson approximation to the binomial distribution. The SIG ended with a keynote address by Dr Edwin Cuppen of the Hubrecht Laboratory, in Utrecht, The Netherlands. His presentation demonstrated both some interesting advantage of short read sequencing, such as the ability of CHiP-seq experiments to identify which genes are regulated by specific distal enhancers, and some key limitations, for example, that RNA-seq, while capable of profiling relative transcript levels in different conditions, is unable to reconstruct actual transcript levels due to biases introduced during sample preparation. In addition to the podium presentations, many Short-SIG attendees used the opportunity to discuss collaborations and the general direction of the field. Clearly, the increase in read length (only 25–35 bp 2 years ago and 50–100 bp today) is making it difficult to develop timely tools, as the problems associated with different length reads are quite dissimilar. Illumina and SOLiD reads will very soon be as long as 454 reads were a few years ago, and this dynamics is forcing bioinformaticians to rethink algorithms developed only a year ago. Similarly, the increasing throughput of the sequencing platforms is requiring the scaling of the algorithms to larger datasets. Bioinformatics remains one of the key bottlenecks in HTS data analysis, with datasets created at a faster rate than can be effectively analyzed, and few tools providing ‘one stop shopping’ for the complete analysis of a single dataset. Addressing these shortcomings is a key step to realizing the full promise of HTS technologies. Conflict of Interest: none declared.

The seat reservation problem is the problem of assigning passengers to seats on a train with n seats and k stations enroute in an online manner. The performance of algorithms for this problem is studied using the relative worst order ratio, a fairly new measure for the quality of online algorithms, which allows for direct comparisons between algorithms. This study has yielded new separations between algorithms. For example, for both variants of the problem considered, using the relative worst order ratio, First-Fit and Best-Fit are shown to be better than Worst-Fit.

Distributed fair queueing in shared-medium ad hoc wireless networks is non-trivial because of the unique design challenges in such networks, such as location-dependent contention, distributed nature of ad hoc fair queueing, channel spatial reuse, and scalability in the presence of node mobility. In this paper, we seek to devise new distributed, localized, scalable and efficient solutions to this problem. We first analyze an ideal centralized fair queueing algorithm developed for ad hoc networks, and extract the desired global properties that the localized algorithms should possess. We then propose three localized fair queueing models, in which local schedulers self-coordinate their local interactions and collectively achieve the desired global properties. We further describe a novel implementation of the proposed models within the framework of the popular CSMA/CA paradigm and address several practical issues. Our simulations and analysis demonstrate the effectiveness of our proposed design.