BOL: Related items

Mercator: Multiple Whole-Genome Orthology Map Construction

Jit — Tue, 19 May 2020 16:46:22 -0500

Whole-genome homology maps attempt to identify the evolutionary relationships between and within multiple genomes. The term "syntenic" is often used to describe regions of multiple genomes that are believed to have evolved from the same region in an ancestral genome. However, it has been pointed out that this use of the term is incorrect (Passarge et al. 1999) and thus we will use the terms "homologous", "orthologous", and "paralogous" instead. Ideally, given K genomes, we would like to identify all orthologous genomic regions as well as paralogous regions within each genome and hypothetical ancestral genome. Maps listing these relationships are extremely valuable to researchers performing comparative analyses of genomic sequence. Here we present our initial work in the form a program called Mercator that constructs orthology maps between multiple whole genomes.

Address of the bookmark: https://www.biostat.wisc.edu/~cdewey/mercator/

MIKE: an ultrafast, assembly-, and alignment-free approach for phylogenetic tree construction

Abhi — Mon, 08 Apr 2024 06:19:52 -0500

MIKE (MinHash-based k-mer algorithm). This algorithm is designed for the swift calculation of the Jaccard coefficient directly from raw sequencing reads and enables the construction of phylogenetic trees based on the resultant Jaccard coefficient. Simulation results highlight the superior speed of MIKE compared to existing state-of-the-art methods. We used MIKE to reconstruct a phylogenetic tree, incorporating 238 yeast, 303 Zea, 141 Ficus, 67 Oryza, and 43 Saccharum spontaneum samples. MIKE demonstrated accurate performance across varying evolutionary scales, reproductive modes, and ploidy levels, proving itself as a powerful tool for phylogenetic tree construction.

Address of the bookmark: https://github.com/Argonum-Clever2/mike

Krona

Jit — Wed, 22 Mar 2017 04:47:35 -0500

Krona allows hierarchical data to be explored with zooming, multi-layered pie charts. Krona charts can be created using an Excel template or KronaTools, which includes support for several bioinformatics tools and raw data formats. The interactive charts are self-contained and can be viewed with any modern web browser (see Browser support).

Address of the bookmark: https://github.com/marbl/Krona/wiki

Π-cyc: A Reference-free SNP Discovery Application using Parallel Graph Search

Jit — Tue, 28 Jan 2020 03:34:23 -0600

Reference free SNP search for comparative population genomics: multiple samples run simultanously. **experimental phase, compiles and runs with OpenMPI-1.8.8 with Intel Compiler only

Cycles enumeration (aka Bubbles) as part of de novo de bruijn graphs assembly using colours can be unpractical for large error prone genomes which makes the assembly process produce an excessive number of false positive cycles. Our solution is to search the graph in multicores shared memory parallel mode using graph decomposition then use filtering method to generate good quality SNPs.

https://arxiv.org/abs/1809.06700

https://github.com/redayounsi/2KP2P

/2kp2omp/bin/main_2kp2_K63_C2 -i fastq_files.txt -o fungus_bub.fasta -r stat_fungus.txt -c cov_fungus_hash.txt -k 63 -h 20 -b 100 -g 600 -l 100 -f 16 -t 5.0 -x 1 -v 0 -p 1 -y 1 -u 1

Address of the bookmark: https://github.com/redayounsi/2KP2P

String graph based genome assembly software and tools !

Rahul Nayak — Tue, 19 Dec 2017 17:17:38 -0600

In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". String graphs were first proposed by E. W. Myers in a 2005 publication. In recent Genome Research paper describing an innovative approach for assembling large genomes from NGS data caught our attention for several reasons. i) it give different "string graph" prospective of long lasting genome assembly problem ii) the paper is coauthored by Jared Simpson, the developer of ABySS assembler and Richard Durbin. iii) Simpson-Durbin algorithm is that it does not rely on de Bruijn graphs, and instead employs a different graph construction approach called ‘string graph’.

Following are the genome assembly tools based on string graph:

1.SGA (String Graph Assembler) https://github.com/jts/sga

Assembles large genomes from high coverage short read data. SGA is designed as a modular set of programs, which are used to form an assembly pipeline. SGA implements a set of assembly algorithms based on the FM-index. As the FM-index is a compressed data structure, the algorithms are very memory efficient. The SGA assembly has three distinct phases. The first phase corrects base calling errors in the reads. The second phase assembles contigs from the corrected reads. The third phase uses paired end and/or mate pair data to build scaffolds from the contigs. The output of this software is a PDF report that allows the properties of the genome and data quality to be visually explored. By providing more information to the user at the start of an assembly project, this software will help increase awareness of the factors that make a given assembly easy or difficult, assist in the selection of software and parameters and help to troubleshoot an assembly if it runs into problems.

2. SAGE: String-overlap Assembly of GEnomes https://github.com/lucian-ilie/SAGE2

SAGE, for de novo genome assembly. As opposed to most assemblers, which are de Bruijn graph based, SAGE uses the string-overlap graph. SAGE builds upon great existing work on string-overlap graph and maximum likelihood assembly, bringing an important number of new ideas, such as the efficient computation of the transitive reduction of the string overlap graph, the use of (generalized) edge multiplicity statistics for more accurate estimation of read copy counts, and the improved use of mate pairs and min-cost flow for supporting edge merging. The assemblies produced by SAGE for several short and medium-size genomes compared favourably with those of existing leading assemblers.

3. FSG: Fast String Graph

The new integrated assembler has been assessed on a standard benchmark, showing that fast string graph (FSG) is significantly faster than SGA while maintaining a moderate use of main memory, and showing practical advantages in running FSG on multiple threads. Moreover, we have studied the effect of coverage rates on the running times.

