Need to edit/enhance a java program

  • Posted:
  • Proposals: 0
  • Remote
  • #35283
  • Archived
  • 0


Experience Level: Intermediate
I need someone to enhance a needleman-wunsch algorithm that I have implemented. The algorithm calculates the distance between two strings (it is an approximate string matching algorithm). It does this by recursively calculating a needleman-wunsch matrix. Each part of the matrix is calculated from the three immediate cells situated from it: the one above, the one to the left, and the one to the top left (diagonal). The value that is chosen is the maximum from these three calculations. However, I need a 'traceback' matrix where, when a value is chosen from these three, it then stores either 'up','diag',or 'left' in that cell in the traceback matrix.

When both matrices are finished, we begin the traceback from the bottom-right value in the traceback matrix. A diag command means that the character is lined up, a left command means that a gap is inserted into the pattern being searched for, and an up command means that a gap is inserted into the text being searched from. I need this traceback matrix then to produce the alignment, with a certain amount of errors tolerated.

For example:

text: abcdhellogi
pattern: helli
errors: 1

would give the outcome:

- - - -helli- -

An error is where the character does not line up with the final alignment (i.e. 'i' does not match 'o' but we have allowed for 1 error, therefore it lines up).

I have attached two very good pdfs that explain the process (probably better than I have).

If you would like any more information, please ask.


New Proposal

Create an account now and send a proposal now to get this job.

Sign up

Clarification Board Ask a Question

    There are no clarification messages.