Questions tagged [algorithms]
The algorithms tag has no usage guidance, but it has a tag wiki.
29
questions
0
votes
0answers
15 views
Help understanding why a particular pair in a set does not form a breakpoint for the Breakpoint Reversal Sort algorithm
S = { 8, 2, 7, 6, 5, 1, 4, 3 }
The sort will be performed on the set including 0 and n+1 to give
S' = { 0, 8, 2, 7, 6, 5, 1, 4, 3, 9 }
My textbook lists the breakpoint subsets as follows:
...
0
votes
1answer
33 views
Directed mutagenesis primer design by back to back PCR of constructs
We're mutating a virus construct (virus-like particle [VLP]) using back to back primer PCR for a VLP construct and want to optimise the primer design.
A regular primer design program (Primer3) isn't ...
0
votes
0answers
27 views
Kinetics “Master Equation”
In stochastic (probabilistic) models, the evolution of a system over time is calculated using a "Master Equation" which also factors the external and internal noise / perturbations in order to more ...
1
vote
2answers
129 views
mapping heteryzygous kmers on a genome
I have a set (a couple of millions) of kmer pairs of known length (usually 21) that I know that are heterozygous in the middle nucleotide. For instance:
...
4
votes
1answer
73 views
Attractor Landscape Analysis
I have come across a modeling toolbox, ATLANTIS, which is able to determine cell fates in silico based on the input models provided. This MATLAB-based toolbox is built on a method called "Attractor ...
1
vote
3answers
55 views
How to score how densely bases are distributed along a given oligo?
Suppose I have a short chain string of oligos, and I want to rate them from 0 to 1 based on how clustered the "A"s are in respect to the chain. For example:
...
4
votes
0answers
40 views
Prediction of prokaryotic origins of replication (ORI)
I want to predict origins of replication (ORI) on hundreds of prokaryotic genomes. The most straight-forward solution would be to use most commonly used tool, Ori-Finder.
It uses integrated gene ...
1
vote
1answer
93 views
Non-random access on a fastq file
There was a nice question on random access on a fastq file, however I have the opposite problem. I want to programatically access non-random fastq entries quickly (using C++).
Say I have several ...
2
votes
1answer
73 views
How is consensus alignment for OLC assembly usually implemented?
Background
In C++ I want to implement a simple class that performs overlap layout consensus assembly but I can not figure out the most logical data structure to use for the consensus alignment step.
...
1
vote
1answer
50 views
How do I interpret the function O(f^-2 log n) in Shekhar et al. (2017)?
The results of Shekhar et al. (2017) "indicate that ASTRAL requires $\mathcal{O}(f^{-2} \log{n})$ gene trees to reconstruct the species tree correctly with high probability where n is the number of ...
0
votes
1answer
42 views
What are some of the major questions pursued by the field bioinformatics? [closed]
I am an occasional user of tools in bioinformatics and I am fascinated by the possibility of uncovering deeper patterns in the biological realm using the help of computer algorithms. Yet I don't know ...
3
votes
0answers
84 views
Histosketch vs Count-Min sketch: preserving similarity
A preprint describing a new tool and its application to microbiome analysis was recently published in bioRxiv[1]. At the core of this new tool, HULK, is a new data structure called a histosketch[2] ...
6
votes
1answer
89 views
Getting all NNI trees of a parsimony tree
I have an aligned protein sequence file which I have been using for reconstructing a parsimonious tree. I am currently using NNITreeSearcher._get_neighbors method from Biopython 1.72 but it's way to ...
4
votes
1answer
77 views
Efficiently aligning a lot of reads on the same small reference sequence
The context: I have a DNA-sequence coding for a protein, about 1500 bp in length. Using NGS, a lot of reads of (mutants of) this same sequence were acquired. All of these reads need to be aligned to ...
1
vote
0answers
26 views
Stand alone chaining tool for existing blast hits?
I have a table of blast hits in a database that I'd like to chain. What is a good choice for a 'stand alone' chaining tool? Is it simple to implement in Perl, for example?
Example 'hit' data is here. ...
4
votes
2answers
81 views
Do any computational phylogenetic methods enable the specification of ancestral states?
Various phylogenetic algorithms estimate ancestral states of a phylogenetic dataset. Is there a way in either maximum parsimony, distance-based methods, or Bayesian inference to indicate what the ...
0
votes
2answers
50 views
Why does `pratchet()` in `phangorn` not find the most parsimonious trees?
I called pratchet() on a dataset with binary values for the characters and it returned a parsimony value of 35. I then calculated the parsimony value for the ...
6
votes
2answers
236 views
How does htslib/samtools access optional BAM fields?
I am confused regarding how various software libraries deal with optional fields in a BAM:
Based upon the BAM specification, there are 11 mandatory fields to a BAM:
...
5
votes
2answers
189 views
Books on bioinformatics algorithms
I'm looking for a book about bioinformatics algorithms, such as alignment, BLAST search, and variant calling.
I'm hoping reading about this subject will give me a deeper understanding of the ...
4
votes
2answers
72 views
How does Li and Durbin's BWA paper compare alignment programs on real data?
Li and Durbin's "Fast and accurate short read alignment with burrows-whleeler transform" found here, says:
We evaluate the performance of BWA on ... real paired-end data by
checking the fraction ...
0
votes
0answers
121 views
How can I calculate and compare intra-cluster correlation for each GO term and pathway?
How can I calculate and compare intra-cluster correlation for each GO term and pathway?
I want for all the genes, which belong to the same GO-term, calculate a similarity score. Each GO term can be ...
3
votes
2answers
130 views
How to find/build the evolutionary history of a protein from its sequence?
I would like to build the evolutionary history of a protein. For example given a FASTA entry how can I build an evolutionary tree? Here is the 5wxy protein for example:
...
2
votes
1answer
141 views
How is a principal component analysis for population structure made from a bam or other alignment file?
I'm curious how a PCA for population structure is built from an alignment/BAM or SAM file. How do programs like angsd and ngsCovar actually build a PCA? What exactly makes things come out as different ...
6
votes
2answers
163 views
Estimate the length of poly-A tails from randomly-primed RNAseq data
So a poly-A tail is a long chain of adenine nucleotides that is added to a messenger RNA (mRNA) molecule during RNA processing to increase the stability of the molecule.
For my project, I would like ...
3
votes
0answers
37 views
Large range parameter identification
I have a model (ODE) of an enzymatic reaction, and I'd like to estimate four of its parameters to fit some available data. To obtain the model I am just using Mass-Action Kinetics.
Some more details:
...
1
vote
2answers
122 views
Can structural equation modeling be used in Bioinformatics?
I am a bioinformatics student and I was learning the basics of structural equation modeling (SEM) to help one of my friends.
I was wondering, are there any applications of SEM in bioinformatics? Any ...
4
votes
0answers
49 views
Help with identifying disease modules
I've made an application that at this point ranks all combinations of drug pairs relevant to a biological network/graph in the order of how disruptive the outcome of deleting the targets of a given ...
8
votes
1answer
2k views
How are MACS2's narrow peak and broad peak algorithms different?
The peak calling tool MACS2 can call peaks in either narrow peak mode (for focused signals like transcription factor ChIPseq) or broad peak mode (for more defuse signals, like certain histone ...
22
votes
4answers
1k views
Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?
A common bioinformatics task is to decompose a DNA sequence into its constituent k-mers and compute a hash value for each k-mer. Rolling hash functions are an appealing solution for this task, since ...
