Skip to main content
10 votes
Accepted

How are MACS2's narrow peak and broad peak algorithms different?

The key function is call_broadpeaks: The description attached to the function says: This function try to find enriched regions within which, scores are ...
Daniel Kim's user avatar
8 votes
Accepted

Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?

A rolling hash function for DNA sequences called ntHash has recently been published in Bioinformatics and the authors dealt with reverse complements: Using this table, we can easily compute the ...
Karel Břinda's user avatar
8 votes

Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?

Let f and r be two integers. They always keep the k-mer on the forward and reverse strand, respectively. At a new base ...
user172818's user avatar
  • 6,575
6 votes

Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?

If your goal is to minimise storage by just having one hash per kmer and its reverse complement, there is a simple solution for non-rolling hashes. For any sequence S, you compute and store the hash ...
BaCh's user avatar
  • 734
5 votes
Accepted

mapping heteryzygous kmers on a genome

I don't know if this is the best answer, but one quick-n-dirty approach I commonly use involves tweaking bwa mem to report only perfect matches. So in your case, ...
Daniel Standage's user avatar
5 votes
Accepted

Is the algorithm of the STAR RNA Seq-Aligner similar to the Knuth-Morris-Pratt string matching algorithm?

No, STAR isn't using the KMP algorithm or a modification of it. The KMP algorithm is an online exact pattern matching algorithm. It does (linear time) pre-processing on the query and then finds all ...
nomad's user avatar
  • 482
4 votes

Books on bioinformatics algorithms

Here are a couple books I'd recommend: Dan Gusfield's Algorithms on Strings, Trees, and Sequences is a deep and wide treatment of aligning, searching, and processing strings, trees, and sequences. ...
Alex Reynolds's user avatar
4 votes

Getting all NNI trees of a parsimony tree

As I've studies the 'TreeConstruction' module of Biopython, I came to know that '_get_neighbors' method is the one that is used ...
Sidra Younas's user avatar
4 votes
Accepted

Efficiently aligning a lot of reads on the same small reference sequence

I would suggest using a whole genome aligner like BWA or BOWTIE2 and swapping out the whole genome reference with your specific reference. These alignment algorithms are designed to align large ...
Bioathlete's user avatar
  • 2,584
4 votes
Accepted

How does htslib/samtools access optional BAM fields?

How does htslib access each of the optional fields, given this structure? htslib uses a macro, bam_get_aux, for this purpose. You can check the source code of this ...
Konrad Rudolph's user avatar
4 votes

Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?