4. BASE https://github.com/dhlbh/BASE

It enhances the classic seed-extension approach by indexing the reads efficiently to generate adaptive seeds that have high probability to appear uniquely in the genome. Such seeds form the basis for BASE to build extension trees and then to use reverse validation to remove the branches based on read coverage and paired-end information, resulting in high-quality consensus sequences of reads sharing the seeds. Such consensus sequences are then extended to contigs. BASE is a practically efficient tool for constructing contig, with significant improvement in quality for long NGS reads. It is relatively easy to extend BASE to include scaffolding.

5. Fermi https://github.com/lh3/fermi/

Fermi is a de novo assembler with a particular focus on assembling Illumina short sequence reads from a mammal-sized genome. In addition to the role of a typical assembler, fermi also aims to preserve heterozygotes which are often collapsed by other assemblers. Its ultimate goal is to find a minimal set of unitigs to represent all the information in raw reads.

If you want to learn about String Graph assembler, please read the following papers -

i) The Fragment Assembly String Graph - E. W. Myers

This paper describes the String Graph concept.

ii) Efficient construction of an assembly string graph using the FM-index - Jared T. Simpson and Richard Durbin

This earlier paper from Simpson and Durbin

iii) Efficient de novo assembly of large genomes using compressed data structures - Jared T. Simpson and Richard Durbin

wtdbg2: A fuzzy Bruijn graph approach to long noisy reads assembly

BioStar — Mon, 04 Feb 2019 04:53:47 -0600

Wtdbg2 is a de novo sequence assembler for long noisy reads produced by PacBio or Oxford Nanopore Technologies (ONT). It assembles raw reads without error correction and then builds the consensus from intermediate assembly output.

./wtdbg2 -x rs -g 4.6m -t 16 -i reads.fa.gz -fo prefix
./wtpoa-cns -t 16 -i prefix.ctg.lay.gz -fo prefix.ctg.fa

Address of the bookmark: https://github.com/ruanjue/wtdbg2

GraphPath: A graph attention model for molecular stratification with interpretability based on the pathway-pathway interaction network

LEGE — Wed, 27 Mar 2024 20:51:21 -0500

Achieving accurate and interpretable clinical predictions requires paramount attention to thoroughly characterizing patients at both the molecular and biological pathway levels. In this paper, we present GraphPath, a biological knowledge-driven graph neural network with multi-head self-attention mechanism that implements the pathway-pathway interaction network. We train GraphPath to classify the cancer status of patients with prostate cancer based on their multi-omics profiling.

Address of the bookmark: https://github.com/amazingma/GraphPath

A Subway Map for the Genome

LEGE — Fri, 04 Sep 2026 04:14:14 -0500

Maya was looking at a genome graph on her computer. There were nodes, branches, and paths going in every direction.

“It’s like a subway map,” she said, “but for DNA.”

That idea is exactly what Sequence Tube Map brings to life.

Instead of showing a genome as one long, confusing sequence, it displays different genomic paths like routes on a metro map. Where sequences are shared, the paths travel together. Where genetic variation occurs, they branch into different routes and may join again later.

This makes complex genome graphs much easier to explore.

Maya could now see how different haplotypes moved through the same genomic region and where they took different paths. She could even view sequencing reads mapped onto the graph, helping her understand what was happening in regions with genetic variation.

What once looked like a tangled network now looked like a journey.

Sequence Tube Map turns the complexity of graph genomes into a visual story—making it easier for scientists to see how DNA can take different routes.

Read more at https://github.com/vgteam/sequencetubemap

and

https://academic.oup.com/bioinformatics/article/35/24/5318/5542397

Demo at https://vgteam.github.io/sequenceTubeMap/

AlignGraph: algorithm for secondary de novo genome assembly guided by closely related references

Manisha Mishra — Tue, 17 Apr 2018 16:21:20 -0500

AlignGraph is a software that extends and joins contigs or scaffolds by reassembling them with help provided by a reference genome of a closely related organism.

Using AlignGraph

AlignGraph --read1 reads_1.fa --read2 reads_2.fa --contig contigs.fa --genome genome.fa --distanceLow distanceLow --distanceHigh distancehigh --extendedContig extendedContigs.fa --remainingContig remainingContigs.fa [--kMer k --insertVariation insertVariation --coverage coverage --part p --fastMap --ratioCheck --iterativeMap --misassemblyRemoval --resume]

Address of the bookmark: https://github.com/baoe/AlignGraph

Hercules: a profile HMM-based hybrid error correction algorithm for long reads

Jit — Mon, 20 Aug 2018 14:14:11 -0500

Choosing whether to use second or third generation sequencing platforms can lead to trade-offs between accuracy and read length. Several studies require long and accurate reads including de novo assembly, fusion and structural variation detection. In such cases researchers often combine both technologies and the more erroneous long reads are corrected using the short reads. Current approaches rely on various graph based alignment techniques and do not take the error profile of the underlying technology into account. Memory- and time- efficient machine learning algorithms that address these shortcomings have the potential to achieve better and more accurate integration of these two technologies. Results: We designed and developed Hercules, the first machine learning-based long read error correction algorithm. The algorithm models every long read as a profile Hidden Markov Model with respect to the underlying platformtextquoterights error profile. The algorithm learns a posterior transition/emission probability distribution for each long read and uses this to correct errors in these reads. Using datasets from two DNA-seq BAC clones (CH17-157L1 and CH17-227A2), and human brain cerebellum polyA RNA-seq, we show that Hercules-corrected reads have the highest mapping rate among all competing algorithms and highest accuracy when most of the basepairs of a long read are covered with short reads. Availability:

Hercules source code is available at https://github.com/BilkentCompGen/Hercules

Address of the bookmark: https://github.com/BilkentCompGen/Hercules