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
...
- 116
9
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 ...
- 6,485
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 ...
- 1,899
7
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 ...
- 754
5
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 +...
- 4,845
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, ...
- 5,060
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 ...
- 472
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.
...
- 3,125
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 ...
- 503
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 ...
- 2,574
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 ...
- 4,845
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 ...
- 19.6k
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 ...
- 4,845
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 ...
- 5,517
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 ...
- 1,261
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 ...
- 13.8k
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 ...
- 19.6k
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 ...
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 ...
2
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.
- 81
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 ...
- 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 ...
- 2,739
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-...
- 6,485
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, ...
- 3,301
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 ...
- 3,141
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 ...
- 13.8k
2
votes
How does Li and Durbin's BWA paper compare alignment programs on real data?
What they are pairing is the RNAseq data with the reference genome: as the legend of the table 2 says:
The 12.2 million read pairs were mapped to the human genome
These softwares align the same ...
- 4,693
2
votes
How to score how densely bases are distributed along a given oligo?
You could count the number of transitions between an A and a 'not A', and divide this number by the total number of As. You might also need to scale by the sequence length, if you have different ...
- 1,012
2
votes
Accepted
Time complexity of the Neighbors function
Let's first establish a lower bound on any solution:
Given a hamming distance $D$ and an input pattern $P$ of length $N$, there are $\sum_{k=0}^D{N \choose k} 3^k$ other strings within hamming ...
- 810
2
votes
Accepted
How to reconstruct a target string from a large set of overlapping reads
Unless it's not obvious, the problem has no unique solution. An obvious example is a string which uses entirely one character; the problem is then to determine its length, which you can only do ...
- 136
Only top scored, non community-wiki answers of a minimum length are eligible