At its easiest, you just store the forward ($F$) and reverse ($R$) hash value. You update the forward hash value by conventional means, e.g. bit-shifting the base value into its lower bits: $$ F_{n +...
Konrad Rudolph's user avatar
4 votes
Accepted

How is a principal component analysis for population structure made from a bam or other alignment file?

In general, the process works as such: Variants are found at a number of loci in each sample (missing loci are often imputed). Each sample is scored at each locus, often according to the number of ...
Devon Ryan's user avatar
  • 19.7k
4 votes

Estimate the length of poly-A tails from randomly-primed RNAseq data

Can’t be done. If you already sequenced then I’m afraid the money is wasted (unless of course the data is good for something else). The standard Illumina basecaller doesn’t deal well with ...
Konrad Rudolph's user avatar
4 votes

mapping heteryzygous kmers on a genome

Indeed, with suffix arrays, you can map a kmer in ~0.0007s. The way to go is to build a suffix array (for instance using PySAIS package) and then do a convoluted binary search of the four possible ...
Kamil S Jaron's user avatar
4 votes
Accepted

Algorithm for counting neighbors

The usual method is dividing the space into cells, in your case 7Å cubes, assigning atoms to cells, and searching for neighbors only in 3x3x3=27 cells. This method is described in Wikipedia as cell ...
marcin's user avatar
  • 1,261
4 votes
Accepted

Why do we need seondary structure detection algorithms?

Right, that's easy PDB is strictly experimentally derived structures, for example crystal structures or NMR. There are at least three very good reasons, There are billions of proteins. Even small ...
M__'s user avatar
  • 12.8k
3 votes
Accepted

Estimate the length of poly-A tails from randomly-primed RNAseq data

Just look for polyA tracts at the end of sequences, and count them if they're larger than ~18 bases. I've done this with MinION cDNA reads by mapping the polyA adapter sequence (with an elongated ...
gringer's user avatar
  • 14.7k
3 votes

How does htslib/samtools access optional BAM fields?

In a BAM file, all of the auxiliary tags (the optional fields you refer to) are held what is effectively a void * field, one after the other. Each entry within this ...
Devon Ryan's user avatar
  • 19.7k
3 votes

Books on bioinformatics algorithms

If you're interested in variant calling, I just co-authored an O'Reilly book called Genomics in the Cloud that covers the GATK Best Practices from a scientific standpoint (germline and somatic short ...
Geraldine_VdAuwera's user avatar
3 votes

Books on bioinformatics algorithms

Bioinformatics and Functional Genomics by Jonathan Pevsner is a good one, he goes over the biology as well as how the algorithms work, and provides real-world examples.
Imer Muhović's user avatar
3 votes
Accepted

What does it mean by "PC" in this article?

Answer from @user438383, @matteo-ferla and @m, converted from comments [anyone, feel free to edit this answer to improve it]: According to the intro it means 'pseudocenter'. All measurements are ...
3 votes
Accepted

What is the cutoff distance in this algorithm?

The 43 features are listed in the supplementary materials on page 4. For example, ...
gilleain's user avatar
  • 388
3 votes

Help Understanding the Greedy Motif Search Algorithm from Textbook

I have been similarly stuck on the Bioinformatics textbook motif problems in Rosalind, mostly because the documentation included with the problems is sparse, useless, or nonexistent. The mouseover for ...
gringer's user avatar
  • 14.7k
3 votes
Accepted

Help Understanding the Greedy Motif Search Algorithm from Textbook

I figured this out after rereading the chapter a few times. I am going to try my best to describe the solution here for anyone else who runs into this issue, since I don't think this was meant to be ...
David Rouleau's user avatar
2 votes

Do any computational phylogenetic methods enable the specification of ancestral states?

For maximum parsimony, Fitch's method seems simple and intuitive, and can be done in the R phangorn package: Fitch, Walter M. (1971). "Toward Defining the Course of Evolution: Minimum Change for a ...
Jay Moore's user avatar
  • 1,012
2 votes
Accepted

Non-random access on a fastq file

You don't have a RAM problem because you only have about: 10-20 reads that I want to access from each file. Please go for (2). If you are concerned about RAM usage, you may selectively write some ...
SmallChess's user avatar
  • 2,729
2 votes
Accepted

How is consensus alignment for OLC assembly usually implemented?

For short reads, mainstream assemblers don't have a consensus step. The contig path directly spells the consensus sequence. For long reads, the most popular way to derive a consensus is via partial-...
user172818's user avatar
  • 6,575
2 votes

How do I interpret the function O(f^-2 log n) in Shekhar et al. (2017)?

Big O notation means "of the order of". Thus $\mathcal{O}(f^{-2} \log{n})$ means that the number of trees required goes with $\log{n}$ for number of species (i.e. if you square the number of genes, ...
Ian Sudbery's user avatar
  • 3,331
2 votes
Accepted

What are some of the major questions pursued by the field bioinformatics?

Welcome! Bioinformatics is just a term that describes an approach to doing biology. People who use ( DNA sequencing/genomics/protein informatics + programming ) to answer biological questions are ...
conchoecia's user avatar
  • 3,181
2 votes
Accepted

How does Li and Durbin's BWA paper compare alignment programs on real data?

For the simulated reads, they know exactly where the reads came from, because they are able to create that link at the time paired-end reads are generated from the genome. Those simulated reads would ...
gringer's user avatar
  • 14.7k

Only top scored, non community-wiki answers of a minimum length are eligible