Maximum Subsequence Sum in Perl
No Comments »#!/usr/bin/perl
# Date: 25 Feb 2006
# Revised: 21 Oct 2007
# By: Me (ycl6 / ycl6 [at] users [dot] sourceforge [dot] net)
# Generate a range of 10 numbers between -10 ~ 10
my $total = 10;
my @array;
for ($i=0; $i < $total; $i++)
{
my $random_number = int(rand(20) - 10);
push @array, $random_number;
}
sub print
{
print "Numbers: ";
foreach $random_number (@array)
{
print "$random_number ";
}
print "\n";
}
print "=== Method 1 ===\n";
&print;
my $summax = 0;
my $sum = 0;
for ($i = 0; $i < $total -1; $i++)
{
for ($j = $i; $j < $total; $j++)
{
$sum = 0;
print "Reset sum to 0\n";
for ($k = $i; $k <= $j; $k++)
{
print "i = $i\t\tj = $j\t\tk = $k\t\t";
print "\$sum ($sum) + \$array[\$k] ($array[$k]) = ", $sum + $array[$k], "\n";
$sum = $sum + $array[$k];
if ($summax < $sum)
{
$summax = $sum;
print "+++ Current Max Sum: $summax\n";
}
}
}
}
print "\nMaximum Subsequence Sum = $summax\n";
print "\n=== Method 2 ===\n";
&print;
my $summax = 0;
my $sum = 0;
for ($i = 0; $i < $total; $i++)
{
$sum = 0;
print "Reset sum to 0\n";
for ($j = $i; $j < $total; $j++)
{
print "i = $i\t\tj = $j\t\t";
print "\$sum ($sum) + \$array[\$j] ($array[$j]) = ", $sum + $array[$j], "\n";
$sum = $sum + $array[$j];
if ($summax < $sum)
{
$summax = $sum;
print "+++ Current Max Sum: $summax\n";
}
}
}
print "\nMaximum Subsequence Sum = $summax\n";
print "\n=== Method 3 ===\n";
&print;
my $summax = 0;
my $sum = 0;
for ($i = 0; $i < $total; $i++)
{
print "i = $i\t\t";
print "\$sum ($sum) + \$array[\$i] ($array[$i]) = ", $sum + $array[$i], "\n";
$sum = $sum + $array[$i];
if ($summax < $sum)
{
$summax = $sum;
print "+++ Current Max Sum: $summax\n";
}
elsif ($sum < 0)
{
$sum = 0;
print "Reset sum to 0\n";
}
}
print "\nMaximum Subsequence Sum = $summax\n";
* Divide and Conquer strategy not shown
Death receptors (APOPTOSIS)
No Comments »Source: St.George’s Hospital Medical School
Death receptors are cell surface receptors that transmit apoptosis signals initiated by specific ligands. They play an important role in apoptosis and can activate a caspase cascade within seconds of ligand binding. Induction of apoptosis via this mechanism is therefore very rapid. Death receptors belong to the tumour necrosis factor (TNF) gene superfamily and generally can have several functions other than initiating apoptosis. The best characterised of the death receptors are CD95 (or Fas), TNFR1 (TNF receptor-1) and the TRAIL (TNF-related apoptosis inducing ligand) receptors DR4 and DR5.
Figure 1: Activation of apoptosis through CD95 / Fas
Signaling by Tumour Necrosis Factor Receptor-1 (TNFR1)
TNF is produced by T-cells and activated macrophages in response to infection. By ligating TNFR1, TNF can have several effects (see Figure 1). In some cells it leads to activation of NF-kB and AP-1 which leads to the induction of a number of proinflammatory and immunomodulatory genes. In some cells, however, TNF can also induce apoptosis, although receptor ligation is rarely enough on its own to initiate apoptosis as is the case with CD95 ligand binding.
Binding of TNF alpha to TNFR1 results in receptor trimerisation and clustering of intracellular death domains. This allows binding of an intracellular adapter molecule called TRADD (TNFR-associated death domain) via interactions between death domains. TRADD has the ability to recruit a number of different proteins to the activated receptor. Recruitment of TRAF2 (TNF-associated factor 2) leads to activation of NF-kB and the JNK/Ap-1 pathway.
TRADD can also associate with FADD, which leads to the induction of apoptosis via the recruitment and cleavage of pro-caspase 8. TNFR1 is also able to mediate apoptosis through the recruitment of an adapter molecule called RAIDD (RIP-associated ICH-1 / CED-3 homologous protein with a death domain). RAIDD associates with RIP through interactions between death domains and can recruit caspase 2 through an interaction with a motif, similar to the death effector domain, known as CARD (caspase recruitment domain). Recruitment of caspase 2 leads to induction of apoptosis.
Figure 2: TNF receptor signaling
All about “Suffix”
No Comments »Source: National Institute of Standards and Technology
suffix Definition: The end characters of a string. More formally a string v is a suffix of a string u if u=u’v for some string u’.
prefix Definition: The beginning characters of a string. More formally a string v ∈ Σ* is a prefix of a string u ∈ Σ* if u=vu’ for some string u’ ∈ Σ*.
trie Definition: A tree for storing strings in which there is one node for every common prefix. The strings are stored in extra leaf nodes.
Example:
POSITION: 0 1 2 3 4 5 6 TEXT: G O O G O L $ S(0): G O O G O L $ S(1): O O G O L $ S(2): O G O L $ S(3): G O L $ S(4): O L $ S(5): L $
Principles:
The idea behind suffix TRIE is to assign to each symbol in a text an index corresponding to its position in the text. To build the suffix TRIE we use these indices instead of the actual object.
Note: The resulting tree has n+1 leaves and height n+1.
suffix tree Definition: A compact representation of a trie corresponding to the suffixes of a given string where all nodes with one child are merged with their parents.
The suffix tree is created by TRIMMING (compacting + collapsing every unary node) of the suffix TRIE.
We store pointers rather than words in the leaves. And we replaced every string by a pair of indices, (a,b), where a is the index of the beginning of the string and b the index of the end of the string. i.e: We write
Remark: This make the storage in a suffix tree strickly O(n).
Search in suffix tree
Searching for all instances of a substring S in a suffix tree is easy since the symbols in S define a path down the suffix tree. Following this path, if we encountered a NIL pointer before reaching the end, then S is not in the tree. If we end up at a node x then S occurs at least once. Moreover the places where S can be found are given by the pointers in all the leaves in the subtree rooted at x.
Pseudo-code for searching in suffix tree:
SEARCH()
Start at root
Go down the tree by taking each time the corresponding bifurcation
If S correspond to a node then return all leaves in subtree
If S encountered a NIL pointer then S is not in the tree
For example:
If S = “GO” we take the GO bifurcation and return: GOOGOL$,GOL$.
If S = “OR” we take the O bifurcation and then we hit a NIL pointer so “OR” is not in the tree.
suffix array Definition: An array of all starting positions of suffixes of a string in lexicographical order, which allows a binary search.