< ^ From:

< ^ Subject:

Actually, the NrArrangement algorithm is exactly the enumeration algorithm

I need for the problem I'm solving. I would just like to know if there is

a reference (literature or textbook) explaining the algorithm, how it was

developed, etc.

FYI, our group has developed a novel piece of software which searches

protein sequence databases for evolutionary matches to a fragmented query

whose positional residue assignments are known but fragmentary residue

assignments are unknown (and therefore deconvolved by our algorithm).

An example is the easiest way to explain this better:

Say that the "true" matching protein has this sequence:

ACDGHTYERYGHDFIPLKFNDEQWSTRF

Let's take 3 fragments from this protein:

ACDG,

HDFI,

NDEQ

Now, shuffle the residues in each column (position):

ADEI,

NDDQ,

HCFG

This is what our queries look like. They are the result of a biochemical

experiment where an unknown protein is cleaved into fragments and then the

aggregate mixture of fragments is put into an "Edman Sequencer", which

determines the aggregate sequence of the fragments at each position, but

cannot specify to which fragment each residue belongs.

I use a variation of the NrArrangement algorithm to determine the total

number of possible "deconvolved" fragment alignments, given that an

alignment can involve between 1..K fragments. This factor helps us

to define the effective search space when calculating the statistical

significance of any alignment.

In truth, since our algorithm is not optimal, but a fast heuristic, it

turns out that for longer queries with multiple fragments, the effective

search space is much smaller than the theoretically possible search space

defined by the query, so we perform Poisson fitting to adjust our

statistics accordingly.

Both the code and the paper describing this algorithm include

acknowledgement and references to the GAP development team. But I'd also

like to know where the NrArrangment algorithm came from (if even just

"Uhh, it's obvious graduate level combinatorics").

Thanks again,

-Aaron Mackey

On Tue, 22 Feb 2000, Neil Zanella wrote:

Hi,

Are you looking for an algorithm to enumerate permutations?

If so are all of the objects being permuted indistinguishable?

Do you need a lexicographic enumeration or any enumeration?

Why do you need such an enumeration algorithm. Most such algorithms

are almost impractical as they consume a lot of time especially

for n > 15 or so. What do you need such an algorithm for?Regards,

Neil Zanella

nzanella@cs.mun.caOn Mon, 21 Feb 2000, Aaron J Mackey wrote:I would be grateful for any references or pointers regarding the

enumeration algorithm used by NrArrangements. Thank you.-Aaron Mackey

-- o ~ ~ ~ ~ ~ ~ o / Aaron J Mackey \ \ Dr. Pearson Laboratory / \ University of Virginia \ / (804) 924-2821 \ \ amackey@virginia.edu / o ~ ~ ~ ~ ~ ~ o

-- o ~ ~ ~ ~ ~ ~ o / Aaron J Mackey \ \ Dr. Pearson Laboratory / \ University of Virginia \ / (804) 924-2821 \ \ amackey@virginia.edu / o ~ ~ ~ ~ ~ ~ o

Miles-Receive-Header: reply

> < [top]